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 "tree-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 copy chain ending in NAME along the defs.
299 If NAME was replaced in its only use then this function can be used
300 to clean up dead stmts. Returns true if cleanup-cfg has to run. */
303 remove_prop_source_from_use (tree name)
305 gimple_stmt_iterator gsi;
307 bool cfg_changed = false;
312 if (!has_zero_uses (name))
315 stmt = SSA_NAME_DEF_STMT (name);
316 gsi = gsi_for_stmt (stmt);
317 bb = gimple_bb (stmt);
319 gsi_remove (&gsi, true);
320 cfg_changed |= gimple_purge_dead_eh_edges (bb);
322 name = (gimple_assign_copy_p (stmt)) ? gimple_assign_rhs1 (stmt) : NULL;
323 } while (name && TREE_CODE (name) == SSA_NAME);
328 /* Return the rhs of a gimple_assign STMT in a form of a single tree,
329 converted to type TYPE.
331 This should disappear, but is needed so we can combine expressions and use
332 the fold() interfaces. Long term, we need to develop folding and combine
333 routines that deal with gimple exclusively . */
336 rhs_to_tree (tree type, gimple stmt)
338 location_t loc = gimple_location (stmt);
339 enum tree_code code = gimple_assign_rhs_code (stmt);
340 if (get_gimple_rhs_class (code) == GIMPLE_TERNARY_RHS)
341 return fold_build3_loc (loc, code, type, gimple_assign_rhs1 (stmt),
342 gimple_assign_rhs2 (stmt),
343 gimple_assign_rhs3 (stmt));
344 else if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
345 return fold_build2_loc (loc, code, type, gimple_assign_rhs1 (stmt),
346 gimple_assign_rhs2 (stmt));
347 else if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
348 return build1 (code, type, gimple_assign_rhs1 (stmt));
349 else if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
350 return gimple_assign_rhs1 (stmt);
355 /* Combine OP0 CODE OP1 in the context of a COND_EXPR. Returns
356 the folded result in a form suitable for COND_EXPR_COND or
357 NULL_TREE, if there is no suitable simplified form. If
358 INVARIANT_ONLY is true only gimple_min_invariant results are
359 considered simplified. */
362 combine_cond_expr_cond (location_t loc, enum tree_code code, tree type,
363 tree op0, tree op1, bool invariant_only)
367 gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
369 t = fold_binary_loc (loc, code, type, op0, op1);
373 /* Require that we got a boolean type out if we put one in. */
374 gcc_assert (TREE_CODE (TREE_TYPE (t)) == TREE_CODE (type));
376 /* Canonicalize the combined condition for use in a COND_EXPR. */
377 t = canonicalize_cond_expr_cond (t);
379 /* Bail out if we required an invariant but didn't get one. */
380 if (!t || (invariant_only && !is_gimple_min_invariant (t)))
386 /* Combine the comparison OP0 CODE OP1 at LOC with the defining statements
387 of its operand. Return a new comparison tree or NULL_TREE if there
388 were no simplifying combines. */
391 forward_propagate_into_comparison_1 (location_t loc,
392 enum tree_code code, tree type,
395 tree tmp = NULL_TREE;
396 tree rhs0 = NULL_TREE, rhs1 = NULL_TREE;
397 bool single_use0_p = false, single_use1_p = false;
399 /* For comparisons use the first operand, that is likely to
400 simplify comparisons against constants. */
401 if (TREE_CODE (op0) == SSA_NAME)
403 gimple def_stmt = get_prop_source_stmt (op0, false, &single_use0_p);
404 if (def_stmt && can_propagate_from (def_stmt))
406 rhs0 = rhs_to_tree (TREE_TYPE (op1), def_stmt);
407 tmp = combine_cond_expr_cond (loc, code, type,
408 rhs0, op1, !single_use0_p);
414 /* If that wasn't successful, try the second operand. */
415 if (TREE_CODE (op1) == SSA_NAME)
417 gimple def_stmt = get_prop_source_stmt (op1, false, &single_use1_p);
418 if (def_stmt && can_propagate_from (def_stmt))
420 rhs1 = rhs_to_tree (TREE_TYPE (op0), def_stmt);
421 tmp = combine_cond_expr_cond (loc, code, type,
422 op0, rhs1, !single_use1_p);
428 /* If that wasn't successful either, try both operands. */
429 if (rhs0 != NULL_TREE
430 && rhs1 != NULL_TREE)
431 tmp = combine_cond_expr_cond (loc, code, type,
433 !(single_use0_p && single_use1_p));
438 /* Propagate from the ssa name definition statements of the assignment
439 from a comparison at *GSI into the conditional if that simplifies it.
440 Returns true if the stmt was modified, false if not. */
443 forward_propagate_into_comparison (gimple_stmt_iterator *gsi)
445 gimple stmt = gsi_stmt (*gsi);
448 /* Combine the comparison with defining statements. */
449 tmp = forward_propagate_into_comparison_1 (gimple_location (stmt),
450 gimple_assign_rhs_code (stmt),
452 (gimple_assign_lhs (stmt)),
453 gimple_assign_rhs1 (stmt),
454 gimple_assign_rhs2 (stmt));
457 gimple_assign_set_rhs_from_tree (gsi, tmp);
465 /* Propagate from the ssa name definition statements of COND_EXPR
466 in GIMPLE_COND statement STMT into the conditional if that simplifies it.
467 Returns zero if no statement was changed, one if there were
468 changes and two if cfg_cleanup needs to run.
470 This must be kept in sync with forward_propagate_into_cond. */
473 forward_propagate_into_gimple_cond (gimple stmt)
475 int did_something = 0;
476 location_t loc = gimple_location (stmt);
478 enum tree_code code = gimple_cond_code (stmt);
480 /* We can do tree combining on SSA_NAME and comparison expressions. */
481 if (TREE_CODE_CLASS (gimple_cond_code (stmt)) != tcc_comparison)
484 tmp = forward_propagate_into_comparison_1 (loc, code,
486 gimple_cond_lhs (stmt),
487 gimple_cond_rhs (stmt));
490 if (dump_file && tmp)
492 tree cond = build2 (gimple_cond_code (stmt),
494 gimple_cond_lhs (stmt),
495 gimple_cond_rhs (stmt));
496 fprintf (dump_file, " Replaced '");
497 print_generic_expr (dump_file, cond, 0);
498 fprintf (dump_file, "' with '");
499 print_generic_expr (dump_file, tmp, 0);
500 fprintf (dump_file, "'\n");
503 gimple_cond_set_condition_from_tree (stmt, unshare_expr (tmp));
506 /* Remove defining statements. */
507 if (is_gimple_min_invariant (tmp))
509 else if (did_something == 0)
513 return did_something;
517 /* Propagate from the ssa name definition statements of COND_EXPR
518 in the rhs of statement STMT into the conditional if that simplifies it.
519 Returns zero if no statement was changed, one if there were
520 changes and two if cfg_cleanup needs to run.
522 This must be kept in sync with forward_propagate_into_gimple_cond. */
525 forward_propagate_into_cond (gimple_stmt_iterator *gsi_p)
527 gimple stmt = gsi_stmt (*gsi_p);
528 location_t loc = gimple_location (stmt);
529 int did_something = 0;
530 tree tmp = NULL_TREE;
531 tree cond = gimple_assign_rhs1 (stmt);
533 /* We can do tree combining on SSA_NAME and comparison expressions. */
534 if (COMPARISON_CLASS_P (cond))
535 tmp = forward_propagate_into_comparison_1 (loc, TREE_CODE (cond),
537 TREE_OPERAND (cond, 0),
538 TREE_OPERAND (cond, 1));
539 else if (TREE_CODE (cond) == SSA_NAME)
541 tree name = cond, rhs0;
542 gimple def_stmt = get_prop_source_stmt (name, true, NULL);
543 if (!def_stmt || !can_propagate_from (def_stmt))
544 return did_something;
546 rhs0 = gimple_assign_rhs1 (def_stmt);
547 tmp = combine_cond_expr_cond (loc, NE_EXPR, boolean_type_node, rhs0,
548 build_int_cst (TREE_TYPE (rhs0), 0),
554 if (dump_file && tmp)
556 fprintf (dump_file, " Replaced '");
557 print_generic_expr (dump_file, cond, 0);
558 fprintf (dump_file, "' with '");
559 print_generic_expr (dump_file, tmp, 0);
560 fprintf (dump_file, "'\n");
563 gimple_assign_set_rhs_from_tree (gsi_p, unshare_expr (tmp));
564 stmt = gsi_stmt (*gsi_p);
567 /* Remove defining statements. */
568 if (is_gimple_min_invariant (tmp))
570 else if (did_something == 0)
574 return did_something;
577 /* We've just substituted an ADDR_EXPR into stmt. Update all the
578 relevant data structures to match. */
581 tidy_after_forward_propagate_addr (gimple stmt)
583 /* We may have turned a trapping insn into a non-trapping insn. */
584 if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
585 && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
588 if (TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR)
589 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt));
592 /* DEF_RHS contains the address of the 0th element in an array.
593 USE_STMT uses type of DEF_RHS to compute the address of an
594 arbitrary element within the array. The (variable) byte offset
595 of the element is contained in OFFSET.
597 We walk back through the use-def chains of OFFSET to verify that
598 it is indeed computing the offset of an element within the array
599 and extract the index corresponding to the given byte offset.
601 We then try to fold the entire address expression into a form
604 If we are successful, we replace the right hand side of USE_STMT
605 with the new address computation. */
608 forward_propagate_addr_into_variable_array_index (tree offset,
610 gimple_stmt_iterator *use_stmt_gsi)
613 gimple offset_def, use_stmt = gsi_stmt (*use_stmt_gsi);
616 if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == ARRAY_REF)
617 tunit = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (def_rhs)));
618 else if (TREE_CODE (TREE_TYPE (TREE_OPERAND (def_rhs, 0))) == ARRAY_TYPE)
619 tunit = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (TREE_TYPE (def_rhs))));
622 if (!host_integerp (tunit, 1))
625 /* Get the offset's defining statement. */
626 offset_def = SSA_NAME_DEF_STMT (offset);
628 /* Try to find an expression for a proper index. This is either a
629 multiplication expression by the element size or just the ssa name we came
630 along in case the element size is one. In that case, however, we do not
631 allow multiplications because they can be computing index to a higher
632 level dimension (PR 37861). */
633 if (integer_onep (tunit))
635 if (is_gimple_assign (offset_def)
636 && gimple_assign_rhs_code (offset_def) == MULT_EXPR)
643 /* The statement which defines OFFSET before type conversion
644 must be a simple GIMPLE_ASSIGN. */
645 if (!is_gimple_assign (offset_def))
648 /* The RHS of the statement which defines OFFSET must be a
649 multiplication of an object by the size of the array elements.
650 This implicitly verifies that the size of the array elements
652 if (gimple_assign_rhs_code (offset_def) == MULT_EXPR
653 && TREE_CODE (gimple_assign_rhs2 (offset_def)) == INTEGER_CST
654 && tree_int_cst_equal (gimple_assign_rhs2 (offset_def), tunit))
656 /* The first operand to the MULT_EXPR is the desired index. */
657 index = gimple_assign_rhs1 (offset_def);
659 /* If we have idx * tunit + CST * tunit re-associate that. */
660 else if ((gimple_assign_rhs_code (offset_def) == PLUS_EXPR
661 || gimple_assign_rhs_code (offset_def) == MINUS_EXPR)
662 && TREE_CODE (gimple_assign_rhs1 (offset_def)) == SSA_NAME
663 && TREE_CODE (gimple_assign_rhs2 (offset_def)) == INTEGER_CST
664 && (tmp = div_if_zero_remainder (EXACT_DIV_EXPR,
665 gimple_assign_rhs2 (offset_def),
666 tunit)) != NULL_TREE)
668 gimple offset_def2 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (offset_def));
669 if (is_gimple_assign (offset_def2)
670 && gimple_assign_rhs_code (offset_def2) == MULT_EXPR
671 && TREE_CODE (gimple_assign_rhs2 (offset_def2)) == INTEGER_CST
672 && tree_int_cst_equal (gimple_assign_rhs2 (offset_def2), tunit))
674 index = fold_build2 (gimple_assign_rhs_code (offset_def),
676 gimple_assign_rhs1 (offset_def2), tmp);
685 /* Replace the pointer addition with array indexing. */
686 index = force_gimple_operand_gsi (use_stmt_gsi, index, true, NULL_TREE,
687 true, GSI_SAME_STMT);
688 if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == ARRAY_REF)
690 new_rhs = unshare_expr (def_rhs);
691 TREE_OPERAND (TREE_OPERAND (new_rhs, 0), 1) = index;
695 new_rhs = build4 (ARRAY_REF, TREE_TYPE (TREE_TYPE (TREE_TYPE (def_rhs))),
696 unshare_expr (TREE_OPERAND (def_rhs, 0)),
697 index, integer_zero_node, NULL_TREE);
698 new_rhs = build_fold_addr_expr (new_rhs);
699 if (!useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (use_stmt)),
700 TREE_TYPE (new_rhs)))
702 new_rhs = force_gimple_operand_gsi (use_stmt_gsi, new_rhs, true,
703 NULL_TREE, true, GSI_SAME_STMT);
704 new_rhs = fold_convert (TREE_TYPE (gimple_assign_lhs (use_stmt)),
708 gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs);
709 use_stmt = gsi_stmt (*use_stmt_gsi);
711 /* That should have created gimple, so there is no need to
712 record information to undo the propagation. */
713 fold_stmt_inplace (use_stmt);
714 tidy_after_forward_propagate_addr (use_stmt);
718 /* NAME is a SSA_NAME representing DEF_RHS which is of the form
719 ADDR_EXPR <whatever>.
721 Try to forward propagate the ADDR_EXPR into the use USE_STMT.
722 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
723 node or for recovery of array indexing from pointer arithmetic.
725 Return true if the propagation was successful (the propagation can
726 be not totally successful, yet things may have been changed). */
729 forward_propagate_addr_expr_1 (tree name, tree def_rhs,
730 gimple_stmt_iterator *use_stmt_gsi,
733 tree lhs, rhs, rhs2, array_ref;
734 gimple use_stmt = gsi_stmt (*use_stmt_gsi);
735 enum tree_code rhs_code;
738 gcc_assert (TREE_CODE (def_rhs) == ADDR_EXPR);
740 lhs = gimple_assign_lhs (use_stmt);
741 rhs_code = gimple_assign_rhs_code (use_stmt);
742 rhs = gimple_assign_rhs1 (use_stmt);
744 /* Trivial cases. The use statement could be a trivial copy or a
745 useless conversion. Recurse to the uses of the lhs as copyprop does
746 not copy through different variant pointers and FRE does not catch
747 all useless conversions. Treat the case of a single-use name and
748 a conversion to def_rhs type separate, though. */
749 if (TREE_CODE (lhs) == SSA_NAME
750 && ((rhs_code == SSA_NAME && rhs == name)
751 || CONVERT_EXPR_CODE_P (rhs_code)))
753 /* Only recurse if we don't deal with a single use or we cannot
754 do the propagation to the current statement. In particular
755 we can end up with a conversion needed for a non-invariant
756 address which we cannot do in a single statement. */
758 || (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs))
759 && (!is_gimple_min_invariant (def_rhs)
760 || (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
761 && POINTER_TYPE_P (TREE_TYPE (def_rhs))
762 && (TYPE_PRECISION (TREE_TYPE (lhs))
763 > TYPE_PRECISION (TREE_TYPE (def_rhs)))))))
764 return forward_propagate_addr_expr (lhs, def_rhs);
766 gimple_assign_set_rhs1 (use_stmt, unshare_expr (def_rhs));
767 if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
768 gimple_assign_set_rhs_code (use_stmt, TREE_CODE (def_rhs));
770 gimple_assign_set_rhs_code (use_stmt, NOP_EXPR);
774 /* Propagate through constant pointer adjustments. */
775 if (TREE_CODE (lhs) == SSA_NAME
776 && rhs_code == POINTER_PLUS_EXPR
778 && TREE_CODE (gimple_assign_rhs2 (use_stmt)) == INTEGER_CST)
781 /* As we come here with non-invariant addresses in def_rhs we need
782 to make sure we can build a valid constant offsetted address
783 for further propagation. Simply rely on fold building that
784 and check after the fact. */
785 new_def_rhs = fold_build2 (MEM_REF, TREE_TYPE (TREE_TYPE (rhs)),
787 fold_convert (ptr_type_node,
788 gimple_assign_rhs2 (use_stmt)));
789 if (TREE_CODE (new_def_rhs) == MEM_REF
790 && !is_gimple_mem_ref_addr (TREE_OPERAND (new_def_rhs, 0)))
792 new_def_rhs = build_fold_addr_expr_with_type (new_def_rhs,
795 /* Recurse. If we could propagate into all uses of lhs do not
796 bother to replace into the current use but just pretend we did. */
797 if (TREE_CODE (new_def_rhs) == ADDR_EXPR
798 && forward_propagate_addr_expr (lhs, new_def_rhs))
801 if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (new_def_rhs)))
802 gimple_assign_set_rhs_with_ops (use_stmt_gsi, TREE_CODE (new_def_rhs),
803 new_def_rhs, NULL_TREE);
804 else if (is_gimple_min_invariant (new_def_rhs))
805 gimple_assign_set_rhs_with_ops (use_stmt_gsi, NOP_EXPR,
806 new_def_rhs, NULL_TREE);
809 gcc_assert (gsi_stmt (*use_stmt_gsi) == use_stmt);
810 update_stmt (use_stmt);
814 /* Now strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
815 ADDR_EXPR will not appear on the LHS. */
816 lhs = gimple_assign_lhs (use_stmt);
817 while (handled_component_p (lhs))
818 lhs = TREE_OPERAND (lhs, 0);
820 /* Now see if the LHS node is a MEM_REF using NAME. If so,
821 propagate the ADDR_EXPR into the use of NAME and fold the result. */
822 if (TREE_CODE (lhs) == MEM_REF
823 && TREE_OPERAND (lhs, 0) == name)
826 HOST_WIDE_INT def_rhs_offset;
827 /* If the address is invariant we can always fold it. */
828 if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0),
831 double_int off = mem_ref_offset (lhs);
833 off = double_int_add (off,
834 shwi_to_double_int (def_rhs_offset));
835 if (TREE_CODE (def_rhs_base) == MEM_REF)
837 off = double_int_add (off, mem_ref_offset (def_rhs_base));
838 new_ptr = TREE_OPERAND (def_rhs_base, 0);
841 new_ptr = build_fold_addr_expr (def_rhs_base);
842 TREE_OPERAND (lhs, 0) = new_ptr;
843 TREE_OPERAND (lhs, 1)
844 = double_int_to_tree (TREE_TYPE (TREE_OPERAND (lhs, 1)), off);
845 tidy_after_forward_propagate_addr (use_stmt);
846 /* Continue propagating into the RHS if this was not the only use. */
850 /* If the LHS is a plain dereference and the value type is the same as
851 that of the pointed-to type of the address we can put the
852 dereferenced address on the LHS preserving the original alias-type. */
853 else if (gimple_assign_lhs (use_stmt) == lhs
854 && useless_type_conversion_p
855 (TREE_TYPE (TREE_OPERAND (def_rhs, 0)),
856 TREE_TYPE (gimple_assign_rhs1 (use_stmt))))
858 tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0);
859 tree new_offset, new_base, saved;
860 while (handled_component_p (*def_rhs_basep))
861 def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0);
862 saved = *def_rhs_basep;
863 if (TREE_CODE (*def_rhs_basep) == MEM_REF)
865 new_base = TREE_OPERAND (*def_rhs_basep, 0);
867 = int_const_binop (PLUS_EXPR, TREE_OPERAND (lhs, 1),
868 TREE_OPERAND (*def_rhs_basep, 1));
872 new_base = build_fold_addr_expr (*def_rhs_basep);
873 new_offset = TREE_OPERAND (lhs, 1);
875 *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep),
876 new_base, new_offset);
877 gimple_assign_set_lhs (use_stmt,
878 unshare_expr (TREE_OPERAND (def_rhs, 0)));
879 *def_rhs_basep = saved;
880 tidy_after_forward_propagate_addr (use_stmt);
881 /* Continue propagating into the RHS if this was not the
887 /* We can have a struct assignment dereferencing our name twice.
888 Note that we didn't propagate into the lhs to not falsely
889 claim we did when propagating into the rhs. */
893 /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
894 nodes from the RHS. */
895 rhs = gimple_assign_rhs1 (use_stmt);
896 if (TREE_CODE (rhs) == ADDR_EXPR)
897 rhs = TREE_OPERAND (rhs, 0);
898 while (handled_component_p (rhs))
899 rhs = TREE_OPERAND (rhs, 0);
901 /* Now see if the RHS node is a MEM_REF using NAME. If so,
902 propagate the ADDR_EXPR into the use of NAME and fold the result. */
903 if (TREE_CODE (rhs) == MEM_REF
904 && TREE_OPERAND (rhs, 0) == name)
907 HOST_WIDE_INT def_rhs_offset;
908 if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0),
911 double_int off = mem_ref_offset (rhs);
913 off = double_int_add (off,
914 shwi_to_double_int (def_rhs_offset));
915 if (TREE_CODE (def_rhs_base) == MEM_REF)
917 off = double_int_add (off, mem_ref_offset (def_rhs_base));
918 new_ptr = TREE_OPERAND (def_rhs_base, 0);
921 new_ptr = build_fold_addr_expr (def_rhs_base);
922 TREE_OPERAND (rhs, 0) = new_ptr;
923 TREE_OPERAND (rhs, 1)
924 = double_int_to_tree (TREE_TYPE (TREE_OPERAND (rhs, 1)), off);
925 fold_stmt_inplace (use_stmt);
926 tidy_after_forward_propagate_addr (use_stmt);
929 /* If the LHS is a plain dereference and the value type is the same as
930 that of the pointed-to type of the address we can put the
931 dereferenced address on the LHS preserving the original alias-type. */
932 else if (gimple_assign_rhs1 (use_stmt) == rhs
933 && useless_type_conversion_p
934 (TREE_TYPE (gimple_assign_lhs (use_stmt)),
935 TREE_TYPE (TREE_OPERAND (def_rhs, 0))))
937 tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0);
938 tree new_offset, new_base, saved;
939 while (handled_component_p (*def_rhs_basep))
940 def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0);
941 saved = *def_rhs_basep;
942 if (TREE_CODE (*def_rhs_basep) == MEM_REF)
944 new_base = TREE_OPERAND (*def_rhs_basep, 0);
946 = int_const_binop (PLUS_EXPR, TREE_OPERAND (rhs, 1),
947 TREE_OPERAND (*def_rhs_basep, 1));
951 new_base = build_fold_addr_expr (*def_rhs_basep);
952 new_offset = TREE_OPERAND (rhs, 1);
954 *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep),
955 new_base, new_offset);
956 gimple_assign_set_rhs1 (use_stmt,
957 unshare_expr (TREE_OPERAND (def_rhs, 0)));
958 *def_rhs_basep = saved;
959 fold_stmt_inplace (use_stmt);
960 tidy_after_forward_propagate_addr (use_stmt);
965 /* If the use of the ADDR_EXPR is not a POINTER_PLUS_EXPR, there
967 if (gimple_assign_rhs_code (use_stmt) != POINTER_PLUS_EXPR
968 || gimple_assign_rhs1 (use_stmt) != name)
971 /* The remaining cases are all for turning pointer arithmetic into
972 array indexing. They only apply when we have the address of
973 element zero in an array. If that is not the case then there
975 array_ref = TREE_OPERAND (def_rhs, 0);
976 if ((TREE_CODE (array_ref) != ARRAY_REF
977 || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE
978 || TREE_CODE (TREE_OPERAND (array_ref, 1)) != INTEGER_CST)
979 && TREE_CODE (TREE_TYPE (array_ref)) != ARRAY_TYPE)
982 rhs2 = gimple_assign_rhs2 (use_stmt);
983 /* Try to optimize &x[C1] p+ C2 where C2 is a multiple of the size
984 of the elements in X into &x[C1 + C2/element size]. */
985 if (TREE_CODE (rhs2) == INTEGER_CST)
987 tree new_rhs = maybe_fold_stmt_addition (gimple_location (use_stmt),
992 tree type = TREE_TYPE (gimple_assign_lhs (use_stmt));
993 new_rhs = unshare_expr (new_rhs);
994 if (!useless_type_conversion_p (type, TREE_TYPE (new_rhs)))
996 if (!is_gimple_min_invariant (new_rhs))
997 new_rhs = force_gimple_operand_gsi (use_stmt_gsi, new_rhs,
999 true, GSI_SAME_STMT);
1000 new_rhs = fold_convert (type, new_rhs);
1002 gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs);
1003 use_stmt = gsi_stmt (*use_stmt_gsi);
1004 update_stmt (use_stmt);
1005 tidy_after_forward_propagate_addr (use_stmt);
1010 /* Try to optimize &x[0] p+ OFFSET where OFFSET is defined by
1011 converting a multiplication of an index by the size of the
1012 array elements, then the result is converted into the proper
1013 type for the arithmetic. */
1014 if (TREE_CODE (rhs2) == SSA_NAME
1015 && (TREE_CODE (array_ref) != ARRAY_REF
1016 || integer_zerop (TREE_OPERAND (array_ref, 1)))
1017 && useless_type_conversion_p (TREE_TYPE (name), TREE_TYPE (def_rhs))
1018 /* Avoid problems with IVopts creating PLUS_EXPRs with a
1019 different type than their operands. */
1020 && useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
1021 return forward_propagate_addr_into_variable_array_index (rhs2, def_rhs,
1026 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
1028 Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME.
1029 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
1030 node or for recovery of array indexing from pointer arithmetic.
1031 Returns true, if all uses have been propagated into. */
1034 forward_propagate_addr_expr (tree name, tree rhs)
1036 int stmt_loop_depth = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_depth;
1037 imm_use_iterator iter;
1040 bool single_use_p = has_single_use (name);
1042 FOR_EACH_IMM_USE_STMT (use_stmt, iter, name)
1047 /* If the use is not in a simple assignment statement, then
1048 there is nothing we can do. */
1049 if (gimple_code (use_stmt) != GIMPLE_ASSIGN)
1051 if (!is_gimple_debug (use_stmt))
1056 /* If the use is in a deeper loop nest, then we do not want
1057 to propagate non-invariant ADDR_EXPRs into the loop as that
1058 is likely adding expression evaluations into the loop. */
1059 if (gimple_bb (use_stmt)->loop_depth > stmt_loop_depth
1060 && !is_gimple_min_invariant (rhs))
1067 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1068 result = forward_propagate_addr_expr_1 (name, rhs, &gsi,
1070 /* If the use has moved to a different statement adjust
1071 the update machinery for the old statement too. */
1072 if (use_stmt != gsi_stmt (gsi))
1074 update_stmt (use_stmt);
1075 use_stmt = gsi_stmt (gsi);
1078 update_stmt (use_stmt);
1082 /* Remove intermediate now unused copy and conversion chains. */
1083 use_rhs = gimple_assign_rhs1 (use_stmt);
1085 && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
1086 && TREE_CODE (use_rhs) == SSA_NAME
1087 && has_zero_uses (gimple_assign_lhs (use_stmt)))
1089 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1090 release_defs (use_stmt);
1091 gsi_remove (&gsi, true);
1095 return all && has_zero_uses (name);
1099 /* Forward propagate the comparison defined in STMT like
1100 cond_1 = x CMP y to uses of the form
1104 Returns true if stmt is now unused. */
1107 forward_propagate_comparison (gimple stmt)
1109 tree name = gimple_assign_lhs (stmt);
1111 tree tmp = NULL_TREE;
1113 /* Don't propagate ssa names that occur in abnormal phis. */
1114 if ((TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
1115 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)))
1116 || (TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME
1117 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs2 (stmt))))
1120 /* Do not un-cse comparisons. But propagate through copies. */
1121 use_stmt = get_prop_dest_stmt (name, &name);
1125 /* Conversion of the condition result to another integral type. */
1126 if (is_gimple_assign (use_stmt)
1127 && (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt))
1128 || TREE_CODE_CLASS (gimple_assign_rhs_code (use_stmt))
1130 || gimple_assign_rhs_code (use_stmt) == BIT_NOT_EXPR
1131 || gimple_assign_rhs_code (use_stmt) == BIT_XOR_EXPR)
1132 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (use_stmt))))
1134 tree lhs = gimple_assign_lhs (use_stmt);
1136 /* We can propagate the condition into a conversion. */
1137 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt)))
1139 /* Avoid using fold here as that may create a COND_EXPR with
1140 non-boolean condition as canonical form. */
1141 tmp = build2 (gimple_assign_rhs_code (stmt), TREE_TYPE (lhs),
1142 gimple_assign_rhs1 (stmt), gimple_assign_rhs2 (stmt));
1144 /* We can propagate the condition into X op CST where op
1145 is EQ_EXPR or NE_EXPR and CST is either one or zero. */
1146 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (use_stmt))
1148 && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == SSA_NAME
1149 && TREE_CODE (gimple_assign_rhs2 (use_stmt)) == INTEGER_CST)
1151 enum tree_code code = gimple_assign_rhs_code (use_stmt);
1152 tree cst = gimple_assign_rhs2 (use_stmt);
1155 cond = build2 (gimple_assign_rhs_code (stmt),
1157 gimple_assign_rhs1 (stmt),
1158 gimple_assign_rhs2 (stmt));
1160 tmp = combine_cond_expr_cond (gimple_location (use_stmt),
1161 code, TREE_TYPE (lhs),
1163 if (tmp == NULL_TREE)
1166 /* We can propagate the condition into a statement that
1167 computes the logical negation of the comparison result. */
1168 else if ((gimple_assign_rhs_code (use_stmt) == BIT_NOT_EXPR
1169 && TYPE_PRECISION (TREE_TYPE (lhs)) == 1)
1170 || (gimple_assign_rhs_code (use_stmt) == BIT_XOR_EXPR
1171 && integer_onep (gimple_assign_rhs2 (use_stmt))))
1173 tree type = TREE_TYPE (gimple_assign_rhs1 (stmt));
1174 bool nans = HONOR_NANS (TYPE_MODE (type));
1175 enum tree_code code;
1176 code = invert_tree_comparison (gimple_assign_rhs_code (stmt), nans);
1177 if (code == ERROR_MARK)
1180 tmp = build2 (code, TREE_TYPE (lhs), gimple_assign_rhs1 (stmt),
1181 gimple_assign_rhs2 (stmt));
1187 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1188 gimple_assign_set_rhs_from_tree (&gsi, unshare_expr (tmp));
1189 use_stmt = gsi_stmt (gsi);
1190 update_stmt (use_stmt);
1193 if (dump_file && (dump_flags & TDF_DETAILS))
1195 tree old_rhs = rhs_to_tree (TREE_TYPE (gimple_assign_lhs (stmt)),
1197 fprintf (dump_file, " Replaced '");
1198 print_generic_expr (dump_file, old_rhs, dump_flags);
1199 fprintf (dump_file, "' with '");
1200 print_generic_expr (dump_file, tmp, dump_flags);
1201 fprintf (dump_file, "'\n");
1204 /* Remove defining statements. */
1205 return remove_prop_source_from_use (name);
1212 /* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y.
1213 If so, we can change STMT into lhs = y which can later be copy
1214 propagated. Similarly for negation.
1216 This could trivially be formulated as a forward propagation
1217 to immediate uses. However, we already had an implementation
1218 from DOM which used backward propagation via the use-def links.
1220 It turns out that backward propagation is actually faster as
1221 there's less work to do for each NOT/NEG expression we find.
1222 Backwards propagation needs to look at the statement in a single
1223 backlink. Forward propagation needs to look at potentially more
1224 than one forward link.
1226 Returns true when the statement was changed. */
1229 simplify_not_neg_expr (gimple_stmt_iterator *gsi_p)
1231 gimple stmt = gsi_stmt (*gsi_p);
1232 tree rhs = gimple_assign_rhs1 (stmt);
1233 gimple rhs_def_stmt = SSA_NAME_DEF_STMT (rhs);
1235 /* See if the RHS_DEF_STMT has the same form as our statement. */
1236 if (is_gimple_assign (rhs_def_stmt)
1237 && gimple_assign_rhs_code (rhs_def_stmt) == gimple_assign_rhs_code (stmt))
1239 tree rhs_def_operand = gimple_assign_rhs1 (rhs_def_stmt);
1241 /* Verify that RHS_DEF_OPERAND is a suitable SSA_NAME. */
1242 if (TREE_CODE (rhs_def_operand) == SSA_NAME
1243 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand))
1245 gimple_assign_set_rhs_from_tree (gsi_p, rhs_def_operand);
1246 stmt = gsi_stmt (*gsi_p);
1255 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
1256 the condition which we may be able to optimize better. */
1259 simplify_gimple_switch (gimple stmt)
1261 tree cond = gimple_switch_index (stmt);
1265 /* The optimization that we really care about is removing unnecessary
1266 casts. That will let us do much better in propagating the inferred
1267 constant at the switch target. */
1268 if (TREE_CODE (cond) == SSA_NAME)
1270 def_stmt = SSA_NAME_DEF_STMT (cond);
1271 if (is_gimple_assign (def_stmt))
1273 if (gimple_assign_rhs_code (def_stmt) == NOP_EXPR)
1278 def = gimple_assign_rhs1 (def_stmt);
1280 /* ??? Why was Jeff testing this? We are gimple... */
1281 gcc_checking_assert (is_gimple_val (def));
1283 to = TREE_TYPE (cond);
1284 ti = TREE_TYPE (def);
1286 /* If we have an extension that preserves value, then we
1287 can copy the source value into the switch. */
1289 need_precision = TYPE_PRECISION (ti);
1291 if (! INTEGRAL_TYPE_P (ti))
1293 else if (TYPE_UNSIGNED (to) && !TYPE_UNSIGNED (ti))
1295 else if (!TYPE_UNSIGNED (to) && TYPE_UNSIGNED (ti))
1296 need_precision += 1;
1297 if (TYPE_PRECISION (to) < need_precision)
1302 gimple_switch_set_index (stmt, def);
1313 /* For pointers p2 and p1 return p2 - p1 if the
1314 difference is known and constant, otherwise return NULL. */
1317 constant_pointer_difference (tree p1, tree p2)
1320 #define CPD_ITERATIONS 5
1321 tree exps[2][CPD_ITERATIONS];
1322 tree offs[2][CPD_ITERATIONS];
1325 for (i = 0; i < 2; i++)
1327 tree p = i ? p1 : p2;
1328 tree off = size_zero_node;
1330 enum tree_code code;
1332 /* For each of p1 and p2 we need to iterate at least
1333 twice, to handle ADDR_EXPR directly in p1/p2,
1334 SSA_NAME with ADDR_EXPR or POINTER_PLUS_EXPR etc.
1335 on definition's stmt RHS. Iterate a few extra times. */
1339 if (!POINTER_TYPE_P (TREE_TYPE (p)))
1341 if (TREE_CODE (p) == ADDR_EXPR)
1343 tree q = TREE_OPERAND (p, 0);
1344 HOST_WIDE_INT offset;
1345 tree base = get_addr_base_and_unit_offset (q, &offset);
1350 off = size_binop (PLUS_EXPR, off, size_int (offset));
1352 if (TREE_CODE (q) == MEM_REF
1353 && TREE_CODE (TREE_OPERAND (q, 0)) == SSA_NAME)
1355 p = TREE_OPERAND (q, 0);
1356 off = size_binop (PLUS_EXPR, off,
1357 double_int_to_tree (sizetype,
1358 mem_ref_offset (q)));
1367 if (TREE_CODE (p) != SSA_NAME)
1371 if (j == CPD_ITERATIONS)
1373 stmt = SSA_NAME_DEF_STMT (p);
1374 if (!is_gimple_assign (stmt) || gimple_assign_lhs (stmt) != p)
1376 code = gimple_assign_rhs_code (stmt);
1377 if (code == POINTER_PLUS_EXPR)
1379 if (TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST)
1381 off = size_binop (PLUS_EXPR, off, gimple_assign_rhs2 (stmt));
1382 p = gimple_assign_rhs1 (stmt);
1384 else if (code == ADDR_EXPR || code == NOP_EXPR)
1385 p = gimple_assign_rhs1 (stmt);
1393 for (i = 0; i < cnt[0]; i++)
1394 for (j = 0; j < cnt[1]; j++)
1395 if (exps[0][i] == exps[1][j])
1396 return size_binop (MINUS_EXPR, offs[0][i], offs[1][j]);
1401 /* *GSI_P is a GIMPLE_CALL to a builtin function.
1403 memcpy (p, "abcd", 4);
1404 memset (p + 4, ' ', 3);
1406 memcpy (p, "abcd ", 7);
1407 call if the latter can be stored by pieces during expansion. */
1410 simplify_builtin_call (gimple_stmt_iterator *gsi_p, tree callee2)
1412 gimple stmt1, stmt2 = gsi_stmt (*gsi_p);
1413 tree vuse = gimple_vuse (stmt2);
1416 stmt1 = SSA_NAME_DEF_STMT (vuse);
1418 switch (DECL_FUNCTION_CODE (callee2))
1420 case BUILT_IN_MEMSET:
1421 if (gimple_call_num_args (stmt2) != 3
1422 || gimple_call_lhs (stmt2)
1424 || BITS_PER_UNIT != 8)
1429 tree ptr1, src1, str1, off1, len1, lhs1;
1430 tree ptr2 = gimple_call_arg (stmt2, 0);
1431 tree val2 = gimple_call_arg (stmt2, 1);
1432 tree len2 = gimple_call_arg (stmt2, 2);
1433 tree diff, vdef, new_str_cst;
1435 unsigned int ptr1_align;
1436 unsigned HOST_WIDE_INT src_len;
1438 use_operand_p use_p;
1440 if (!host_integerp (val2, 0)
1441 || !host_integerp (len2, 1))
1443 if (is_gimple_call (stmt1))
1445 /* If first stmt is a call, it needs to be memcpy
1446 or mempcpy, with string literal as second argument and
1448 callee1 = gimple_call_fndecl (stmt1);
1449 if (callee1 == NULL_TREE
1450 || DECL_BUILT_IN_CLASS (callee1) != BUILT_IN_NORMAL
1451 || gimple_call_num_args (stmt1) != 3)
1453 if (DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMCPY
1454 && DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMPCPY)
1456 ptr1 = gimple_call_arg (stmt1, 0);
1457 src1 = gimple_call_arg (stmt1, 1);
1458 len1 = gimple_call_arg (stmt1, 2);
1459 lhs1 = gimple_call_lhs (stmt1);
1460 if (!host_integerp (len1, 1))
1462 str1 = string_constant (src1, &off1);
1463 if (str1 == NULL_TREE)
1465 if (!host_integerp (off1, 1)
1466 || compare_tree_int (off1, TREE_STRING_LENGTH (str1) - 1) > 0
1467 || compare_tree_int (len1, TREE_STRING_LENGTH (str1)
1468 - tree_low_cst (off1, 1)) > 0
1469 || TREE_CODE (TREE_TYPE (str1)) != ARRAY_TYPE
1470 || TYPE_MODE (TREE_TYPE (TREE_TYPE (str1)))
1471 != TYPE_MODE (char_type_node))
1474 else if (gimple_assign_single_p (stmt1))
1476 /* Otherwise look for length 1 memcpy optimized into
1478 ptr1 = gimple_assign_lhs (stmt1);
1479 src1 = gimple_assign_rhs1 (stmt1);
1480 if (TREE_CODE (ptr1) != MEM_REF
1481 || TYPE_MODE (TREE_TYPE (ptr1)) != TYPE_MODE (char_type_node)
1482 || !host_integerp (src1, 0))
1484 ptr1 = build_fold_addr_expr (ptr1);
1485 callee1 = NULL_TREE;
1486 len1 = size_one_node;
1488 off1 = size_zero_node;
1494 diff = constant_pointer_difference (ptr1, ptr2);
1495 if (diff == NULL && lhs1 != NULL)
1497 diff = constant_pointer_difference (lhs1, ptr2);
1498 if (DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1500 diff = size_binop (PLUS_EXPR, diff,
1501 fold_convert (sizetype, len1));
1503 /* If the difference between the second and first destination pointer
1504 is not constant, or is bigger than memcpy length, bail out. */
1506 || !host_integerp (diff, 1)
1507 || tree_int_cst_lt (len1, diff))
1510 /* Use maximum of difference plus memset length and memcpy length
1511 as the new memcpy length, if it is too big, bail out. */
1512 src_len = tree_low_cst (diff, 1);
1513 src_len += tree_low_cst (len2, 1);
1514 if (src_len < (unsigned HOST_WIDE_INT) tree_low_cst (len1, 1))
1515 src_len = tree_low_cst (len1, 1);
1519 /* If mempcpy value is used elsewhere, bail out, as mempcpy
1520 with bigger length will return different result. */
1521 if (lhs1 != NULL_TREE
1522 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1523 && (TREE_CODE (lhs1) != SSA_NAME
1524 || !single_imm_use (lhs1, &use_p, &use_stmt)
1525 || use_stmt != stmt2))
1528 /* If anything reads memory in between memcpy and memset
1529 call, the modified memcpy call might change it. */
1530 vdef = gimple_vdef (stmt1);
1532 && (!single_imm_use (vdef, &use_p, &use_stmt)
1533 || use_stmt != stmt2))
1536 ptr1_align = get_pointer_alignment (ptr1, BIGGEST_ALIGNMENT);
1537 /* Construct the new source string literal. */
1538 src_buf = XALLOCAVEC (char, src_len + 1);
1541 TREE_STRING_POINTER (str1) + tree_low_cst (off1, 1),
1542 tree_low_cst (len1, 1));
1544 src_buf[0] = tree_low_cst (src1, 0);
1545 memset (src_buf + tree_low_cst (diff, 1),
1546 tree_low_cst (val2, 1), tree_low_cst (len2, 1));
1547 src_buf[src_len] = '\0';
1548 /* Neither builtin_strncpy_read_str nor builtin_memcpy_read_str
1549 handle embedded '\0's. */
1550 if (strlen (src_buf) != src_len)
1552 rtl_profile_for_bb (gimple_bb (stmt2));
1553 /* If the new memcpy wouldn't be emitted by storing the literal
1554 by pieces, this optimization might enlarge .rodata too much,
1555 as commonly used string literals couldn't be shared any
1557 if (!can_store_by_pieces (src_len,
1558 builtin_strncpy_read_str,
1559 src_buf, ptr1_align, false))
1562 new_str_cst = build_string_literal (src_len, src_buf);
1565 /* If STMT1 is a mem{,p}cpy call, adjust it and remove
1567 if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1568 gimple_call_set_lhs (stmt1, NULL_TREE);
1569 gimple_call_set_arg (stmt1, 1, new_str_cst);
1570 gimple_call_set_arg (stmt1, 2,
1571 build_int_cst (TREE_TYPE (len1), src_len));
1572 update_stmt (stmt1);
1573 unlink_stmt_vdef (stmt2);
1574 gsi_remove (gsi_p, true);
1575 release_defs (stmt2);
1576 if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1577 release_ssa_name (lhs1);
1582 /* Otherwise, if STMT1 is length 1 memcpy optimized into
1583 assignment, remove STMT1 and change memset call into
1585 gimple_stmt_iterator gsi = gsi_for_stmt (stmt1);
1587 if (!is_gimple_val (ptr1))
1588 ptr1 = force_gimple_operand_gsi (gsi_p, ptr1, true, NULL_TREE,
1589 true, GSI_SAME_STMT);
1590 gimple_call_set_fndecl (stmt2, built_in_decls [BUILT_IN_MEMCPY]);
1591 gimple_call_set_arg (stmt2, 0, ptr1);
1592 gimple_call_set_arg (stmt2, 1, new_str_cst);
1593 gimple_call_set_arg (stmt2, 2,
1594 build_int_cst (TREE_TYPE (len2), src_len));
1595 unlink_stmt_vdef (stmt1);
1596 gsi_remove (&gsi, true);
1597 release_defs (stmt1);
1598 update_stmt (stmt2);
1609 /* Checks if expression has type of one-bit precision, or is a known
1610 truth-valued expression. */
1612 truth_valued_ssa_name (tree name)
1615 tree type = TREE_TYPE (name);
1617 if (!INTEGRAL_TYPE_P (type))
1619 /* Don't check here for BOOLEAN_TYPE as the precision isn't
1620 necessarily one and so ~X is not equal to !X. */
1621 if (TYPE_PRECISION (type) == 1)
1623 def = SSA_NAME_DEF_STMT (name);
1624 if (is_gimple_assign (def))
1625 return truth_value_p (gimple_assign_rhs_code (def));
1629 /* Helper routine for simplify_bitwise_binary_1 function.
1630 Return for the SSA name NAME the expression X if it mets condition
1631 NAME = !X. Otherwise return NULL_TREE.
1632 Detected patterns for NAME = !X are:
1633 !X and X == 0 for X with integral type.
1634 X ^ 1, X != 1,or ~X for X with integral type with precision of one. */
1636 lookup_logical_inverted_value (tree name)
1639 enum tree_code code;
1642 /* If name has none-intergal type, or isn't a SSA_NAME, then
1644 if (TREE_CODE (name) != SSA_NAME
1645 || !INTEGRAL_TYPE_P (TREE_TYPE (name)))
1647 def = SSA_NAME_DEF_STMT (name);
1648 if (!is_gimple_assign (def))
1651 code = gimple_assign_rhs_code (def);
1652 op1 = gimple_assign_rhs1 (def);
1655 /* Get for EQ_EXPR or BIT_XOR_EXPR operation the second operand.
1656 If CODE isn't an EQ_EXPR, BIT_XOR_EXPR, TRUTH_NOT_EXPR,
1657 or BIT_NOT_EXPR, then return. */
1658 if (code == EQ_EXPR || code == NE_EXPR
1659 || code == BIT_XOR_EXPR)
1660 op2 = gimple_assign_rhs2 (def);
1664 case TRUTH_NOT_EXPR:
1667 if (truth_valued_ssa_name (name))
1671 /* Check if we have X == 0 and X has an integral type. */
1672 if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)))
1674 if (integer_zerop (op2))
1678 /* Check if we have X != 1 and X is a truth-valued. */
1679 if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)))
1681 if (integer_onep (op2) && truth_valued_ssa_name (op1))
1685 /* Check if we have X ^ 1 and X is truth valued. */
1686 if (integer_onep (op2) && truth_valued_ssa_name (op1))
1696 /* Optimize ARG1 CODE ARG2 to a constant for bitwise binary
1697 operations CODE, if one operand has the logically inverted
1698 value of the other. */
1700 simplify_bitwise_binary_1 (enum tree_code code, tree type,
1701 tree arg1, tree arg2)
1705 /* If CODE isn't a bitwise binary operation, return NULL_TREE. */
1706 if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR
1707 && code != BIT_XOR_EXPR)
1710 /* First check if operands ARG1 and ARG2 are equal. If so
1711 return NULL_TREE as this optimization is handled fold_stmt. */
1714 /* See if we have in arguments logical-not patterns. */
1715 if (((anot = lookup_logical_inverted_value (arg1)) == NULL_TREE
1717 && ((anot = lookup_logical_inverted_value (arg2)) == NULL_TREE
1722 if (code == BIT_AND_EXPR)
1723 return fold_convert (type, integer_zero_node);
1724 /* X | !X -> 1 and X ^ !X -> 1, if X is truth-valued. */
1725 if (truth_valued_ssa_name (anot))
1726 return fold_convert (type, integer_one_node);
1728 /* ??? Otherwise result is (X != 0 ? X : 1). not handled. */
1732 /* Simplify bitwise binary operations.
1733 Return true if a transformation applied, otherwise return false. */
1736 simplify_bitwise_binary (gimple_stmt_iterator *gsi)
1738 gimple stmt = gsi_stmt (*gsi);
1739 tree arg1 = gimple_assign_rhs1 (stmt);
1740 tree arg2 = gimple_assign_rhs2 (stmt);
1741 enum tree_code code = gimple_assign_rhs_code (stmt);
1743 gimple def1 = NULL, def2 = NULL;
1744 tree def1_arg1, def2_arg1;
1745 enum tree_code def1_code, def2_code;
1747 /* If the first argument is an SSA name that is itself a result of a
1748 typecast of an ADDR_EXPR to an integer, feed the ADDR_EXPR to the
1749 folder rather than the ssa name. */
1750 if (code == BIT_AND_EXPR
1751 && TREE_CODE (arg2) == INTEGER_CST
1752 && TREE_CODE (arg1) == SSA_NAME)
1754 gimple def = SSA_NAME_DEF_STMT (arg1);
1757 /* ??? This looks bogus - the conversion could be truncating. */
1758 if (is_gimple_assign (def)
1759 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def))
1760 && INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
1762 tree opp = gimple_assign_rhs1 (def);
1763 if (TREE_CODE (opp) == ADDR_EXPR)
1767 res = fold_binary_loc (gimple_location (stmt),
1768 BIT_AND_EXPR, TREE_TYPE (gimple_assign_lhs (stmt)),
1770 if (res && is_gimple_min_invariant (res))
1772 gimple_assign_set_rhs_from_tree (gsi, res);
1778 def1_code = TREE_CODE (arg1);
1780 if (TREE_CODE (arg1) == SSA_NAME)
1782 def1 = SSA_NAME_DEF_STMT (arg1);
1783 if (is_gimple_assign (def1))
1785 def1_code = gimple_assign_rhs_code (def1);
1786 def1_arg1 = gimple_assign_rhs1 (def1);
1790 def2_code = TREE_CODE (arg2);
1792 if (TREE_CODE (arg2) == SSA_NAME)
1794 def2 = SSA_NAME_DEF_STMT (arg2);
1795 if (is_gimple_assign (def2))
1797 def2_code = gimple_assign_rhs_code (def2);
1798 def2_arg1 = gimple_assign_rhs1 (def2);
1802 /* Try to fold (type) X op CST -> (type) (X op ((type-x) CST)). */
1803 if (TREE_CODE (arg2) == INTEGER_CST
1804 && CONVERT_EXPR_CODE_P (def1_code)
1805 && INTEGRAL_TYPE_P (TREE_TYPE (def1_arg1))
1806 && int_fits_type_p (arg2, TREE_TYPE (def1_arg1)))
1809 tree tem = create_tmp_reg (TREE_TYPE (def1_arg1), NULL);
1811 gimple_build_assign_with_ops (code, tem, def1_arg1,
1812 fold_convert_loc (gimple_location (stmt),
1813 TREE_TYPE (def1_arg1),
1815 tem = make_ssa_name (tem, newop);
1816 gimple_assign_set_lhs (newop, tem);
1817 gsi_insert_before (gsi, newop, GSI_SAME_STMT);
1818 gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
1819 tem, NULL_TREE, NULL_TREE);
1820 update_stmt (gsi_stmt (*gsi));
1824 /* For bitwise binary operations apply operand conversions to the
1825 binary operation result instead of to the operands. This allows
1826 to combine successive conversions and bitwise binary operations. */
1827 if (CONVERT_EXPR_CODE_P (def1_code)
1828 && CONVERT_EXPR_CODE_P (def2_code)
1829 && types_compatible_p (TREE_TYPE (def1_arg1), TREE_TYPE (def2_arg1))
1830 /* Make sure that the conversion widens the operands, or has same
1831 precision, or that it changes the operation to a bitfield
1833 && ((TYPE_PRECISION (TREE_TYPE (def1_arg1))
1834 <= TYPE_PRECISION (TREE_TYPE (arg1)))
1835 || (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (arg1)))
1837 || (TYPE_PRECISION (TREE_TYPE (arg1))
1838 != GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (arg1))))))
1841 tree tem = create_tmp_reg (TREE_TYPE (def1_arg1),
1843 newop = gimple_build_assign_with_ops (code, tem, def1_arg1, def2_arg1);
1844 tem = make_ssa_name (tem, newop);
1845 gimple_assign_set_lhs (newop, tem);
1846 gsi_insert_before (gsi, newop, GSI_SAME_STMT);
1847 gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
1848 tem, NULL_TREE, NULL_TREE);
1849 update_stmt (gsi_stmt (*gsi));
1853 /* (a | CST1) & CST2 -> (a & CST2) | (CST1 & CST2). */
1854 if (code == BIT_AND_EXPR
1855 && def1_code == BIT_IOR_EXPR
1856 && TREE_CODE (arg2) == INTEGER_CST
1857 && TREE_CODE (gimple_assign_rhs2 (def1)) == INTEGER_CST)
1859 tree cst = fold_build2 (BIT_AND_EXPR, TREE_TYPE (arg2),
1860 arg2, gimple_assign_rhs2 (def1));
1863 if (integer_zerop (cst))
1865 gimple_assign_set_rhs1 (stmt, def1_arg1);
1869 tem = create_tmp_reg (TREE_TYPE (arg2), NULL);
1870 newop = gimple_build_assign_with_ops (BIT_AND_EXPR,
1871 tem, def1_arg1, arg2);
1872 tem = make_ssa_name (tem, newop);
1873 gimple_assign_set_lhs (newop, tem);
1874 /* Make sure to re-process the new stmt as it's walking upwards. */
1875 gsi_insert_before (gsi, newop, GSI_NEW_STMT);
1876 gimple_assign_set_rhs1 (stmt, tem);
1877 gimple_assign_set_rhs2 (stmt, cst);
1878 gimple_assign_set_rhs_code (stmt, BIT_IOR_EXPR);
1883 /* Combine successive equal operations with constants. */
1884 if ((code == BIT_AND_EXPR
1885 || code == BIT_IOR_EXPR
1886 || code == BIT_XOR_EXPR)
1887 && def1_code == code
1888 && TREE_CODE (arg2) == INTEGER_CST
1889 && TREE_CODE (gimple_assign_rhs2 (def1)) == INTEGER_CST)
1891 tree cst = fold_build2 (code, TREE_TYPE (arg2),
1892 arg2, gimple_assign_rhs2 (def1));
1893 gimple_assign_set_rhs1 (stmt, def1_arg1);
1894 gimple_assign_set_rhs2 (stmt, cst);
1899 /* Try simple folding for X op !X, and X op X. */
1900 res = simplify_bitwise_binary_1 (code, TREE_TYPE (arg1), arg1, arg2);
1901 if (res != NULL_TREE)
1903 gimple_assign_set_rhs_from_tree (gsi, res);
1904 update_stmt (gsi_stmt (*gsi));
1912 /* Perform re-associations of the plus or minus statement STMT that are
1913 always permitted. Returns true if the CFG was changed. */
1916 associate_plusminus (gimple stmt)
1918 tree rhs1 = gimple_assign_rhs1 (stmt);
1919 tree rhs2 = gimple_assign_rhs2 (stmt);
1920 enum tree_code code = gimple_assign_rhs_code (stmt);
1921 gimple_stmt_iterator gsi;
1924 /* We can't reassociate at all for saturating types. */
1925 if (TYPE_SATURATING (TREE_TYPE (rhs1)))
1928 /* First contract negates. */
1933 /* A +- (-B) -> A -+ B. */
1934 if (TREE_CODE (rhs2) == SSA_NAME)
1936 gimple def_stmt = SSA_NAME_DEF_STMT (rhs2);
1937 if (is_gimple_assign (def_stmt)
1938 && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR
1939 && can_propagate_from (def_stmt))
1941 code = (code == MINUS_EXPR) ? PLUS_EXPR : MINUS_EXPR;
1942 gimple_assign_set_rhs_code (stmt, code);
1943 rhs2 = gimple_assign_rhs1 (def_stmt);
1944 gimple_assign_set_rhs2 (stmt, rhs2);
1945 gimple_set_modified (stmt, true);
1950 /* (-A) + B -> B - A. */
1951 if (TREE_CODE (rhs1) == SSA_NAME
1952 && code == PLUS_EXPR)
1954 gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
1955 if (is_gimple_assign (def_stmt)
1956 && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR
1957 && can_propagate_from (def_stmt))
1960 gimple_assign_set_rhs_code (stmt, code);
1962 gimple_assign_set_rhs1 (stmt, rhs1);
1963 rhs2 = gimple_assign_rhs1 (def_stmt);
1964 gimple_assign_set_rhs2 (stmt, rhs2);
1965 gimple_set_modified (stmt, true);
1972 /* We can't reassociate floating-point or fixed-point plus or minus
1973 because of saturation to +-Inf. */
1974 if (FLOAT_TYPE_P (TREE_TYPE (rhs1))
1975 || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1)))
1978 /* Second match patterns that allow contracting a plus-minus pair
1979 irrespective of overflow issues.
1981 (A +- B) - A -> +- B
1983 (CST +- A) +- CST -> CST +- A
1984 (A + CST) +- CST -> A + CST
1987 A - (A +- B) -> -+ B
1988 A +- (B +- A) -> +- B
1989 CST +- (CST +- A) -> CST +- A
1990 CST +- (A +- CST) -> CST +- A
1993 via commutating the addition and contracting operations to zero
1994 by reassociation. */
1996 gsi = gsi_for_stmt (stmt);
1997 if (TREE_CODE (rhs1) == SSA_NAME)
1999 gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
2000 if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt))
2002 enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
2003 if (def_code == PLUS_EXPR
2004 || def_code == MINUS_EXPR)
2006 tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2007 tree def_rhs2 = gimple_assign_rhs2 (def_stmt);
2008 if (operand_equal_p (def_rhs1, rhs2, 0)
2009 && code == MINUS_EXPR)
2011 /* (A +- B) - A -> +- B. */
2012 code = ((def_code == PLUS_EXPR)
2013 ? TREE_CODE (def_rhs2) : NEGATE_EXPR);
2016 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2017 gcc_assert (gsi_stmt (gsi) == stmt);
2018 gimple_set_modified (stmt, true);
2020 else if (operand_equal_p (def_rhs2, rhs2, 0)
2021 && code != def_code)
2023 /* (A +- B) -+ B -> A. */
2024 code = TREE_CODE (def_rhs1);
2027 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2028 gcc_assert (gsi_stmt (gsi) == stmt);
2029 gimple_set_modified (stmt, true);
2031 else if (TREE_CODE (rhs2) == INTEGER_CST
2032 && TREE_CODE (def_rhs1) == INTEGER_CST)
2034 /* (CST +- A) +- CST -> CST +- A. */
2035 tree cst = fold_binary (code, TREE_TYPE (rhs1),
2037 if (cst && !TREE_OVERFLOW (cst))
2040 gimple_assign_set_rhs_code (stmt, code);
2042 gimple_assign_set_rhs1 (stmt, rhs1);
2044 gimple_assign_set_rhs2 (stmt, rhs2);
2045 gimple_set_modified (stmt, true);
2048 else if (TREE_CODE (rhs2) == INTEGER_CST
2049 && TREE_CODE (def_rhs2) == INTEGER_CST
2050 && def_code == PLUS_EXPR)
2052 /* (A + CST) +- CST -> A + CST. */
2053 tree cst = fold_binary (code, TREE_TYPE (rhs1),
2055 if (cst && !TREE_OVERFLOW (cst))
2058 gimple_assign_set_rhs_code (stmt, code);
2060 gimple_assign_set_rhs1 (stmt, rhs1);
2062 gimple_assign_set_rhs2 (stmt, rhs2);
2063 gimple_set_modified (stmt, true);
2067 else if (def_code == BIT_NOT_EXPR
2068 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
2070 tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2071 if (code == PLUS_EXPR
2072 && operand_equal_p (def_rhs1, rhs2, 0))
2076 rhs1 = build_int_cst_type (TREE_TYPE (rhs2), -1);
2078 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2079 gcc_assert (gsi_stmt (gsi) == stmt);
2080 gimple_set_modified (stmt, true);
2082 else if (code == PLUS_EXPR
2083 && integer_onep (rhs1))
2089 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2090 gcc_assert (gsi_stmt (gsi) == stmt);
2091 gimple_set_modified (stmt, true);
2097 if (rhs2 && TREE_CODE (rhs2) == SSA_NAME)
2099 gimple def_stmt = SSA_NAME_DEF_STMT (rhs2);
2100 if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt))
2102 enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
2103 if (def_code == PLUS_EXPR
2104 || def_code == MINUS_EXPR)
2106 tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2107 tree def_rhs2 = gimple_assign_rhs2 (def_stmt);
2108 if (operand_equal_p (def_rhs1, rhs1, 0)
2109 && code == MINUS_EXPR)
2111 /* A - (A +- B) -> -+ B. */
2112 code = ((def_code == PLUS_EXPR)
2113 ? NEGATE_EXPR : TREE_CODE (def_rhs2));
2116 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2117 gcc_assert (gsi_stmt (gsi) == stmt);
2118 gimple_set_modified (stmt, true);
2120 else if (operand_equal_p (def_rhs2, rhs1, 0)
2121 && code != def_code)
2123 /* A +- (B +- A) -> +- B. */
2124 code = ((code == PLUS_EXPR)
2125 ? TREE_CODE (def_rhs1) : NEGATE_EXPR);
2128 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2129 gcc_assert (gsi_stmt (gsi) == stmt);
2130 gimple_set_modified (stmt, true);
2132 else if (TREE_CODE (rhs1) == INTEGER_CST
2133 && TREE_CODE (def_rhs1) == INTEGER_CST)
2135 /* CST +- (CST +- A) -> CST +- A. */
2136 tree cst = fold_binary (code, TREE_TYPE (rhs2),
2138 if (cst && !TREE_OVERFLOW (cst))
2140 code = (code == def_code ? PLUS_EXPR : MINUS_EXPR);
2141 gimple_assign_set_rhs_code (stmt, code);
2143 gimple_assign_set_rhs1 (stmt, rhs1);
2145 gimple_assign_set_rhs2 (stmt, rhs2);
2146 gimple_set_modified (stmt, true);
2149 else if (TREE_CODE (rhs1) == INTEGER_CST
2150 && TREE_CODE (def_rhs2) == INTEGER_CST)
2152 /* CST +- (A +- CST) -> CST +- A. */
2153 tree cst = fold_binary (def_code == code
2154 ? PLUS_EXPR : MINUS_EXPR,
2157 if (cst && !TREE_OVERFLOW (cst))
2160 gimple_assign_set_rhs1 (stmt, rhs1);
2162 gimple_assign_set_rhs2 (stmt, rhs2);
2163 gimple_set_modified (stmt, true);
2167 else if (def_code == BIT_NOT_EXPR
2168 && INTEGRAL_TYPE_P (TREE_TYPE (rhs2)))
2170 tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2171 if (code == PLUS_EXPR
2172 && operand_equal_p (def_rhs1, rhs1, 0))
2176 rhs1 = build_int_cst_type (TREE_TYPE (rhs1), -1);
2178 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2179 gcc_assert (gsi_stmt (gsi) == stmt);
2180 gimple_set_modified (stmt, true);
2187 if (gimple_modified_p (stmt))
2189 fold_stmt_inplace (stmt);
2191 if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
2192 && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
2199 /* Combine two conversions in a row for the second conversion at *GSI.
2200 Returns true if there were any changes made. */
2203 combine_conversions (gimple_stmt_iterator *gsi)
2205 gimple stmt = gsi_stmt (*gsi);
2208 enum tree_code code = gimple_assign_rhs_code (stmt);
2210 gcc_checking_assert (CONVERT_EXPR_CODE_P (code)
2211 || code == FLOAT_EXPR
2212 || code == FIX_TRUNC_EXPR);
2214 lhs = gimple_assign_lhs (stmt);
2215 op0 = gimple_assign_rhs1 (stmt);
2216 if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (op0)))
2218 gimple_assign_set_rhs_code (stmt, TREE_CODE (op0));
2222 if (TREE_CODE (op0) != SSA_NAME)
2225 def_stmt = SSA_NAME_DEF_STMT (op0);
2226 if (!is_gimple_assign (def_stmt))
2229 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
2231 tree defop0 = gimple_assign_rhs1 (def_stmt);
2232 tree type = TREE_TYPE (lhs);
2233 tree inside_type = TREE_TYPE (defop0);
2234 tree inter_type = TREE_TYPE (op0);
2235 int inside_int = INTEGRAL_TYPE_P (inside_type);
2236 int inside_ptr = POINTER_TYPE_P (inside_type);
2237 int inside_float = FLOAT_TYPE_P (inside_type);
2238 int inside_vec = TREE_CODE (inside_type) == VECTOR_TYPE;
2239 unsigned int inside_prec = TYPE_PRECISION (inside_type);
2240 int inside_unsignedp = TYPE_UNSIGNED (inside_type);
2241 int inter_int = INTEGRAL_TYPE_P (inter_type);
2242 int inter_ptr = POINTER_TYPE_P (inter_type);
2243 int inter_float = FLOAT_TYPE_P (inter_type);
2244 int inter_vec = TREE_CODE (inter_type) == VECTOR_TYPE;
2245 unsigned int inter_prec = TYPE_PRECISION (inter_type);
2246 int inter_unsignedp = TYPE_UNSIGNED (inter_type);
2247 int final_int = INTEGRAL_TYPE_P (type);
2248 int final_ptr = POINTER_TYPE_P (type);
2249 int final_float = FLOAT_TYPE_P (type);
2250 int final_vec = TREE_CODE (type) == VECTOR_TYPE;
2251 unsigned int final_prec = TYPE_PRECISION (type);
2252 int final_unsignedp = TYPE_UNSIGNED (type);
2254 /* In addition to the cases of two conversions in a row
2255 handled below, if we are converting something to its own
2256 type via an object of identical or wider precision, neither
2257 conversion is needed. */
2258 if (useless_type_conversion_p (type, inside_type)
2259 && (((inter_int || inter_ptr) && final_int)
2260 || (inter_float && final_float))
2261 && inter_prec >= final_prec)
2263 gimple_assign_set_rhs1 (stmt, unshare_expr (defop0));
2264 gimple_assign_set_rhs_code (stmt, TREE_CODE (defop0));
2269 /* Likewise, if the intermediate and initial types are either both
2270 float or both integer, we don't need the middle conversion if the
2271 former is wider than the latter and doesn't change the signedness
2272 (for integers). Avoid this if the final type is a pointer since
2273 then we sometimes need the middle conversion. Likewise if the
2274 final type has a precision not equal to the size of its mode. */
2275 if (((inter_int && inside_int)
2276 || (inter_float && inside_float)
2277 || (inter_vec && inside_vec))
2278 && inter_prec >= inside_prec
2279 && (inter_float || inter_vec
2280 || inter_unsignedp == inside_unsignedp)
2281 && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (type))
2282 && TYPE_MODE (type) == TYPE_MODE (inter_type))
2284 && (! final_vec || inter_prec == inside_prec))
2286 gimple_assign_set_rhs1 (stmt, defop0);
2291 /* If we have a sign-extension of a zero-extended value, we can
2292 replace that by a single zero-extension. */
2293 if (inside_int && inter_int && final_int
2294 && inside_prec < inter_prec && inter_prec < final_prec
2295 && inside_unsignedp && !inter_unsignedp)
2297 gimple_assign_set_rhs1 (stmt, defop0);
2302 /* Two conversions in a row are not needed unless:
2303 - some conversion is floating-point (overstrict for now), or
2304 - some conversion is a vector (overstrict for now), or
2305 - the intermediate type is narrower than both initial and
2307 - the intermediate type and innermost type differ in signedness,
2308 and the outermost type is wider than the intermediate, or
2309 - the initial type is a pointer type and the precisions of the
2310 intermediate and final types differ, or
2311 - the final type is a pointer type and the precisions of the
2312 initial and intermediate types differ. */
2313 if (! inside_float && ! inter_float && ! final_float
2314 && ! inside_vec && ! inter_vec && ! final_vec
2315 && (inter_prec >= inside_prec || inter_prec >= final_prec)
2316 && ! (inside_int && inter_int
2317 && inter_unsignedp != inside_unsignedp
2318 && inter_prec < final_prec)
2319 && ((inter_unsignedp && inter_prec > inside_prec)
2320 == (final_unsignedp && final_prec > inter_prec))
2321 && ! (inside_ptr && inter_prec != final_prec)
2322 && ! (final_ptr && inside_prec != inter_prec)
2323 && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (type))
2324 && TYPE_MODE (type) == TYPE_MODE (inter_type)))
2326 gimple_assign_set_rhs1 (stmt, defop0);
2331 /* A truncation to an unsigned type should be canonicalized as
2332 bitwise and of a mask. */
2333 if (final_int && inter_int && inside_int
2334 && final_prec == inside_prec
2335 && final_prec > inter_prec
2339 tem = fold_build2 (BIT_AND_EXPR, inside_type,
2342 (inside_type, double_int_mask (inter_prec)));
2343 if (!useless_type_conversion_p (type, inside_type))
2345 tem = force_gimple_operand_gsi (gsi, tem, true, NULL_TREE, true,
2347 gimple_assign_set_rhs1 (stmt, tem);
2350 gimple_assign_set_rhs_from_tree (gsi, tem);
2351 update_stmt (gsi_stmt (*gsi));
2359 /* Main entry point for the forward propagation and statement combine
2363 ssa_forward_propagate_and_combine (void)
2366 unsigned int todoflags = 0;
2368 cfg_changed = false;
2372 gimple_stmt_iterator gsi, prev;
2373 bool prev_initialized;
2375 /* Apply forward propagation to all stmts in the basic-block.
2376 Note we update GSI within the loop as necessary. */
2377 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2379 gimple stmt = gsi_stmt (gsi);
2381 enum tree_code code;
2383 if (!is_gimple_assign (stmt))
2389 lhs = gimple_assign_lhs (stmt);
2390 rhs = gimple_assign_rhs1 (stmt);
2391 code = gimple_assign_rhs_code (stmt);
2392 if (TREE_CODE (lhs) != SSA_NAME
2393 || has_zero_uses (lhs))
2399 /* If this statement sets an SSA_NAME to an address,
2400 try to propagate the address into the uses of the SSA_NAME. */
2401 if (code == ADDR_EXPR
2402 /* Handle pointer conversions on invariant addresses
2403 as well, as this is valid gimple. */
2404 || (CONVERT_EXPR_CODE_P (code)
2405 && TREE_CODE (rhs) == ADDR_EXPR
2406 && POINTER_TYPE_P (TREE_TYPE (lhs))))
2408 tree base = get_base_address (TREE_OPERAND (rhs, 0));
2411 || decl_address_invariant_p (base))
2412 && !stmt_references_abnormal_ssa_name (stmt)
2413 && forward_propagate_addr_expr (lhs, rhs))
2415 release_defs (stmt);
2416 todoflags |= TODO_remove_unused_locals;
2417 gsi_remove (&gsi, true);
2422 else if (code == POINTER_PLUS_EXPR && can_propagate_from (stmt))
2424 if (TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST
2425 /* ??? Better adjust the interface to that function
2426 instead of building new trees here. */
2427 && forward_propagate_addr_expr
2431 fold_build2 (MEM_REF,
2432 TREE_TYPE (TREE_TYPE (rhs)),
2436 gimple_assign_rhs2 (stmt))))))
2438 release_defs (stmt);
2439 todoflags |= TODO_remove_unused_locals;
2440 gsi_remove (&gsi, true);
2442 else if (is_gimple_min_invariant (rhs))
2444 /* Make sure to fold &a[0] + off_1 here. */
2445 fold_stmt_inplace (stmt);
2447 if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
2453 else if (TREE_CODE_CLASS (code) == tcc_comparison)
2455 forward_propagate_comparison (stmt);
2462 /* Combine stmts with the stmts defining their operands.
2463 Note we update GSI within the loop as necessary. */
2464 prev_initialized = false;
2465 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
2467 gimple stmt = gsi_stmt (gsi);
2468 bool changed = false;
2470 switch (gimple_code (stmt))
2474 tree rhs1 = gimple_assign_rhs1 (stmt);
2475 enum tree_code code = gimple_assign_rhs_code (stmt);
2477 if ((code == BIT_NOT_EXPR
2478 || code == NEGATE_EXPR)
2479 && TREE_CODE (rhs1) == SSA_NAME)
2480 changed = simplify_not_neg_expr (&gsi);
2481 else if (code == COND_EXPR)
2483 /* In this case the entire COND_EXPR is in rhs1. */
2485 fold_defer_overflow_warnings ();
2486 did_something = forward_propagate_into_cond (&gsi);
2487 stmt = gsi_stmt (gsi);
2488 if (did_something == 2)
2490 fold_undefer_overflow_warnings
2491 (!TREE_NO_WARNING (rhs1) && did_something, stmt,
2492 WARN_STRICT_OVERFLOW_CONDITIONAL);
2493 changed = did_something != 0;
2495 else if (TREE_CODE_CLASS (code) == tcc_comparison)
2497 bool no_warning = gimple_no_warning_p (stmt);
2498 fold_defer_overflow_warnings ();
2499 changed = forward_propagate_into_comparison (&gsi);
2500 fold_undefer_overflow_warnings
2501 (!no_warning && changed,
2502 stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
2504 else if (code == BIT_AND_EXPR
2505 || code == BIT_IOR_EXPR
2506 || code == BIT_XOR_EXPR)
2507 changed = simplify_bitwise_binary (&gsi);
2508 else if (code == PLUS_EXPR
2509 || code == MINUS_EXPR)
2510 changed = associate_plusminus (stmt);
2511 else if (CONVERT_EXPR_CODE_P (code)
2512 || code == FLOAT_EXPR
2513 || code == FIX_TRUNC_EXPR)
2514 changed = combine_conversions (&gsi);
2519 changed = simplify_gimple_switch (stmt);
2525 fold_defer_overflow_warnings ();
2526 did_something = forward_propagate_into_gimple_cond (stmt);
2527 if (did_something == 2)
2529 fold_undefer_overflow_warnings
2530 (did_something, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
2531 changed = did_something != 0;
2537 tree callee = gimple_call_fndecl (stmt);
2538 if (callee != NULL_TREE
2539 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
2540 changed = simplify_builtin_call (&gsi, callee);
2549 /* If the stmt changed then re-visit it and the statements
2550 inserted before it. */
2551 if (!prev_initialized)
2552 gsi = gsi_start_bb (bb);
2562 prev_initialized = true;
2569 todoflags |= TODO_cleanup_cfg;
2576 gate_forwprop (void)
2578 return flag_tree_forwprop;
2581 struct gimple_opt_pass pass_forwprop =
2585 "forwprop", /* name */
2586 gate_forwprop, /* gate */
2587 ssa_forward_propagate_and_combine, /* execute */
2590 0, /* static_pass_number */
2591 TV_TREE_FORWPROP, /* tv_id */
2592 PROP_cfg | PROP_ssa, /* properties_required */
2593 0, /* properties_provided */
2594 0, /* properties_destroyed */
2595 0, /* todo_flags_start */
2598 | TODO_verify_ssa /* todo_flags_finish */