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 true zero if the stmt was changed. */
546 forward_propagate_into_cond (gimple_stmt_iterator *gsi_p)
548 gimple stmt = gsi_stmt (*gsi_p);
549 tree tmp = NULL_TREE;
550 tree cond = gimple_assign_rhs1 (stmt);
552 /* We can do tree combining on SSA_NAME and comparison expressions. */
553 if (COMPARISON_CLASS_P (cond))
554 tmp = forward_propagate_into_comparison_1 (stmt, TREE_CODE (cond),
556 TREE_OPERAND (cond, 0),
557 TREE_OPERAND (cond, 1));
558 else if (TREE_CODE (cond) == SSA_NAME)
561 gimple def_stmt = get_prop_source_stmt (name, true, NULL);
562 if (!def_stmt || !can_propagate_from (def_stmt))
565 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_comparison)
566 tmp = fold_build2_loc (gimple_location (def_stmt),
567 gimple_assign_rhs_code (def_stmt),
569 gimple_assign_rhs1 (def_stmt),
570 gimple_assign_rhs2 (def_stmt));
575 if (dump_file && tmp)
577 fprintf (dump_file, " Replaced '");
578 print_generic_expr (dump_file, cond, 0);
579 fprintf (dump_file, "' with '");
580 print_generic_expr (dump_file, tmp, 0);
581 fprintf (dump_file, "'\n");
584 if (integer_onep (tmp))
585 gimple_assign_set_rhs_from_tree (gsi_p, gimple_assign_rhs2 (stmt));
586 else if (integer_zerop (tmp))
587 gimple_assign_set_rhs_from_tree (gsi_p, gimple_assign_rhs3 (stmt));
589 gimple_assign_set_rhs1 (stmt, unshare_expr (tmp));
590 stmt = gsi_stmt (*gsi_p);
599 /* We've just substituted an ADDR_EXPR into stmt. Update all the
600 relevant data structures to match. */
603 tidy_after_forward_propagate_addr (gimple stmt)
605 /* We may have turned a trapping insn into a non-trapping insn. */
606 if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
607 && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
610 if (TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR)
611 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt));
614 /* DEF_RHS contains the address of the 0th element in an array.
615 USE_STMT uses type of DEF_RHS to compute the address of an
616 arbitrary element within the array. The (variable) byte offset
617 of the element is contained in OFFSET.
619 We walk back through the use-def chains of OFFSET to verify that
620 it is indeed computing the offset of an element within the array
621 and extract the index corresponding to the given byte offset.
623 We then try to fold the entire address expression into a form
626 If we are successful, we replace the right hand side of USE_STMT
627 with the new address computation. */
630 forward_propagate_addr_into_variable_array_index (tree offset,
632 gimple_stmt_iterator *use_stmt_gsi)
635 gimple offset_def, use_stmt = gsi_stmt (*use_stmt_gsi);
638 if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == ARRAY_REF)
639 tunit = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (def_rhs)));
640 else if (TREE_CODE (TREE_TYPE (TREE_OPERAND (def_rhs, 0))) == ARRAY_TYPE)
641 tunit = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (TREE_TYPE (def_rhs))));
644 if (!host_integerp (tunit, 1))
647 /* Get the offset's defining statement. */
648 offset_def = SSA_NAME_DEF_STMT (offset);
650 /* Try to find an expression for a proper index. This is either a
651 multiplication expression by the element size or just the ssa name we came
652 along in case the element size is one. In that case, however, we do not
653 allow multiplications because they can be computing index to a higher
654 level dimension (PR 37861). */
655 if (integer_onep (tunit))
657 if (is_gimple_assign (offset_def)
658 && gimple_assign_rhs_code (offset_def) == MULT_EXPR)
665 /* The statement which defines OFFSET before type conversion
666 must be a simple GIMPLE_ASSIGN. */
667 if (!is_gimple_assign (offset_def))
670 /* The RHS of the statement which defines OFFSET must be a
671 multiplication of an object by the size of the array elements.
672 This implicitly verifies that the size of the array elements
674 if (gimple_assign_rhs_code (offset_def) == MULT_EXPR
675 && TREE_CODE (gimple_assign_rhs2 (offset_def)) == INTEGER_CST
676 && tree_int_cst_equal (gimple_assign_rhs2 (offset_def), tunit))
678 /* The first operand to the MULT_EXPR is the desired index. */
679 index = gimple_assign_rhs1 (offset_def);
681 /* If we have idx * tunit + CST * tunit re-associate that. */
682 else if ((gimple_assign_rhs_code (offset_def) == PLUS_EXPR
683 || gimple_assign_rhs_code (offset_def) == MINUS_EXPR)
684 && TREE_CODE (gimple_assign_rhs1 (offset_def)) == SSA_NAME
685 && TREE_CODE (gimple_assign_rhs2 (offset_def)) == INTEGER_CST
686 && (tmp = div_if_zero_remainder (EXACT_DIV_EXPR,
687 gimple_assign_rhs2 (offset_def),
688 tunit)) != NULL_TREE)
690 gimple offset_def2 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (offset_def));
691 if (is_gimple_assign (offset_def2)
692 && gimple_assign_rhs_code (offset_def2) == MULT_EXPR
693 && TREE_CODE (gimple_assign_rhs2 (offset_def2)) == INTEGER_CST
694 && tree_int_cst_equal (gimple_assign_rhs2 (offset_def2), tunit))
696 index = fold_build2 (gimple_assign_rhs_code (offset_def),
698 gimple_assign_rhs1 (offset_def2), tmp);
707 /* Replace the pointer addition with array indexing. */
708 index = force_gimple_operand_gsi (use_stmt_gsi, index, true, NULL_TREE,
709 true, GSI_SAME_STMT);
710 if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == ARRAY_REF)
712 new_rhs = unshare_expr (def_rhs);
713 TREE_OPERAND (TREE_OPERAND (new_rhs, 0), 1) = index;
717 new_rhs = build4 (ARRAY_REF, TREE_TYPE (TREE_TYPE (TREE_TYPE (def_rhs))),
718 unshare_expr (TREE_OPERAND (def_rhs, 0)),
719 index, integer_zero_node, NULL_TREE);
720 new_rhs = build_fold_addr_expr (new_rhs);
721 if (!useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (use_stmt)),
722 TREE_TYPE (new_rhs)))
724 new_rhs = force_gimple_operand_gsi (use_stmt_gsi, new_rhs, true,
725 NULL_TREE, true, GSI_SAME_STMT);
726 new_rhs = fold_convert (TREE_TYPE (gimple_assign_lhs (use_stmt)),
730 gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs);
731 use_stmt = gsi_stmt (*use_stmt_gsi);
733 /* That should have created gimple, so there is no need to
734 record information to undo the propagation. */
735 fold_stmt_inplace (use_stmt);
736 tidy_after_forward_propagate_addr (use_stmt);
740 /* NAME is a SSA_NAME representing DEF_RHS which is of the form
741 ADDR_EXPR <whatever>.
743 Try to forward propagate the ADDR_EXPR into the use USE_STMT.
744 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
745 node or for recovery of array indexing from pointer arithmetic.
747 Return true if the propagation was successful (the propagation can
748 be not totally successful, yet things may have been changed). */
751 forward_propagate_addr_expr_1 (tree name, tree def_rhs,
752 gimple_stmt_iterator *use_stmt_gsi,
755 tree lhs, rhs, rhs2, array_ref;
756 gimple use_stmt = gsi_stmt (*use_stmt_gsi);
757 enum tree_code rhs_code;
760 gcc_assert (TREE_CODE (def_rhs) == ADDR_EXPR);
762 lhs = gimple_assign_lhs (use_stmt);
763 rhs_code = gimple_assign_rhs_code (use_stmt);
764 rhs = gimple_assign_rhs1 (use_stmt);
766 /* Trivial cases. The use statement could be a trivial copy or a
767 useless conversion. Recurse to the uses of the lhs as copyprop does
768 not copy through different variant pointers and FRE does not catch
769 all useless conversions. Treat the case of a single-use name and
770 a conversion to def_rhs type separate, though. */
771 if (TREE_CODE (lhs) == SSA_NAME
772 && ((rhs_code == SSA_NAME && rhs == name)
773 || CONVERT_EXPR_CODE_P (rhs_code)))
775 /* Only recurse if we don't deal with a single use or we cannot
776 do the propagation to the current statement. In particular
777 we can end up with a conversion needed for a non-invariant
778 address which we cannot do in a single statement. */
780 || (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs))
781 && (!is_gimple_min_invariant (def_rhs)
782 || (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
783 && POINTER_TYPE_P (TREE_TYPE (def_rhs))
784 && (TYPE_PRECISION (TREE_TYPE (lhs))
785 > TYPE_PRECISION (TREE_TYPE (def_rhs)))))))
786 return forward_propagate_addr_expr (lhs, def_rhs);
788 gimple_assign_set_rhs1 (use_stmt, unshare_expr (def_rhs));
789 if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
790 gimple_assign_set_rhs_code (use_stmt, TREE_CODE (def_rhs));
792 gimple_assign_set_rhs_code (use_stmt, NOP_EXPR);
796 /* Propagate through constant pointer adjustments. */
797 if (TREE_CODE (lhs) == SSA_NAME
798 && rhs_code == POINTER_PLUS_EXPR
800 && TREE_CODE (gimple_assign_rhs2 (use_stmt)) == INTEGER_CST)
803 /* As we come here with non-invariant addresses in def_rhs we need
804 to make sure we can build a valid constant offsetted address
805 for further propagation. Simply rely on fold building that
806 and check after the fact. */
807 new_def_rhs = fold_build2 (MEM_REF, TREE_TYPE (TREE_TYPE (rhs)),
809 fold_convert (ptr_type_node,
810 gimple_assign_rhs2 (use_stmt)));
811 if (TREE_CODE (new_def_rhs) == MEM_REF
812 && !is_gimple_mem_ref_addr (TREE_OPERAND (new_def_rhs, 0)))
814 new_def_rhs = build_fold_addr_expr_with_type (new_def_rhs,
817 /* Recurse. If we could propagate into all uses of lhs do not
818 bother to replace into the current use but just pretend we did. */
819 if (TREE_CODE (new_def_rhs) == ADDR_EXPR
820 && forward_propagate_addr_expr (lhs, new_def_rhs))
823 if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (new_def_rhs)))
824 gimple_assign_set_rhs_with_ops (use_stmt_gsi, TREE_CODE (new_def_rhs),
825 new_def_rhs, NULL_TREE);
826 else if (is_gimple_min_invariant (new_def_rhs))
827 gimple_assign_set_rhs_with_ops (use_stmt_gsi, NOP_EXPR,
828 new_def_rhs, NULL_TREE);
831 gcc_assert (gsi_stmt (*use_stmt_gsi) == use_stmt);
832 update_stmt (use_stmt);
836 /* Now strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
837 ADDR_EXPR will not appear on the LHS. */
838 lhs = gimple_assign_lhs (use_stmt);
839 while (handled_component_p (lhs))
840 lhs = TREE_OPERAND (lhs, 0);
842 /* Now see if the LHS node is a MEM_REF using NAME. If so,
843 propagate the ADDR_EXPR into the use of NAME and fold the result. */
844 if (TREE_CODE (lhs) == MEM_REF
845 && TREE_OPERAND (lhs, 0) == name)
848 HOST_WIDE_INT def_rhs_offset;
849 /* If the address is invariant we can always fold it. */
850 if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0),
853 double_int off = mem_ref_offset (lhs);
855 off = double_int_add (off,
856 shwi_to_double_int (def_rhs_offset));
857 if (TREE_CODE (def_rhs_base) == MEM_REF)
859 off = double_int_add (off, mem_ref_offset (def_rhs_base));
860 new_ptr = TREE_OPERAND (def_rhs_base, 0);
863 new_ptr = build_fold_addr_expr (def_rhs_base);
864 TREE_OPERAND (lhs, 0) = new_ptr;
865 TREE_OPERAND (lhs, 1)
866 = double_int_to_tree (TREE_TYPE (TREE_OPERAND (lhs, 1)), off);
867 tidy_after_forward_propagate_addr (use_stmt);
868 /* Continue propagating into the RHS if this was not the only use. */
872 /* If the LHS is a plain dereference and the value type is the same as
873 that of the pointed-to type of the address we can put the
874 dereferenced address on the LHS preserving the original alias-type. */
875 else if (gimple_assign_lhs (use_stmt) == lhs
876 && useless_type_conversion_p
877 (TREE_TYPE (TREE_OPERAND (def_rhs, 0)),
878 TREE_TYPE (gimple_assign_rhs1 (use_stmt))))
880 tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0);
881 tree new_offset, new_base, saved;
882 while (handled_component_p (*def_rhs_basep))
883 def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0);
884 saved = *def_rhs_basep;
885 if (TREE_CODE (*def_rhs_basep) == MEM_REF)
887 new_base = TREE_OPERAND (*def_rhs_basep, 0);
889 = int_const_binop (PLUS_EXPR, TREE_OPERAND (lhs, 1),
890 TREE_OPERAND (*def_rhs_basep, 1));
894 new_base = build_fold_addr_expr (*def_rhs_basep);
895 new_offset = TREE_OPERAND (lhs, 1);
897 *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep),
898 new_base, new_offset);
899 TREE_THIS_VOLATILE (*def_rhs_basep) = TREE_THIS_VOLATILE (lhs);
900 TREE_THIS_NOTRAP (*def_rhs_basep) = TREE_THIS_NOTRAP (lhs);
901 gimple_assign_set_lhs (use_stmt,
902 unshare_expr (TREE_OPERAND (def_rhs, 0)));
903 *def_rhs_basep = saved;
904 tidy_after_forward_propagate_addr (use_stmt);
905 /* Continue propagating into the RHS if this was not the
911 /* We can have a struct assignment dereferencing our name twice.
912 Note that we didn't propagate into the lhs to not falsely
913 claim we did when propagating into the rhs. */
917 /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
918 nodes from the RHS. */
919 rhs = gimple_assign_rhs1 (use_stmt);
920 if (TREE_CODE (rhs) == ADDR_EXPR)
921 rhs = TREE_OPERAND (rhs, 0);
922 while (handled_component_p (rhs))
923 rhs = TREE_OPERAND (rhs, 0);
925 /* Now see if the RHS node is a MEM_REF using NAME. If so,
926 propagate the ADDR_EXPR into the use of NAME and fold the result. */
927 if (TREE_CODE (rhs) == MEM_REF
928 && TREE_OPERAND (rhs, 0) == name)
931 HOST_WIDE_INT def_rhs_offset;
932 if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0),
935 double_int off = mem_ref_offset (rhs);
937 off = double_int_add (off,
938 shwi_to_double_int (def_rhs_offset));
939 if (TREE_CODE (def_rhs_base) == MEM_REF)
941 off = double_int_add (off, mem_ref_offset (def_rhs_base));
942 new_ptr = TREE_OPERAND (def_rhs_base, 0);
945 new_ptr = build_fold_addr_expr (def_rhs_base);
946 TREE_OPERAND (rhs, 0) = new_ptr;
947 TREE_OPERAND (rhs, 1)
948 = double_int_to_tree (TREE_TYPE (TREE_OPERAND (rhs, 1)), off);
949 fold_stmt_inplace (use_stmt);
950 tidy_after_forward_propagate_addr (use_stmt);
953 /* If the RHS is a plain dereference and the value type is the same as
954 that of the pointed-to type of the address we can put the
955 dereferenced address on the RHS preserving the original alias-type. */
956 else if (gimple_assign_rhs1 (use_stmt) == rhs
957 && useless_type_conversion_p
958 (TREE_TYPE (gimple_assign_lhs (use_stmt)),
959 TREE_TYPE (TREE_OPERAND (def_rhs, 0))))
961 tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0);
962 tree new_offset, new_base, saved;
963 while (handled_component_p (*def_rhs_basep))
964 def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0);
965 saved = *def_rhs_basep;
966 if (TREE_CODE (*def_rhs_basep) == MEM_REF)
968 new_base = TREE_OPERAND (*def_rhs_basep, 0);
970 = int_const_binop (PLUS_EXPR, TREE_OPERAND (rhs, 1),
971 TREE_OPERAND (*def_rhs_basep, 1));
975 new_base = build_fold_addr_expr (*def_rhs_basep);
976 new_offset = TREE_OPERAND (rhs, 1);
978 *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep),
979 new_base, new_offset);
980 TREE_THIS_VOLATILE (*def_rhs_basep) = TREE_THIS_VOLATILE (rhs);
981 TREE_THIS_NOTRAP (*def_rhs_basep) = TREE_THIS_NOTRAP (rhs);
982 gimple_assign_set_rhs1 (use_stmt,
983 unshare_expr (TREE_OPERAND (def_rhs, 0)));
984 *def_rhs_basep = saved;
985 fold_stmt_inplace (use_stmt);
986 tidy_after_forward_propagate_addr (use_stmt);
991 /* If the use of the ADDR_EXPR is not a POINTER_PLUS_EXPR, there
993 if (gimple_assign_rhs_code (use_stmt) != POINTER_PLUS_EXPR
994 || gimple_assign_rhs1 (use_stmt) != name)
997 /* The remaining cases are all for turning pointer arithmetic into
998 array indexing. They only apply when we have the address of
999 element zero in an array. If that is not the case then there
1000 is nothing to do. */
1001 array_ref = TREE_OPERAND (def_rhs, 0);
1002 if ((TREE_CODE (array_ref) != ARRAY_REF
1003 || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE
1004 || TREE_CODE (TREE_OPERAND (array_ref, 1)) != INTEGER_CST)
1005 && TREE_CODE (TREE_TYPE (array_ref)) != ARRAY_TYPE)
1008 rhs2 = gimple_assign_rhs2 (use_stmt);
1009 /* Optimize &x[C1] p+ C2 to &x p+ C3 with C3 = C1 * element_size + C2. */
1010 if (TREE_CODE (rhs2) == INTEGER_CST)
1012 tree new_rhs = build1_loc (gimple_location (use_stmt),
1013 ADDR_EXPR, TREE_TYPE (def_rhs),
1014 fold_build2 (MEM_REF,
1015 TREE_TYPE (TREE_TYPE (def_rhs)),
1016 unshare_expr (def_rhs),
1017 fold_convert (ptr_type_node,
1019 gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs);
1020 use_stmt = gsi_stmt (*use_stmt_gsi);
1021 update_stmt (use_stmt);
1022 tidy_after_forward_propagate_addr (use_stmt);
1026 /* Try to optimize &x[0] p+ OFFSET where OFFSET is defined by
1027 converting a multiplication of an index by the size of the
1028 array elements, then the result is converted into the proper
1029 type for the arithmetic. */
1030 if (TREE_CODE (rhs2) == SSA_NAME
1031 && (TREE_CODE (array_ref) != ARRAY_REF
1032 || integer_zerop (TREE_OPERAND (array_ref, 1)))
1033 && useless_type_conversion_p (TREE_TYPE (name), TREE_TYPE (def_rhs))
1034 /* Avoid problems with IVopts creating PLUS_EXPRs with a
1035 different type than their operands. */
1036 && useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
1037 return forward_propagate_addr_into_variable_array_index (rhs2, def_rhs,
1042 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
1044 Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME.
1045 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
1046 node or for recovery of array indexing from pointer arithmetic.
1047 Returns true, if all uses have been propagated into. */
1050 forward_propagate_addr_expr (tree name, tree rhs)
1052 int stmt_loop_depth = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_depth;
1053 imm_use_iterator iter;
1056 bool single_use_p = has_single_use (name);
1058 FOR_EACH_IMM_USE_STMT (use_stmt, iter, name)
1063 /* If the use is not in a simple assignment statement, then
1064 there is nothing we can do. */
1065 if (gimple_code (use_stmt) != GIMPLE_ASSIGN)
1067 if (!is_gimple_debug (use_stmt))
1072 /* If the use is in a deeper loop nest, then we do not want
1073 to propagate non-invariant ADDR_EXPRs into the loop as that
1074 is likely adding expression evaluations into the loop. */
1075 if (gimple_bb (use_stmt)->loop_depth > stmt_loop_depth
1076 && !is_gimple_min_invariant (rhs))
1083 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1084 result = forward_propagate_addr_expr_1 (name, rhs, &gsi,
1086 /* If the use has moved to a different statement adjust
1087 the update machinery for the old statement too. */
1088 if (use_stmt != gsi_stmt (gsi))
1090 update_stmt (use_stmt);
1091 use_stmt = gsi_stmt (gsi);
1094 update_stmt (use_stmt);
1098 /* Remove intermediate now unused copy and conversion chains. */
1099 use_rhs = gimple_assign_rhs1 (use_stmt);
1101 && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
1102 && TREE_CODE (use_rhs) == SSA_NAME
1103 && has_zero_uses (gimple_assign_lhs (use_stmt)))
1105 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1106 release_defs (use_stmt);
1107 gsi_remove (&gsi, true);
1111 return all && has_zero_uses (name);
1115 /* Forward propagate the comparison defined in STMT like
1116 cond_1 = x CMP y to uses of the form
1120 Returns true if stmt is now unused. */
1123 forward_propagate_comparison (gimple stmt)
1125 tree name = gimple_assign_lhs (stmt);
1127 tree tmp = NULL_TREE;
1128 gimple_stmt_iterator gsi;
1129 enum tree_code code;
1132 /* Don't propagate ssa names that occur in abnormal phis. */
1133 if ((TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
1134 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)))
1135 || (TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME
1136 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs2 (stmt))))
1139 /* Do not un-cse comparisons. But propagate through copies. */
1140 use_stmt = get_prop_dest_stmt (name, &name);
1142 || !is_gimple_assign (use_stmt))
1145 code = gimple_assign_rhs_code (use_stmt);
1146 lhs = gimple_assign_lhs (use_stmt);
1147 if (!INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
1150 /* We can propagate the condition into a statement that
1151 computes the logical negation of the comparison result. */
1152 if ((code == BIT_NOT_EXPR
1153 && TYPE_PRECISION (TREE_TYPE (lhs)) == 1)
1154 || (code == BIT_XOR_EXPR
1155 && integer_onep (gimple_assign_rhs2 (use_stmt))))
1157 tree type = TREE_TYPE (gimple_assign_rhs1 (stmt));
1158 bool nans = HONOR_NANS (TYPE_MODE (type));
1159 enum tree_code inv_code;
1160 inv_code = invert_tree_comparison (gimple_assign_rhs_code (stmt), nans);
1161 if (inv_code == ERROR_MARK)
1164 tmp = build2 (inv_code, TREE_TYPE (lhs), gimple_assign_rhs1 (stmt),
1165 gimple_assign_rhs2 (stmt));
1170 gsi = gsi_for_stmt (use_stmt);
1171 gimple_assign_set_rhs_from_tree (&gsi, unshare_expr (tmp));
1172 use_stmt = gsi_stmt (gsi);
1173 update_stmt (use_stmt);
1175 if (dump_file && (dump_flags & TDF_DETAILS))
1177 fprintf (dump_file, " Replaced '");
1178 print_gimple_expr (dump_file, stmt, 0, dump_flags);
1179 fprintf (dump_file, "' with '");
1180 print_gimple_expr (dump_file, use_stmt, 0, dump_flags);
1181 fprintf (dump_file, "'\n");
1184 /* Remove defining statements. */
1185 return remove_prop_source_from_use (name);
1189 /* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y.
1190 If so, we can change STMT into lhs = y which can later be copy
1191 propagated. Similarly for negation.
1193 This could trivially be formulated as a forward propagation
1194 to immediate uses. However, we already had an implementation
1195 from DOM which used backward propagation via the use-def links.
1197 It turns out that backward propagation is actually faster as
1198 there's less work to do for each NOT/NEG expression we find.
1199 Backwards propagation needs to look at the statement in a single
1200 backlink. Forward propagation needs to look at potentially more
1201 than one forward link.
1203 Returns true when the statement was changed. */
1206 simplify_not_neg_expr (gimple_stmt_iterator *gsi_p)
1208 gimple stmt = gsi_stmt (*gsi_p);
1209 tree rhs = gimple_assign_rhs1 (stmt);
1210 gimple rhs_def_stmt = SSA_NAME_DEF_STMT (rhs);
1212 /* See if the RHS_DEF_STMT has the same form as our statement. */
1213 if (is_gimple_assign (rhs_def_stmt)
1214 && gimple_assign_rhs_code (rhs_def_stmt) == gimple_assign_rhs_code (stmt))
1216 tree rhs_def_operand = gimple_assign_rhs1 (rhs_def_stmt);
1218 /* Verify that RHS_DEF_OPERAND is a suitable SSA_NAME. */
1219 if (TREE_CODE (rhs_def_operand) == SSA_NAME
1220 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand))
1222 gimple_assign_set_rhs_from_tree (gsi_p, rhs_def_operand);
1223 stmt = gsi_stmt (*gsi_p);
1232 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
1233 the condition which we may be able to optimize better. */
1236 simplify_gimple_switch (gimple stmt)
1238 tree cond = gimple_switch_index (stmt);
1242 /* The optimization that we really care about is removing unnecessary
1243 casts. That will let us do much better in propagating the inferred
1244 constant at the switch target. */
1245 if (TREE_CODE (cond) == SSA_NAME)
1247 def_stmt = SSA_NAME_DEF_STMT (cond);
1248 if (is_gimple_assign (def_stmt))
1250 if (gimple_assign_rhs_code (def_stmt) == NOP_EXPR)
1255 def = gimple_assign_rhs1 (def_stmt);
1257 /* ??? Why was Jeff testing this? We are gimple... */
1258 gcc_checking_assert (is_gimple_val (def));
1260 to = TREE_TYPE (cond);
1261 ti = TREE_TYPE (def);
1263 /* If we have an extension that preserves value, then we
1264 can copy the source value into the switch. */
1266 need_precision = TYPE_PRECISION (ti);
1268 if (! INTEGRAL_TYPE_P (ti))
1270 else if (TYPE_UNSIGNED (to) && !TYPE_UNSIGNED (ti))
1272 else if (!TYPE_UNSIGNED (to) && TYPE_UNSIGNED (ti))
1273 need_precision += 1;
1274 if (TYPE_PRECISION (to) < need_precision)
1279 gimple_switch_set_index (stmt, def);
1290 /* For pointers p2 and p1 return p2 - p1 if the
1291 difference is known and constant, otherwise return NULL. */
1294 constant_pointer_difference (tree p1, tree p2)
1297 #define CPD_ITERATIONS 5
1298 tree exps[2][CPD_ITERATIONS];
1299 tree offs[2][CPD_ITERATIONS];
1302 for (i = 0; i < 2; i++)
1304 tree p = i ? p1 : p2;
1305 tree off = size_zero_node;
1307 enum tree_code code;
1309 /* For each of p1 and p2 we need to iterate at least
1310 twice, to handle ADDR_EXPR directly in p1/p2,
1311 SSA_NAME with ADDR_EXPR or POINTER_PLUS_EXPR etc.
1312 on definition's stmt RHS. Iterate a few extra times. */
1316 if (!POINTER_TYPE_P (TREE_TYPE (p)))
1318 if (TREE_CODE (p) == ADDR_EXPR)
1320 tree q = TREE_OPERAND (p, 0);
1321 HOST_WIDE_INT offset;
1322 tree base = get_addr_base_and_unit_offset (q, &offset);
1327 off = size_binop (PLUS_EXPR, off, size_int (offset));
1329 if (TREE_CODE (q) == MEM_REF
1330 && TREE_CODE (TREE_OPERAND (q, 0)) == SSA_NAME)
1332 p = TREE_OPERAND (q, 0);
1333 off = size_binop (PLUS_EXPR, off,
1334 double_int_to_tree (sizetype,
1335 mem_ref_offset (q)));
1344 if (TREE_CODE (p) != SSA_NAME)
1348 if (j == CPD_ITERATIONS)
1350 stmt = SSA_NAME_DEF_STMT (p);
1351 if (!is_gimple_assign (stmt) || gimple_assign_lhs (stmt) != p)
1353 code = gimple_assign_rhs_code (stmt);
1354 if (code == POINTER_PLUS_EXPR)
1356 if (TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST)
1358 off = size_binop (PLUS_EXPR, off, gimple_assign_rhs2 (stmt));
1359 p = gimple_assign_rhs1 (stmt);
1361 else if (code == ADDR_EXPR || code == NOP_EXPR)
1362 p = gimple_assign_rhs1 (stmt);
1370 for (i = 0; i < cnt[0]; i++)
1371 for (j = 0; j < cnt[1]; j++)
1372 if (exps[0][i] == exps[1][j])
1373 return size_binop (MINUS_EXPR, offs[0][i], offs[1][j]);
1378 /* *GSI_P is a GIMPLE_CALL to a builtin function.
1380 memcpy (p, "abcd", 4);
1381 memset (p + 4, ' ', 3);
1383 memcpy (p, "abcd ", 7);
1384 call if the latter can be stored by pieces during expansion. */
1387 simplify_builtin_call (gimple_stmt_iterator *gsi_p, tree callee2)
1389 gimple stmt1, stmt2 = gsi_stmt (*gsi_p);
1390 tree vuse = gimple_vuse (stmt2);
1393 stmt1 = SSA_NAME_DEF_STMT (vuse);
1395 switch (DECL_FUNCTION_CODE (callee2))
1397 case BUILT_IN_MEMSET:
1398 if (gimple_call_num_args (stmt2) != 3
1399 || gimple_call_lhs (stmt2)
1401 || BITS_PER_UNIT != 8)
1406 tree ptr1, src1, str1, off1, len1, lhs1;
1407 tree ptr2 = gimple_call_arg (stmt2, 0);
1408 tree val2 = gimple_call_arg (stmt2, 1);
1409 tree len2 = gimple_call_arg (stmt2, 2);
1410 tree diff, vdef, new_str_cst;
1412 unsigned int ptr1_align;
1413 unsigned HOST_WIDE_INT src_len;
1415 use_operand_p use_p;
1417 if (!host_integerp (val2, 0)
1418 || !host_integerp (len2, 1))
1420 if (is_gimple_call (stmt1))
1422 /* If first stmt is a call, it needs to be memcpy
1423 or mempcpy, with string literal as second argument and
1425 callee1 = gimple_call_fndecl (stmt1);
1426 if (callee1 == NULL_TREE
1427 || DECL_BUILT_IN_CLASS (callee1) != BUILT_IN_NORMAL
1428 || gimple_call_num_args (stmt1) != 3)
1430 if (DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMCPY
1431 && DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMPCPY)
1433 ptr1 = gimple_call_arg (stmt1, 0);
1434 src1 = gimple_call_arg (stmt1, 1);
1435 len1 = gimple_call_arg (stmt1, 2);
1436 lhs1 = gimple_call_lhs (stmt1);
1437 if (!host_integerp (len1, 1))
1439 str1 = string_constant (src1, &off1);
1440 if (str1 == NULL_TREE)
1442 if (!host_integerp (off1, 1)
1443 || compare_tree_int (off1, TREE_STRING_LENGTH (str1) - 1) > 0
1444 || compare_tree_int (len1, TREE_STRING_LENGTH (str1)
1445 - tree_low_cst (off1, 1)) > 0
1446 || TREE_CODE (TREE_TYPE (str1)) != ARRAY_TYPE
1447 || TYPE_MODE (TREE_TYPE (TREE_TYPE (str1)))
1448 != TYPE_MODE (char_type_node))
1451 else if (gimple_assign_single_p (stmt1))
1453 /* Otherwise look for length 1 memcpy optimized into
1455 ptr1 = gimple_assign_lhs (stmt1);
1456 src1 = gimple_assign_rhs1 (stmt1);
1457 if (TREE_CODE (ptr1) != MEM_REF
1458 || TYPE_MODE (TREE_TYPE (ptr1)) != TYPE_MODE (char_type_node)
1459 || !host_integerp (src1, 0))
1461 ptr1 = build_fold_addr_expr (ptr1);
1462 callee1 = NULL_TREE;
1463 len1 = size_one_node;
1465 off1 = size_zero_node;
1471 diff = constant_pointer_difference (ptr1, ptr2);
1472 if (diff == NULL && lhs1 != NULL)
1474 diff = constant_pointer_difference (lhs1, ptr2);
1475 if (DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1477 diff = size_binop (PLUS_EXPR, diff,
1478 fold_convert (sizetype, len1));
1480 /* If the difference between the second and first destination pointer
1481 is not constant, or is bigger than memcpy length, bail out. */
1483 || !host_integerp (diff, 1)
1484 || tree_int_cst_lt (len1, diff))
1487 /* Use maximum of difference plus memset length and memcpy length
1488 as the new memcpy length, if it is too big, bail out. */
1489 src_len = tree_low_cst (diff, 1);
1490 src_len += tree_low_cst (len2, 1);
1491 if (src_len < (unsigned HOST_WIDE_INT) tree_low_cst (len1, 1))
1492 src_len = tree_low_cst (len1, 1);
1496 /* If mempcpy value is used elsewhere, bail out, as mempcpy
1497 with bigger length will return different result. */
1498 if (lhs1 != NULL_TREE
1499 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1500 && (TREE_CODE (lhs1) != SSA_NAME
1501 || !single_imm_use (lhs1, &use_p, &use_stmt)
1502 || use_stmt != stmt2))
1505 /* If anything reads memory in between memcpy and memset
1506 call, the modified memcpy call might change it. */
1507 vdef = gimple_vdef (stmt1);
1509 && (!single_imm_use (vdef, &use_p, &use_stmt)
1510 || use_stmt != stmt2))
1513 ptr1_align = get_pointer_alignment (ptr1);
1514 /* Construct the new source string literal. */
1515 src_buf = XALLOCAVEC (char, src_len + 1);
1518 TREE_STRING_POINTER (str1) + tree_low_cst (off1, 1),
1519 tree_low_cst (len1, 1));
1521 src_buf[0] = tree_low_cst (src1, 0);
1522 memset (src_buf + tree_low_cst (diff, 1),
1523 tree_low_cst (val2, 1), tree_low_cst (len2, 1));
1524 src_buf[src_len] = '\0';
1525 /* Neither builtin_strncpy_read_str nor builtin_memcpy_read_str
1526 handle embedded '\0's. */
1527 if (strlen (src_buf) != src_len)
1529 rtl_profile_for_bb (gimple_bb (stmt2));
1530 /* If the new memcpy wouldn't be emitted by storing the literal
1531 by pieces, this optimization might enlarge .rodata too much,
1532 as commonly used string literals couldn't be shared any
1534 if (!can_store_by_pieces (src_len,
1535 builtin_strncpy_read_str,
1536 src_buf, ptr1_align, false))
1539 new_str_cst = build_string_literal (src_len, src_buf);
1542 /* If STMT1 is a mem{,p}cpy call, adjust it and remove
1544 if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1545 gimple_call_set_lhs (stmt1, NULL_TREE);
1546 gimple_call_set_arg (stmt1, 1, new_str_cst);
1547 gimple_call_set_arg (stmt1, 2,
1548 build_int_cst (TREE_TYPE (len1), src_len));
1549 update_stmt (stmt1);
1550 unlink_stmt_vdef (stmt2);
1551 gsi_remove (gsi_p, true);
1552 release_defs (stmt2);
1553 if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1554 release_ssa_name (lhs1);
1559 /* Otherwise, if STMT1 is length 1 memcpy optimized into
1560 assignment, remove STMT1 and change memset call into
1562 gimple_stmt_iterator gsi = gsi_for_stmt (stmt1);
1564 if (!is_gimple_val (ptr1))
1565 ptr1 = force_gimple_operand_gsi (gsi_p, ptr1, true, NULL_TREE,
1566 true, GSI_SAME_STMT);
1567 gimple_call_set_fndecl (stmt2, built_in_decls [BUILT_IN_MEMCPY]);
1568 gimple_call_set_arg (stmt2, 0, ptr1);
1569 gimple_call_set_arg (stmt2, 1, new_str_cst);
1570 gimple_call_set_arg (stmt2, 2,
1571 build_int_cst (TREE_TYPE (len2), src_len));
1572 unlink_stmt_vdef (stmt1);
1573 gsi_remove (&gsi, true);
1574 release_defs (stmt1);
1575 update_stmt (stmt2);
1586 /* Checks if expression has type of one-bit precision, or is a known
1587 truth-valued expression. */
1589 truth_valued_ssa_name (tree name)
1592 tree type = TREE_TYPE (name);
1594 if (!INTEGRAL_TYPE_P (type))
1596 /* Don't check here for BOOLEAN_TYPE as the precision isn't
1597 necessarily one and so ~X is not equal to !X. */
1598 if (TYPE_PRECISION (type) == 1)
1600 def = SSA_NAME_DEF_STMT (name);
1601 if (is_gimple_assign (def))
1602 return truth_value_p (gimple_assign_rhs_code (def));
1606 /* Helper routine for simplify_bitwise_binary_1 function.
1607 Return for the SSA name NAME the expression X if it mets condition
1608 NAME = !X. Otherwise return NULL_TREE.
1609 Detected patterns for NAME = !X are:
1610 !X and X == 0 for X with integral type.
1611 X ^ 1, X != 1,or ~X for X with integral type with precision of one. */
1613 lookup_logical_inverted_value (tree name)
1616 enum tree_code code;
1619 /* If name has none-intergal type, or isn't a SSA_NAME, then
1621 if (TREE_CODE (name) != SSA_NAME
1622 || !INTEGRAL_TYPE_P (TREE_TYPE (name)))
1624 def = SSA_NAME_DEF_STMT (name);
1625 if (!is_gimple_assign (def))
1628 code = gimple_assign_rhs_code (def);
1629 op1 = gimple_assign_rhs1 (def);
1632 /* Get for EQ_EXPR or BIT_XOR_EXPR operation the second operand.
1633 If CODE isn't an EQ_EXPR, BIT_XOR_EXPR, or BIT_NOT_EXPR, then return. */
1634 if (code == EQ_EXPR || code == NE_EXPR
1635 || code == BIT_XOR_EXPR)
1636 op2 = gimple_assign_rhs2 (def);
1641 if (truth_valued_ssa_name (name))
1645 /* Check if we have X == 0 and X has an integral type. */
1646 if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)))
1648 if (integer_zerop (op2))
1652 /* Check if we have X != 1 and X is a truth-valued. */
1653 if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)))
1655 if (integer_onep (op2) && truth_valued_ssa_name (op1))
1659 /* Check if we have X ^ 1 and X is truth valued. */
1660 if (integer_onep (op2) && truth_valued_ssa_name (op1))
1670 /* Optimize ARG1 CODE ARG2 to a constant for bitwise binary
1671 operations CODE, if one operand has the logically inverted
1672 value of the other. */
1674 simplify_bitwise_binary_1 (enum tree_code code, tree type,
1675 tree arg1, tree arg2)
1679 /* If CODE isn't a bitwise binary operation, return NULL_TREE. */
1680 if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR
1681 && code != BIT_XOR_EXPR)
1684 /* First check if operands ARG1 and ARG2 are equal. If so
1685 return NULL_TREE as this optimization is handled fold_stmt. */
1688 /* See if we have in arguments logical-not patterns. */
1689 if (((anot = lookup_logical_inverted_value (arg1)) == NULL_TREE
1691 && ((anot = lookup_logical_inverted_value (arg2)) == NULL_TREE
1696 if (code == BIT_AND_EXPR)
1697 return fold_convert (type, integer_zero_node);
1698 /* X | !X -> 1 and X ^ !X -> 1, if X is truth-valued. */
1699 if (truth_valued_ssa_name (anot))
1700 return fold_convert (type, integer_one_node);
1702 /* ??? Otherwise result is (X != 0 ? X : 1). not handled. */
1706 /* Simplify bitwise binary operations.
1707 Return true if a transformation applied, otherwise return false. */
1710 simplify_bitwise_binary (gimple_stmt_iterator *gsi)
1712 gimple stmt = gsi_stmt (*gsi);
1713 tree arg1 = gimple_assign_rhs1 (stmt);
1714 tree arg2 = gimple_assign_rhs2 (stmt);
1715 enum tree_code code = gimple_assign_rhs_code (stmt);
1717 gimple def1 = NULL, def2 = NULL;
1718 tree def1_arg1, def2_arg1;
1719 enum tree_code def1_code, def2_code;
1721 def1_code = TREE_CODE (arg1);
1723 if (TREE_CODE (arg1) == SSA_NAME)
1725 def1 = SSA_NAME_DEF_STMT (arg1);
1726 if (is_gimple_assign (def1))
1728 def1_code = gimple_assign_rhs_code (def1);
1729 def1_arg1 = gimple_assign_rhs1 (def1);
1733 def2_code = TREE_CODE (arg2);
1735 if (TREE_CODE (arg2) == SSA_NAME)
1737 def2 = SSA_NAME_DEF_STMT (arg2);
1738 if (is_gimple_assign (def2))
1740 def2_code = gimple_assign_rhs_code (def2);
1741 def2_arg1 = gimple_assign_rhs1 (def2);
1745 /* Try to fold (type) X op CST -> (type) (X op ((type-x) CST)). */
1746 if (TREE_CODE (arg2) == INTEGER_CST
1747 && CONVERT_EXPR_CODE_P (def1_code)
1748 && INTEGRAL_TYPE_P (TREE_TYPE (def1_arg1))
1749 && int_fits_type_p (arg2, TREE_TYPE (def1_arg1)))
1752 tree tem = create_tmp_reg (TREE_TYPE (def1_arg1), NULL);
1754 gimple_build_assign_with_ops (code, tem, def1_arg1,
1755 fold_convert_loc (gimple_location (stmt),
1756 TREE_TYPE (def1_arg1),
1758 tem = make_ssa_name (tem, newop);
1759 gimple_assign_set_lhs (newop, tem);
1760 gimple_set_location (newop, gimple_location (stmt));
1761 gsi_insert_before (gsi, newop, GSI_SAME_STMT);
1762 gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
1763 tem, NULL_TREE, NULL_TREE);
1764 update_stmt (gsi_stmt (*gsi));
1768 /* For bitwise binary operations apply operand conversions to the
1769 binary operation result instead of to the operands. This allows
1770 to combine successive conversions and bitwise binary operations. */
1771 if (CONVERT_EXPR_CODE_P (def1_code)
1772 && CONVERT_EXPR_CODE_P (def2_code)
1773 && types_compatible_p (TREE_TYPE (def1_arg1), TREE_TYPE (def2_arg1))
1774 /* Make sure that the conversion widens the operands, or has same
1775 precision, or that it changes the operation to a bitfield
1777 && ((TYPE_PRECISION (TREE_TYPE (def1_arg1))
1778 <= TYPE_PRECISION (TREE_TYPE (arg1)))
1779 || (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (arg1)))
1781 || (TYPE_PRECISION (TREE_TYPE (arg1))
1782 != GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (arg1))))))
1785 tree tem = create_tmp_reg (TREE_TYPE (def1_arg1),
1787 newop = gimple_build_assign_with_ops (code, tem, def1_arg1, def2_arg1);
1788 tem = make_ssa_name (tem, newop);
1789 gimple_assign_set_lhs (newop, tem);
1790 gimple_set_location (newop, gimple_location (stmt));
1791 gsi_insert_before (gsi, newop, GSI_SAME_STMT);
1792 gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
1793 tem, NULL_TREE, NULL_TREE);
1794 update_stmt (gsi_stmt (*gsi));
1798 /* (a | CST1) & CST2 -> (a & CST2) | (CST1 & CST2). */
1799 if (code == BIT_AND_EXPR
1800 && def1_code == BIT_IOR_EXPR
1801 && TREE_CODE (arg2) == INTEGER_CST
1802 && TREE_CODE (gimple_assign_rhs2 (def1)) == INTEGER_CST)
1804 tree cst = fold_build2 (BIT_AND_EXPR, TREE_TYPE (arg2),
1805 arg2, gimple_assign_rhs2 (def1));
1808 if (integer_zerop (cst))
1810 gimple_assign_set_rhs1 (stmt, def1_arg1);
1814 tem = create_tmp_reg (TREE_TYPE (arg2), NULL);
1815 newop = gimple_build_assign_with_ops (BIT_AND_EXPR,
1816 tem, def1_arg1, arg2);
1817 tem = make_ssa_name (tem, newop);
1818 gimple_assign_set_lhs (newop, tem);
1819 gimple_set_location (newop, gimple_location (stmt));
1820 /* Make sure to re-process the new stmt as it's walking upwards. */
1821 gsi_insert_before (gsi, newop, GSI_NEW_STMT);
1822 gimple_assign_set_rhs1 (stmt, tem);
1823 gimple_assign_set_rhs2 (stmt, cst);
1824 gimple_assign_set_rhs_code (stmt, BIT_IOR_EXPR);
1829 /* Combine successive equal operations with constants. */
1830 if ((code == BIT_AND_EXPR
1831 || code == BIT_IOR_EXPR
1832 || code == BIT_XOR_EXPR)
1833 && def1_code == code
1834 && TREE_CODE (arg2) == INTEGER_CST
1835 && TREE_CODE (gimple_assign_rhs2 (def1)) == INTEGER_CST)
1837 tree cst = fold_build2 (code, TREE_TYPE (arg2),
1838 arg2, gimple_assign_rhs2 (def1));
1839 gimple_assign_set_rhs1 (stmt, def1_arg1);
1840 gimple_assign_set_rhs2 (stmt, cst);
1845 /* Canonicalize X ^ ~0 to ~X. */
1846 if (code == BIT_XOR_EXPR
1847 && TREE_CODE (arg2) == INTEGER_CST
1848 && integer_all_onesp (arg2))
1850 gimple_assign_set_rhs_with_ops (gsi, BIT_NOT_EXPR, arg1, NULL_TREE);
1851 gcc_assert (gsi_stmt (*gsi) == stmt);
1856 /* Try simple folding for X op !X, and X op X. */
1857 res = simplify_bitwise_binary_1 (code, TREE_TYPE (arg1), arg1, arg2);
1858 if (res != NULL_TREE)
1860 gimple_assign_set_rhs_from_tree (gsi, res);
1861 update_stmt (gsi_stmt (*gsi));
1869 /* Perform re-associations of the plus or minus statement STMT that are
1870 always permitted. Returns true if the CFG was changed. */
1873 associate_plusminus (gimple stmt)
1875 tree rhs1 = gimple_assign_rhs1 (stmt);
1876 tree rhs2 = gimple_assign_rhs2 (stmt);
1877 enum tree_code code = gimple_assign_rhs_code (stmt);
1878 gimple_stmt_iterator gsi;
1881 /* We can't reassociate at all for saturating types. */
1882 if (TYPE_SATURATING (TREE_TYPE (rhs1)))
1885 /* First contract negates. */
1890 /* A +- (-B) -> A -+ B. */
1891 if (TREE_CODE (rhs2) == SSA_NAME)
1893 gimple def_stmt = SSA_NAME_DEF_STMT (rhs2);
1894 if (is_gimple_assign (def_stmt)
1895 && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR
1896 && can_propagate_from (def_stmt))
1898 code = (code == MINUS_EXPR) ? PLUS_EXPR : MINUS_EXPR;
1899 gimple_assign_set_rhs_code (stmt, code);
1900 rhs2 = gimple_assign_rhs1 (def_stmt);
1901 gimple_assign_set_rhs2 (stmt, rhs2);
1902 gimple_set_modified (stmt, true);
1907 /* (-A) + B -> B - A. */
1908 if (TREE_CODE (rhs1) == SSA_NAME
1909 && code == PLUS_EXPR)
1911 gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
1912 if (is_gimple_assign (def_stmt)
1913 && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR
1914 && can_propagate_from (def_stmt))
1917 gimple_assign_set_rhs_code (stmt, code);
1919 gimple_assign_set_rhs1 (stmt, rhs1);
1920 rhs2 = gimple_assign_rhs1 (def_stmt);
1921 gimple_assign_set_rhs2 (stmt, rhs2);
1922 gimple_set_modified (stmt, true);
1929 /* We can't reassociate floating-point or fixed-point plus or minus
1930 because of saturation to +-Inf. */
1931 if (FLOAT_TYPE_P (TREE_TYPE (rhs1))
1932 || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1)))
1935 /* Second match patterns that allow contracting a plus-minus pair
1936 irrespective of overflow issues.
1938 (A +- B) - A -> +- B
1940 (CST +- A) +- CST -> CST +- A
1941 (A + CST) +- CST -> A + CST
1944 A - (A +- B) -> -+ B
1945 A +- (B +- A) -> +- B
1946 CST +- (CST +- A) -> CST +- A
1947 CST +- (A +- CST) -> CST +- A
1950 via commutating the addition and contracting operations to zero
1951 by reassociation. */
1953 gsi = gsi_for_stmt (stmt);
1954 if (TREE_CODE (rhs1) == SSA_NAME)
1956 gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
1957 if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt))
1959 enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
1960 if (def_code == PLUS_EXPR
1961 || def_code == MINUS_EXPR)
1963 tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
1964 tree def_rhs2 = gimple_assign_rhs2 (def_stmt);
1965 if (operand_equal_p (def_rhs1, rhs2, 0)
1966 && code == MINUS_EXPR)
1968 /* (A +- B) - A -> +- B. */
1969 code = ((def_code == PLUS_EXPR)
1970 ? TREE_CODE (def_rhs2) : NEGATE_EXPR);
1973 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
1974 gcc_assert (gsi_stmt (gsi) == stmt);
1975 gimple_set_modified (stmt, true);
1977 else if (operand_equal_p (def_rhs2, rhs2, 0)
1978 && code != def_code)
1980 /* (A +- B) -+ B -> A. */
1981 code = TREE_CODE (def_rhs1);
1984 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
1985 gcc_assert (gsi_stmt (gsi) == stmt);
1986 gimple_set_modified (stmt, true);
1988 else if (TREE_CODE (rhs2) == INTEGER_CST
1989 && TREE_CODE (def_rhs1) == INTEGER_CST)
1991 /* (CST +- A) +- CST -> CST +- A. */
1992 tree cst = fold_binary (code, TREE_TYPE (rhs1),
1994 if (cst && !TREE_OVERFLOW (cst))
1997 gimple_assign_set_rhs_code (stmt, code);
1999 gimple_assign_set_rhs1 (stmt, rhs1);
2001 gimple_assign_set_rhs2 (stmt, rhs2);
2002 gimple_set_modified (stmt, true);
2005 else if (TREE_CODE (rhs2) == INTEGER_CST
2006 && TREE_CODE (def_rhs2) == INTEGER_CST
2007 && def_code == PLUS_EXPR)
2009 /* (A + CST) +- CST -> A + CST. */
2010 tree cst = fold_binary (code, TREE_TYPE (rhs1),
2012 if (cst && !TREE_OVERFLOW (cst))
2015 gimple_assign_set_rhs_code (stmt, code);
2017 gimple_assign_set_rhs1 (stmt, rhs1);
2019 gimple_assign_set_rhs2 (stmt, rhs2);
2020 gimple_set_modified (stmt, true);
2024 else if (def_code == BIT_NOT_EXPR
2025 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
2027 tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2028 if (code == PLUS_EXPR
2029 && operand_equal_p (def_rhs1, rhs2, 0))
2033 rhs1 = build_int_cst_type (TREE_TYPE (rhs2), -1);
2035 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2036 gcc_assert (gsi_stmt (gsi) == stmt);
2037 gimple_set_modified (stmt, true);
2039 else if (code == PLUS_EXPR
2040 && integer_onep (rhs1))
2046 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2047 gcc_assert (gsi_stmt (gsi) == stmt);
2048 gimple_set_modified (stmt, true);
2054 if (rhs2 && TREE_CODE (rhs2) == SSA_NAME)
2056 gimple def_stmt = SSA_NAME_DEF_STMT (rhs2);
2057 if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt))
2059 enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
2060 if (def_code == PLUS_EXPR
2061 || def_code == MINUS_EXPR)
2063 tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2064 tree def_rhs2 = gimple_assign_rhs2 (def_stmt);
2065 if (operand_equal_p (def_rhs1, rhs1, 0)
2066 && code == MINUS_EXPR)
2068 /* A - (A +- B) -> -+ B. */
2069 code = ((def_code == PLUS_EXPR)
2070 ? NEGATE_EXPR : TREE_CODE (def_rhs2));
2073 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2074 gcc_assert (gsi_stmt (gsi) == stmt);
2075 gimple_set_modified (stmt, true);
2077 else if (operand_equal_p (def_rhs2, rhs1, 0)
2078 && code != def_code)
2080 /* A +- (B +- A) -> +- B. */
2081 code = ((code == PLUS_EXPR)
2082 ? TREE_CODE (def_rhs1) : NEGATE_EXPR);
2085 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2086 gcc_assert (gsi_stmt (gsi) == stmt);
2087 gimple_set_modified (stmt, true);
2089 else if (TREE_CODE (rhs1) == INTEGER_CST
2090 && TREE_CODE (def_rhs1) == INTEGER_CST)
2092 /* CST +- (CST +- A) -> CST +- A. */
2093 tree cst = fold_binary (code, TREE_TYPE (rhs2),
2095 if (cst && !TREE_OVERFLOW (cst))
2097 code = (code == def_code ? PLUS_EXPR : MINUS_EXPR);
2098 gimple_assign_set_rhs_code (stmt, code);
2100 gimple_assign_set_rhs1 (stmt, rhs1);
2102 gimple_assign_set_rhs2 (stmt, rhs2);
2103 gimple_set_modified (stmt, true);
2106 else if (TREE_CODE (rhs1) == INTEGER_CST
2107 && TREE_CODE (def_rhs2) == INTEGER_CST)
2109 /* CST +- (A +- CST) -> CST +- A. */
2110 tree cst = fold_binary (def_code == code
2111 ? PLUS_EXPR : MINUS_EXPR,
2114 if (cst && !TREE_OVERFLOW (cst))
2117 gimple_assign_set_rhs1 (stmt, rhs1);
2119 gimple_assign_set_rhs2 (stmt, rhs2);
2120 gimple_set_modified (stmt, true);
2124 else if (def_code == BIT_NOT_EXPR
2125 && INTEGRAL_TYPE_P (TREE_TYPE (rhs2)))
2127 tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2128 if (code == PLUS_EXPR
2129 && operand_equal_p (def_rhs1, rhs1, 0))
2133 rhs1 = build_int_cst_type (TREE_TYPE (rhs1), -1);
2135 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2136 gcc_assert (gsi_stmt (gsi) == stmt);
2137 gimple_set_modified (stmt, true);
2144 if (gimple_modified_p (stmt))
2146 fold_stmt_inplace (stmt);
2148 if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
2149 && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
2156 /* Combine two conversions in a row for the second conversion at *GSI.
2157 Returns 1 if there were any changes made, 2 if cfg-cleanup needs to
2158 run. Else it returns 0. */
2161 combine_conversions (gimple_stmt_iterator *gsi)
2163 gimple stmt = gsi_stmt (*gsi);
2166 enum tree_code code = gimple_assign_rhs_code (stmt);
2168 gcc_checking_assert (CONVERT_EXPR_CODE_P (code)
2169 || code == FLOAT_EXPR
2170 || code == FIX_TRUNC_EXPR);
2172 lhs = gimple_assign_lhs (stmt);
2173 op0 = gimple_assign_rhs1 (stmt);
2174 if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (op0)))
2176 gimple_assign_set_rhs_code (stmt, TREE_CODE (op0));
2180 if (TREE_CODE (op0) != SSA_NAME)
2183 def_stmt = SSA_NAME_DEF_STMT (op0);
2184 if (!is_gimple_assign (def_stmt))
2187 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
2189 tree defop0 = gimple_assign_rhs1 (def_stmt);
2190 tree type = TREE_TYPE (lhs);
2191 tree inside_type = TREE_TYPE (defop0);
2192 tree inter_type = TREE_TYPE (op0);
2193 int inside_int = INTEGRAL_TYPE_P (inside_type);
2194 int inside_ptr = POINTER_TYPE_P (inside_type);
2195 int inside_float = FLOAT_TYPE_P (inside_type);
2196 int inside_vec = TREE_CODE (inside_type) == VECTOR_TYPE;
2197 unsigned int inside_prec = TYPE_PRECISION (inside_type);
2198 int inside_unsignedp = TYPE_UNSIGNED (inside_type);
2199 int inter_int = INTEGRAL_TYPE_P (inter_type);
2200 int inter_ptr = POINTER_TYPE_P (inter_type);
2201 int inter_float = FLOAT_TYPE_P (inter_type);
2202 int inter_vec = TREE_CODE (inter_type) == VECTOR_TYPE;
2203 unsigned int inter_prec = TYPE_PRECISION (inter_type);
2204 int inter_unsignedp = TYPE_UNSIGNED (inter_type);
2205 int final_int = INTEGRAL_TYPE_P (type);
2206 int final_ptr = POINTER_TYPE_P (type);
2207 int final_float = FLOAT_TYPE_P (type);
2208 int final_vec = TREE_CODE (type) == VECTOR_TYPE;
2209 unsigned int final_prec = TYPE_PRECISION (type);
2210 int final_unsignedp = TYPE_UNSIGNED (type);
2212 /* In addition to the cases of two conversions in a row
2213 handled below, if we are converting something to its own
2214 type via an object of identical or wider precision, neither
2215 conversion is needed. */
2216 if (useless_type_conversion_p (type, inside_type)
2217 && (((inter_int || inter_ptr) && final_int)
2218 || (inter_float && final_float))
2219 && inter_prec >= final_prec)
2221 gimple_assign_set_rhs1 (stmt, unshare_expr (defop0));
2222 gimple_assign_set_rhs_code (stmt, TREE_CODE (defop0));
2224 return remove_prop_source_from_use (op0) ? 2 : 1;
2227 /* Likewise, if the intermediate and initial types are either both
2228 float or both integer, we don't need the middle conversion if the
2229 former is wider than the latter and doesn't change the signedness
2230 (for integers). Avoid this if the final type is a pointer since
2231 then we sometimes need the middle conversion. Likewise if the
2232 final type has a precision not equal to the size of its mode. */
2233 if (((inter_int && inside_int)
2234 || (inter_float && inside_float)
2235 || (inter_vec && inside_vec))
2236 && inter_prec >= inside_prec
2237 && (inter_float || inter_vec
2238 || inter_unsignedp == inside_unsignedp)
2239 && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (type))
2240 && TYPE_MODE (type) == TYPE_MODE (inter_type))
2242 && (! final_vec || inter_prec == inside_prec))
2244 gimple_assign_set_rhs1 (stmt, defop0);
2246 return remove_prop_source_from_use (op0) ? 2 : 1;
2249 /* If we have a sign-extension of a zero-extended value, we can
2250 replace that by a single zero-extension. */
2251 if (inside_int && inter_int && final_int
2252 && inside_prec < inter_prec && inter_prec < final_prec
2253 && inside_unsignedp && !inter_unsignedp)
2255 gimple_assign_set_rhs1 (stmt, defop0);
2257 return remove_prop_source_from_use (op0) ? 2 : 1;
2260 /* Two conversions in a row are not needed unless:
2261 - some conversion is floating-point (overstrict for now), or
2262 - some conversion is a vector (overstrict for now), or
2263 - the intermediate type is narrower than both initial and
2265 - the intermediate type and innermost type differ in signedness,
2266 and the outermost type is wider than the intermediate, or
2267 - the initial type is a pointer type and the precisions of the
2268 intermediate and final types differ, or
2269 - the final type is a pointer type and the precisions of the
2270 initial and intermediate types differ. */
2271 if (! inside_float && ! inter_float && ! final_float
2272 && ! inside_vec && ! inter_vec && ! final_vec
2273 && (inter_prec >= inside_prec || inter_prec >= final_prec)
2274 && ! (inside_int && inter_int
2275 && inter_unsignedp != inside_unsignedp
2276 && inter_prec < final_prec)
2277 && ((inter_unsignedp && inter_prec > inside_prec)
2278 == (final_unsignedp && final_prec > inter_prec))
2279 && ! (inside_ptr && inter_prec != final_prec)
2280 && ! (final_ptr && inside_prec != inter_prec)
2281 && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (type))
2282 && TYPE_MODE (type) == TYPE_MODE (inter_type)))
2284 gimple_assign_set_rhs1 (stmt, defop0);
2286 return remove_prop_source_from_use (op0) ? 2 : 1;
2289 /* A truncation to an unsigned type should be canonicalized as
2290 bitwise and of a mask. */
2291 if (final_int && inter_int && inside_int
2292 && final_prec == inside_prec
2293 && final_prec > inter_prec
2297 tem = fold_build2 (BIT_AND_EXPR, inside_type,
2300 (inside_type, double_int_mask (inter_prec)));
2301 if (!useless_type_conversion_p (type, inside_type))
2303 tem = force_gimple_operand_gsi (gsi, tem, true, NULL_TREE, true,
2305 gimple_assign_set_rhs1 (stmt, tem);
2308 gimple_assign_set_rhs_from_tree (gsi, tem);
2309 update_stmt (gsi_stmt (*gsi));
2317 /* Main entry point for the forward propagation and statement combine
2321 ssa_forward_propagate_and_combine (void)
2324 unsigned int todoflags = 0;
2326 cfg_changed = false;
2330 gimple_stmt_iterator gsi, prev;
2331 bool prev_initialized;
2333 /* Apply forward propagation to all stmts in the basic-block.
2334 Note we update GSI within the loop as necessary. */
2335 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2337 gimple stmt = gsi_stmt (gsi);
2339 enum tree_code code;
2341 if (!is_gimple_assign (stmt))
2347 lhs = gimple_assign_lhs (stmt);
2348 rhs = gimple_assign_rhs1 (stmt);
2349 code = gimple_assign_rhs_code (stmt);
2350 if (TREE_CODE (lhs) != SSA_NAME
2351 || has_zero_uses (lhs))
2357 /* If this statement sets an SSA_NAME to an address,
2358 try to propagate the address into the uses of the SSA_NAME. */
2359 if (code == ADDR_EXPR
2360 /* Handle pointer conversions on invariant addresses
2361 as well, as this is valid gimple. */
2362 || (CONVERT_EXPR_CODE_P (code)
2363 && TREE_CODE (rhs) == ADDR_EXPR
2364 && POINTER_TYPE_P (TREE_TYPE (lhs))))
2366 tree base = get_base_address (TREE_OPERAND (rhs, 0));
2369 || decl_address_invariant_p (base))
2370 && !stmt_references_abnormal_ssa_name (stmt)
2371 && forward_propagate_addr_expr (lhs, rhs))
2373 release_defs (stmt);
2374 todoflags |= TODO_remove_unused_locals;
2375 gsi_remove (&gsi, true);
2380 else if (code == POINTER_PLUS_EXPR && can_propagate_from (stmt))
2382 if (TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST
2383 /* ??? Better adjust the interface to that function
2384 instead of building new trees here. */
2385 && forward_propagate_addr_expr
2389 fold_build2 (MEM_REF,
2390 TREE_TYPE (TREE_TYPE (rhs)),
2394 gimple_assign_rhs2 (stmt))))))
2396 release_defs (stmt);
2397 todoflags |= TODO_remove_unused_locals;
2398 gsi_remove (&gsi, true);
2400 else if (is_gimple_min_invariant (rhs))
2402 /* Make sure to fold &a[0] + off_1 here. */
2403 fold_stmt_inplace (stmt);
2405 if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
2411 else if (TREE_CODE_CLASS (code) == tcc_comparison)
2413 if (forward_propagate_comparison (stmt))
2421 /* Combine stmts with the stmts defining their operands.
2422 Note we update GSI within the loop as necessary. */
2423 prev_initialized = false;
2424 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
2426 gimple stmt = gsi_stmt (gsi);
2427 bool changed = false;
2429 switch (gimple_code (stmt))
2433 tree rhs1 = gimple_assign_rhs1 (stmt);
2434 enum tree_code code = gimple_assign_rhs_code (stmt);
2436 if ((code == BIT_NOT_EXPR
2437 || code == NEGATE_EXPR)
2438 && TREE_CODE (rhs1) == SSA_NAME)
2439 changed = simplify_not_neg_expr (&gsi);
2440 else if (code == COND_EXPR)
2442 /* In this case the entire COND_EXPR is in rhs1. */
2443 changed |= forward_propagate_into_cond (&gsi);
2444 stmt = gsi_stmt (gsi);
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 */