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) == TRUTH_NOT_EXPR)
1131 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (use_stmt))))
1133 tree lhs = gimple_assign_lhs (use_stmt);
1135 /* We can propagate the condition into a conversion. */
1136 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt)))
1138 /* Avoid using fold here as that may create a COND_EXPR with
1139 non-boolean condition as canonical form. */
1140 tmp = build2 (gimple_assign_rhs_code (stmt), TREE_TYPE (lhs),
1141 gimple_assign_rhs1 (stmt), gimple_assign_rhs2 (stmt));
1143 /* We can propagate the condition into X op CST where op
1144 is EQ_EXPR or NE_EXPR and CST is either one or zero. */
1145 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (use_stmt))
1147 && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == SSA_NAME
1148 && TREE_CODE (gimple_assign_rhs2 (use_stmt)) == INTEGER_CST)
1150 enum tree_code code = gimple_assign_rhs_code (use_stmt);
1151 tree cst = gimple_assign_rhs2 (use_stmt);
1154 cond = build2 (gimple_assign_rhs_code (stmt),
1156 gimple_assign_rhs1 (stmt),
1157 gimple_assign_rhs2 (stmt));
1159 tmp = combine_cond_expr_cond (gimple_location (use_stmt),
1160 code, TREE_TYPE (lhs),
1162 if (tmp == NULL_TREE)
1165 /* We can propagate the condition into a statement that
1166 computes the logical negation of the comparison result. */
1167 else if (gimple_assign_rhs_code (use_stmt) == TRUTH_NOT_EXPR)
1169 tree type = TREE_TYPE (gimple_assign_rhs1 (stmt));
1170 bool nans = HONOR_NANS (TYPE_MODE (type));
1171 enum tree_code code;
1172 code = invert_tree_comparison (gimple_assign_rhs_code (stmt), nans);
1173 if (code == ERROR_MARK)
1176 tmp = build2 (code, TREE_TYPE (lhs), gimple_assign_rhs1 (stmt),
1177 gimple_assign_rhs2 (stmt));
1183 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1184 gimple_assign_set_rhs_from_tree (&gsi, unshare_expr (tmp));
1185 use_stmt = gsi_stmt (gsi);
1186 update_stmt (use_stmt);
1189 if (dump_file && (dump_flags & TDF_DETAILS))
1191 tree old_rhs = rhs_to_tree (TREE_TYPE (gimple_assign_lhs (stmt)),
1193 fprintf (dump_file, " Replaced '");
1194 print_generic_expr (dump_file, old_rhs, dump_flags);
1195 fprintf (dump_file, "' with '");
1196 print_generic_expr (dump_file, tmp, dump_flags);
1197 fprintf (dump_file, "'\n");
1200 /* Remove defining statements. */
1201 return remove_prop_source_from_use (name);
1208 /* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y.
1209 If so, we can change STMT into lhs = y which can later be copy
1210 propagated. Similarly for negation.
1212 This could trivially be formulated as a forward propagation
1213 to immediate uses. However, we already had an implementation
1214 from DOM which used backward propagation via the use-def links.
1216 It turns out that backward propagation is actually faster as
1217 there's less work to do for each NOT/NEG expression we find.
1218 Backwards propagation needs to look at the statement in a single
1219 backlink. Forward propagation needs to look at potentially more
1220 than one forward link.
1222 Returns true when the statement was changed. */
1225 simplify_not_neg_expr (gimple_stmt_iterator *gsi_p)
1227 gimple stmt = gsi_stmt (*gsi_p);
1228 tree rhs = gimple_assign_rhs1 (stmt);
1229 gimple rhs_def_stmt = SSA_NAME_DEF_STMT (rhs);
1231 /* See if the RHS_DEF_STMT has the same form as our statement. */
1232 if (is_gimple_assign (rhs_def_stmt)
1233 && gimple_assign_rhs_code (rhs_def_stmt) == gimple_assign_rhs_code (stmt))
1235 tree rhs_def_operand = gimple_assign_rhs1 (rhs_def_stmt);
1237 /* Verify that RHS_DEF_OPERAND is a suitable SSA_NAME. */
1238 if (TREE_CODE (rhs_def_operand) == SSA_NAME
1239 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand))
1241 gimple_assign_set_rhs_from_tree (gsi_p, rhs_def_operand);
1242 stmt = gsi_stmt (*gsi_p);
1251 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
1252 the condition which we may be able to optimize better. */
1255 simplify_gimple_switch (gimple stmt)
1257 tree cond = gimple_switch_index (stmt);
1261 /* The optimization that we really care about is removing unnecessary
1262 casts. That will let us do much better in propagating the inferred
1263 constant at the switch target. */
1264 if (TREE_CODE (cond) == SSA_NAME)
1266 def_stmt = SSA_NAME_DEF_STMT (cond);
1267 if (is_gimple_assign (def_stmt))
1269 if (gimple_assign_rhs_code (def_stmt) == NOP_EXPR)
1274 def = gimple_assign_rhs1 (def_stmt);
1276 /* ??? Why was Jeff testing this? We are gimple... */
1277 gcc_checking_assert (is_gimple_val (def));
1279 to = TREE_TYPE (cond);
1280 ti = TREE_TYPE (def);
1282 /* If we have an extension that preserves value, then we
1283 can copy the source value into the switch. */
1285 need_precision = TYPE_PRECISION (ti);
1287 if (! INTEGRAL_TYPE_P (ti))
1289 else if (TYPE_UNSIGNED (to) && !TYPE_UNSIGNED (ti))
1291 else if (!TYPE_UNSIGNED (to) && TYPE_UNSIGNED (ti))
1292 need_precision += 1;
1293 if (TYPE_PRECISION (to) < need_precision)
1298 gimple_switch_set_index (stmt, def);
1309 /* For pointers p2 and p1 return p2 - p1 if the
1310 difference is known and constant, otherwise return NULL. */
1313 constant_pointer_difference (tree p1, tree p2)
1316 #define CPD_ITERATIONS 5
1317 tree exps[2][CPD_ITERATIONS];
1318 tree offs[2][CPD_ITERATIONS];
1321 for (i = 0; i < 2; i++)
1323 tree p = i ? p1 : p2;
1324 tree off = size_zero_node;
1326 enum tree_code code;
1328 /* For each of p1 and p2 we need to iterate at least
1329 twice, to handle ADDR_EXPR directly in p1/p2,
1330 SSA_NAME with ADDR_EXPR or POINTER_PLUS_EXPR etc.
1331 on definition's stmt RHS. Iterate a few extra times. */
1335 if (!POINTER_TYPE_P (TREE_TYPE (p)))
1337 if (TREE_CODE (p) == ADDR_EXPR)
1339 tree q = TREE_OPERAND (p, 0);
1340 HOST_WIDE_INT offset;
1341 tree base = get_addr_base_and_unit_offset (q, &offset);
1346 off = size_binop (PLUS_EXPR, off, size_int (offset));
1348 if (TREE_CODE (q) == MEM_REF
1349 && TREE_CODE (TREE_OPERAND (q, 0)) == SSA_NAME)
1351 p = TREE_OPERAND (q, 0);
1352 off = size_binop (PLUS_EXPR, off,
1353 double_int_to_tree (sizetype,
1354 mem_ref_offset (q)));
1363 if (TREE_CODE (p) != SSA_NAME)
1367 if (j == CPD_ITERATIONS)
1369 stmt = SSA_NAME_DEF_STMT (p);
1370 if (!is_gimple_assign (stmt) || gimple_assign_lhs (stmt) != p)
1372 code = gimple_assign_rhs_code (stmt);
1373 if (code == POINTER_PLUS_EXPR)
1375 if (TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST)
1377 off = size_binop (PLUS_EXPR, off, gimple_assign_rhs2 (stmt));
1378 p = gimple_assign_rhs1 (stmt);
1380 else if (code == ADDR_EXPR || code == NOP_EXPR)
1381 p = gimple_assign_rhs1 (stmt);
1389 for (i = 0; i < cnt[0]; i++)
1390 for (j = 0; j < cnt[1]; j++)
1391 if (exps[0][i] == exps[1][j])
1392 return size_binop (MINUS_EXPR, offs[0][i], offs[1][j]);
1397 /* *GSI_P is a GIMPLE_CALL to a builtin function.
1399 memcpy (p, "abcd", 4);
1400 memset (p + 4, ' ', 3);
1402 memcpy (p, "abcd ", 7);
1403 call if the latter can be stored by pieces during expansion. */
1406 simplify_builtin_call (gimple_stmt_iterator *gsi_p, tree callee2)
1408 gimple stmt1, stmt2 = gsi_stmt (*gsi_p);
1409 tree vuse = gimple_vuse (stmt2);
1412 stmt1 = SSA_NAME_DEF_STMT (vuse);
1414 switch (DECL_FUNCTION_CODE (callee2))
1416 case BUILT_IN_MEMSET:
1417 if (gimple_call_num_args (stmt2) != 3
1418 || gimple_call_lhs (stmt2)
1420 || BITS_PER_UNIT != 8)
1425 tree ptr1, src1, str1, off1, len1, lhs1;
1426 tree ptr2 = gimple_call_arg (stmt2, 0);
1427 tree val2 = gimple_call_arg (stmt2, 1);
1428 tree len2 = gimple_call_arg (stmt2, 2);
1429 tree diff, vdef, new_str_cst;
1431 unsigned int ptr1_align;
1432 unsigned HOST_WIDE_INT src_len;
1434 use_operand_p use_p;
1436 if (!host_integerp (val2, 0)
1437 || !host_integerp (len2, 1))
1439 if (is_gimple_call (stmt1))
1441 /* If first stmt is a call, it needs to be memcpy
1442 or mempcpy, with string literal as second argument and
1444 callee1 = gimple_call_fndecl (stmt1);
1445 if (callee1 == NULL_TREE
1446 || DECL_BUILT_IN_CLASS (callee1) != BUILT_IN_NORMAL
1447 || gimple_call_num_args (stmt1) != 3)
1449 if (DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMCPY
1450 && DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMPCPY)
1452 ptr1 = gimple_call_arg (stmt1, 0);
1453 src1 = gimple_call_arg (stmt1, 1);
1454 len1 = gimple_call_arg (stmt1, 2);
1455 lhs1 = gimple_call_lhs (stmt1);
1456 if (!host_integerp (len1, 1))
1458 str1 = string_constant (src1, &off1);
1459 if (str1 == NULL_TREE)
1461 if (!host_integerp (off1, 1)
1462 || compare_tree_int (off1, TREE_STRING_LENGTH (str1) - 1) > 0
1463 || compare_tree_int (len1, TREE_STRING_LENGTH (str1)
1464 - tree_low_cst (off1, 1)) > 0
1465 || TREE_CODE (TREE_TYPE (str1)) != ARRAY_TYPE
1466 || TYPE_MODE (TREE_TYPE (TREE_TYPE (str1)))
1467 != TYPE_MODE (char_type_node))
1470 else if (gimple_assign_single_p (stmt1))
1472 /* Otherwise look for length 1 memcpy optimized into
1474 ptr1 = gimple_assign_lhs (stmt1);
1475 src1 = gimple_assign_rhs1 (stmt1);
1476 if (TREE_CODE (ptr1) != MEM_REF
1477 || TYPE_MODE (TREE_TYPE (ptr1)) != TYPE_MODE (char_type_node)
1478 || !host_integerp (src1, 0))
1480 ptr1 = build_fold_addr_expr (ptr1);
1481 callee1 = NULL_TREE;
1482 len1 = size_one_node;
1484 off1 = size_zero_node;
1490 diff = constant_pointer_difference (ptr1, ptr2);
1491 if (diff == NULL && lhs1 != NULL)
1493 diff = constant_pointer_difference (lhs1, ptr2);
1494 if (DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1496 diff = size_binop (PLUS_EXPR, diff,
1497 fold_convert (sizetype, len1));
1499 /* If the difference between the second and first destination pointer
1500 is not constant, or is bigger than memcpy length, bail out. */
1502 || !host_integerp (diff, 1)
1503 || tree_int_cst_lt (len1, diff))
1506 /* Use maximum of difference plus memset length and memcpy length
1507 as the new memcpy length, if it is too big, bail out. */
1508 src_len = tree_low_cst (diff, 1);
1509 src_len += tree_low_cst (len2, 1);
1510 if (src_len < (unsigned HOST_WIDE_INT) tree_low_cst (len1, 1))
1511 src_len = tree_low_cst (len1, 1);
1515 /* If mempcpy value is used elsewhere, bail out, as mempcpy
1516 with bigger length will return different result. */
1517 if (lhs1 != NULL_TREE
1518 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1519 && (TREE_CODE (lhs1) != SSA_NAME
1520 || !single_imm_use (lhs1, &use_p, &use_stmt)
1521 || use_stmt != stmt2))
1524 /* If anything reads memory in between memcpy and memset
1525 call, the modified memcpy call might change it. */
1526 vdef = gimple_vdef (stmt1);
1528 && (!single_imm_use (vdef, &use_p, &use_stmt)
1529 || use_stmt != stmt2))
1532 ptr1_align = get_pointer_alignment (ptr1, BIGGEST_ALIGNMENT);
1533 /* Construct the new source string literal. */
1534 src_buf = XALLOCAVEC (char, src_len + 1);
1537 TREE_STRING_POINTER (str1) + tree_low_cst (off1, 1),
1538 tree_low_cst (len1, 1));
1540 src_buf[0] = tree_low_cst (src1, 0);
1541 memset (src_buf + tree_low_cst (diff, 1),
1542 tree_low_cst (val2, 1), tree_low_cst (len2, 1));
1543 src_buf[src_len] = '\0';
1544 /* Neither builtin_strncpy_read_str nor builtin_memcpy_read_str
1545 handle embedded '\0's. */
1546 if (strlen (src_buf) != src_len)
1548 rtl_profile_for_bb (gimple_bb (stmt2));
1549 /* If the new memcpy wouldn't be emitted by storing the literal
1550 by pieces, this optimization might enlarge .rodata too much,
1551 as commonly used string literals couldn't be shared any
1553 if (!can_store_by_pieces (src_len,
1554 builtin_strncpy_read_str,
1555 src_buf, ptr1_align, false))
1558 new_str_cst = build_string_literal (src_len, src_buf);
1561 /* If STMT1 is a mem{,p}cpy call, adjust it and remove
1563 if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1564 gimple_call_set_lhs (stmt1, NULL_TREE);
1565 gimple_call_set_arg (stmt1, 1, new_str_cst);
1566 gimple_call_set_arg (stmt1, 2,
1567 build_int_cst (TREE_TYPE (len1), src_len));
1568 update_stmt (stmt1);
1569 unlink_stmt_vdef (stmt2);
1570 gsi_remove (gsi_p, true);
1571 release_defs (stmt2);
1572 if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1573 release_ssa_name (lhs1);
1578 /* Otherwise, if STMT1 is length 1 memcpy optimized into
1579 assignment, remove STMT1 and change memset call into
1581 gimple_stmt_iterator gsi = gsi_for_stmt (stmt1);
1583 if (!is_gimple_val (ptr1))
1584 ptr1 = force_gimple_operand_gsi (gsi_p, ptr1, true, NULL_TREE,
1585 true, GSI_SAME_STMT);
1586 gimple_call_set_fndecl (stmt2, built_in_decls [BUILT_IN_MEMCPY]);
1587 gimple_call_set_arg (stmt2, 0, ptr1);
1588 gimple_call_set_arg (stmt2, 1, new_str_cst);
1589 gimple_call_set_arg (stmt2, 2,
1590 build_int_cst (TREE_TYPE (len2), src_len));
1591 unlink_stmt_vdef (stmt1);
1592 gsi_remove (&gsi, true);
1593 release_defs (stmt1);
1594 update_stmt (stmt2);
1605 /* Checks if expression has type of one-bit precision, or is a known
1606 truth-valued expression. */
1608 truth_valued_ssa_name (tree name)
1611 tree type = TREE_TYPE (name);
1613 if (!INTEGRAL_TYPE_P (type))
1615 /* Don't check here for BOOLEAN_TYPE as the precision isn't
1616 necessarily one and so ~X is not equal to !X. */
1617 if (TYPE_PRECISION (type) == 1)
1619 def = SSA_NAME_DEF_STMT (name);
1620 if (is_gimple_assign (def))
1621 return truth_value_p (gimple_assign_rhs_code (def));
1625 /* Helper routine for simplify_bitwise_binary_1 function.
1626 Return for the SSA name NAME the expression X if it mets condition
1627 NAME = !X. Otherwise return NULL_TREE.
1628 Detected patterns for NAME = !X are:
1629 !X and X == 0 for X with integral type.
1630 X ^ 1, X != 1,or ~X for X with integral type with precision of one. */
1632 lookup_logical_inverted_value (tree name)
1635 enum tree_code code;
1638 /* If name has none-intergal type, or isn't a SSA_NAME, then
1640 if (TREE_CODE (name) != SSA_NAME
1641 || !INTEGRAL_TYPE_P (TREE_TYPE (name)))
1643 def = SSA_NAME_DEF_STMT (name);
1644 if (!is_gimple_assign (def))
1647 code = gimple_assign_rhs_code (def);
1648 op1 = gimple_assign_rhs1 (def);
1651 /* Get for EQ_EXPR or BIT_XOR_EXPR operation the second operand.
1652 If CODE isn't an EQ_EXPR, BIT_XOR_EXPR, TRUTH_NOT_EXPR,
1653 or BIT_NOT_EXPR, then return. */
1654 if (code == EQ_EXPR || code == NE_EXPR
1655 || code == BIT_XOR_EXPR)
1656 op2 = gimple_assign_rhs2 (def);
1660 case TRUTH_NOT_EXPR:
1663 if (truth_valued_ssa_name (name))
1667 /* Check if we have X == 0 and X has an integral type. */
1668 if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)))
1670 if (integer_zerop (op2))
1674 /* Check if we have X != 1 and X is a truth-valued. */
1675 if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)))
1677 if (integer_onep (op2) && truth_valued_ssa_name (op1))
1681 /* Check if we have X ^ 1 and X is truth valued. */
1682 if (integer_onep (op2) && truth_valued_ssa_name (op1))
1692 /* Optimize ARG1 CODE ARG2 to a constant for bitwise binary
1693 operations CODE, if one operand has the logically inverted
1694 value of the other. */
1696 simplify_bitwise_binary_1 (enum tree_code code, tree type,
1697 tree arg1, tree arg2)
1701 /* If CODE isn't a bitwise binary operation, return NULL_TREE. */
1702 if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR
1703 && code != BIT_XOR_EXPR)
1706 /* First check if operands ARG1 and ARG2 are equal. If so
1707 return NULL_TREE as this optimization is handled fold_stmt. */
1710 /* See if we have in arguments logical-not patterns. */
1711 if (((anot = lookup_logical_inverted_value (arg1)) == NULL_TREE
1713 && ((anot = lookup_logical_inverted_value (arg2)) == NULL_TREE
1718 if (code == BIT_AND_EXPR)
1719 return fold_convert (type, integer_zero_node);
1720 /* X | !X -> 1 and X ^ !X -> 1, if X is truth-valued. */
1721 if (truth_valued_ssa_name (anot))
1722 return fold_convert (type, integer_one_node);
1724 /* ??? Otherwise result is (X != 0 ? X : 1). not handled. */
1728 /* Simplify bitwise binary operations.
1729 Return true if a transformation applied, otherwise return false. */
1732 simplify_bitwise_binary (gimple_stmt_iterator *gsi)
1734 gimple stmt = gsi_stmt (*gsi);
1735 tree arg1 = gimple_assign_rhs1 (stmt);
1736 tree arg2 = gimple_assign_rhs2 (stmt);
1737 enum tree_code code = gimple_assign_rhs_code (stmt);
1739 gimple def1 = NULL, def2 = NULL;
1740 tree def1_arg1, def2_arg1;
1741 enum tree_code def1_code, def2_code;
1743 /* If the first argument is an SSA name that is itself a result of a
1744 typecast of an ADDR_EXPR to an integer, feed the ADDR_EXPR to the
1745 folder rather than the ssa name. */
1746 if (code == BIT_AND_EXPR
1747 && TREE_CODE (arg2) == INTEGER_CST
1748 && TREE_CODE (arg1) == SSA_NAME)
1750 gimple def = SSA_NAME_DEF_STMT (arg1);
1753 /* ??? This looks bogus - the conversion could be truncating. */
1754 if (is_gimple_assign (def)
1755 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def))
1756 && INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
1758 tree opp = gimple_assign_rhs1 (def);
1759 if (TREE_CODE (opp) == ADDR_EXPR)
1763 res = fold_binary_loc (gimple_location (stmt),
1764 BIT_AND_EXPR, TREE_TYPE (gimple_assign_lhs (stmt)),
1766 if (res && is_gimple_min_invariant (res))
1768 gimple_assign_set_rhs_from_tree (gsi, res);
1774 def1_code = TREE_CODE (arg1);
1776 if (TREE_CODE (arg1) == SSA_NAME)
1778 def1 = SSA_NAME_DEF_STMT (arg1);
1779 if (is_gimple_assign (def1))
1781 def1_code = gimple_assign_rhs_code (def1);
1782 def1_arg1 = gimple_assign_rhs1 (def1);
1786 def2_code = TREE_CODE (arg2);
1788 if (TREE_CODE (arg2) == SSA_NAME)
1790 def2 = SSA_NAME_DEF_STMT (arg2);
1791 if (is_gimple_assign (def2))
1793 def2_code = gimple_assign_rhs_code (def2);
1794 def2_arg1 = gimple_assign_rhs1 (def2);
1798 /* Try to fold (type) X op CST -> (type) (X op ((type-x) CST)). */
1799 if (TREE_CODE (arg2) == INTEGER_CST
1800 && CONVERT_EXPR_CODE_P (def1_code)
1801 && INTEGRAL_TYPE_P (TREE_TYPE (def1_arg1))
1802 && int_fits_type_p (arg2, TREE_TYPE (def1_arg1)))
1805 tree tem = create_tmp_reg (TREE_TYPE (def1_arg1), NULL);
1807 gimple_build_assign_with_ops (code, tem, def1_arg1,
1808 fold_convert_loc (gimple_location (stmt),
1809 TREE_TYPE (def1_arg1),
1811 tem = make_ssa_name (tem, newop);
1812 gimple_assign_set_lhs (newop, tem);
1813 gsi_insert_before (gsi, newop, GSI_SAME_STMT);
1814 gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
1815 tem, NULL_TREE, NULL_TREE);
1816 update_stmt (gsi_stmt (*gsi));
1820 /* For bitwise binary operations apply operand conversions to the
1821 binary operation result instead of to the operands. This allows
1822 to combine successive conversions and bitwise binary operations. */
1823 if (CONVERT_EXPR_CODE_P (def1_code)
1824 && CONVERT_EXPR_CODE_P (def2_code)
1825 && types_compatible_p (TREE_TYPE (def1_arg1), TREE_TYPE (def2_arg1))
1826 /* Make sure that the conversion widens the operands, or has same
1827 precision, or that it changes the operation to a bitfield
1829 && ((TYPE_PRECISION (TREE_TYPE (def1_arg1))
1830 <= TYPE_PRECISION (TREE_TYPE (arg1)))
1831 || (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (arg1)))
1833 || (TYPE_PRECISION (TREE_TYPE (arg1))
1834 != GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (arg1))))))
1837 tree tem = create_tmp_reg (TREE_TYPE (def1_arg1),
1839 newop = gimple_build_assign_with_ops (code, tem, def1_arg1, def2_arg1);
1840 tem = make_ssa_name (tem, newop);
1841 gimple_assign_set_lhs (newop, tem);
1842 gsi_insert_before (gsi, newop, GSI_SAME_STMT);
1843 gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
1844 tem, NULL_TREE, NULL_TREE);
1845 update_stmt (gsi_stmt (*gsi));
1849 /* (a | CST1) & CST2 -> (a & CST2) | (CST1 & CST2). */
1850 if (code == BIT_AND_EXPR
1851 && def1_code == BIT_IOR_EXPR
1852 && TREE_CODE (arg2) == INTEGER_CST
1853 && TREE_CODE (gimple_assign_rhs2 (def1)) == INTEGER_CST)
1855 tree cst = fold_build2 (BIT_AND_EXPR, TREE_TYPE (arg2),
1856 arg2, gimple_assign_rhs2 (def1));
1859 if (integer_zerop (cst))
1861 gimple_assign_set_rhs1 (stmt, def1_arg1);
1865 tem = create_tmp_reg (TREE_TYPE (arg2), NULL);
1866 newop = gimple_build_assign_with_ops (BIT_AND_EXPR,
1867 tem, def1_arg1, arg2);
1868 tem = make_ssa_name (tem, newop);
1869 gimple_assign_set_lhs (newop, tem);
1870 /* Make sure to re-process the new stmt as it's walking upwards. */
1871 gsi_insert_before (gsi, newop, GSI_NEW_STMT);
1872 gimple_assign_set_rhs1 (stmt, tem);
1873 gimple_assign_set_rhs2 (stmt, cst);
1874 gimple_assign_set_rhs_code (stmt, BIT_IOR_EXPR);
1879 /* Combine successive equal operations with constants. */
1880 if ((code == BIT_AND_EXPR
1881 || code == BIT_IOR_EXPR
1882 || code == BIT_XOR_EXPR)
1883 && def1_code == code
1884 && TREE_CODE (arg2) == INTEGER_CST
1885 && TREE_CODE (gimple_assign_rhs2 (def1)) == INTEGER_CST)
1887 tree cst = fold_build2 (code, TREE_TYPE (arg2),
1888 arg2, gimple_assign_rhs2 (def1));
1889 gimple_assign_set_rhs1 (stmt, def1_arg1);
1890 gimple_assign_set_rhs2 (stmt, cst);
1895 /* Try simple folding for X op !X, and X op X. */
1896 res = simplify_bitwise_binary_1 (code, TREE_TYPE (arg1), arg1, arg2);
1897 if (res != NULL_TREE)
1899 gimple_assign_set_rhs_from_tree (gsi, res);
1900 update_stmt (gsi_stmt (*gsi));
1908 /* Perform re-associations of the plus or minus statement STMT that are
1909 always permitted. Returns true if the CFG was changed. */
1912 associate_plusminus (gimple stmt)
1914 tree rhs1 = gimple_assign_rhs1 (stmt);
1915 tree rhs2 = gimple_assign_rhs2 (stmt);
1916 enum tree_code code = gimple_assign_rhs_code (stmt);
1917 gimple_stmt_iterator gsi;
1920 /* We can't reassociate at all for saturating types. */
1921 if (TYPE_SATURATING (TREE_TYPE (rhs1)))
1924 /* First contract negates. */
1929 /* A +- (-B) -> A -+ B. */
1930 if (TREE_CODE (rhs2) == SSA_NAME)
1932 gimple def_stmt = SSA_NAME_DEF_STMT (rhs2);
1933 if (is_gimple_assign (def_stmt)
1934 && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR
1935 && can_propagate_from (def_stmt))
1937 code = (code == MINUS_EXPR) ? PLUS_EXPR : MINUS_EXPR;
1938 gimple_assign_set_rhs_code (stmt, code);
1939 rhs2 = gimple_assign_rhs1 (def_stmt);
1940 gimple_assign_set_rhs2 (stmt, rhs2);
1941 gimple_set_modified (stmt, true);
1946 /* (-A) + B -> B - A. */
1947 if (TREE_CODE (rhs1) == SSA_NAME
1948 && code == PLUS_EXPR)
1950 gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
1951 if (is_gimple_assign (def_stmt)
1952 && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR
1953 && can_propagate_from (def_stmt))
1956 gimple_assign_set_rhs_code (stmt, code);
1958 gimple_assign_set_rhs1 (stmt, rhs1);
1959 rhs2 = gimple_assign_rhs1 (def_stmt);
1960 gimple_assign_set_rhs2 (stmt, rhs2);
1961 gimple_set_modified (stmt, true);
1968 /* We can't reassociate floating-point or fixed-point plus or minus
1969 because of saturation to +-Inf. */
1970 if (FLOAT_TYPE_P (TREE_TYPE (rhs1))
1971 || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1)))
1974 /* Second match patterns that allow contracting a plus-minus pair
1975 irrespective of overflow issues.
1977 (A +- B) - A -> +- B
1979 (CST +- A) +- CST -> CST +- A
1980 (A + CST) +- CST -> A + CST
1983 A - (A +- B) -> -+ B
1984 A +- (B +- A) -> +- B
1985 CST +- (CST +- A) -> CST +- A
1986 CST +- (A +- CST) -> CST +- A
1989 via commutating the addition and contracting operations to zero
1990 by reassociation. */
1992 gsi = gsi_for_stmt (stmt);
1993 if (TREE_CODE (rhs1) == SSA_NAME)
1995 gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
1996 if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt))
1998 enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
1999 if (def_code == PLUS_EXPR
2000 || def_code == MINUS_EXPR)
2002 tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2003 tree def_rhs2 = gimple_assign_rhs2 (def_stmt);
2004 if (operand_equal_p (def_rhs1, rhs2, 0)
2005 && code == MINUS_EXPR)
2007 /* (A +- B) - A -> +- B. */
2008 code = ((def_code == PLUS_EXPR)
2009 ? TREE_CODE (def_rhs2) : NEGATE_EXPR);
2012 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2013 gcc_assert (gsi_stmt (gsi) == stmt);
2014 gimple_set_modified (stmt, true);
2016 else if (operand_equal_p (def_rhs2, rhs2, 0)
2017 && code != def_code)
2019 /* (A +- B) -+ B -> A. */
2020 code = TREE_CODE (def_rhs1);
2023 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2024 gcc_assert (gsi_stmt (gsi) == stmt);
2025 gimple_set_modified (stmt, true);
2027 else if (TREE_CODE (rhs2) == INTEGER_CST
2028 && TREE_CODE (def_rhs1) == INTEGER_CST)
2030 /* (CST +- A) +- CST -> CST +- A. */
2031 tree cst = fold_binary (code, TREE_TYPE (rhs1),
2033 if (cst && !TREE_OVERFLOW (cst))
2036 gimple_assign_set_rhs_code (stmt, code);
2038 gimple_assign_set_rhs1 (stmt, rhs1);
2040 gimple_assign_set_rhs2 (stmt, rhs2);
2041 gimple_set_modified (stmt, true);
2044 else if (TREE_CODE (rhs2) == INTEGER_CST
2045 && TREE_CODE (def_rhs2) == INTEGER_CST
2046 && def_code == PLUS_EXPR)
2048 /* (A + CST) +- CST -> A + CST. */
2049 tree cst = fold_binary (code, TREE_TYPE (rhs1),
2051 if (cst && !TREE_OVERFLOW (cst))
2054 gimple_assign_set_rhs_code (stmt, code);
2056 gimple_assign_set_rhs1 (stmt, rhs1);
2058 gimple_assign_set_rhs2 (stmt, rhs2);
2059 gimple_set_modified (stmt, true);
2063 else if (def_code == BIT_NOT_EXPR
2064 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
2066 tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2067 if (code == PLUS_EXPR
2068 && operand_equal_p (def_rhs1, rhs2, 0))
2072 rhs1 = build_int_cst_type (TREE_TYPE (rhs2), -1);
2074 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2075 gcc_assert (gsi_stmt (gsi) == stmt);
2076 gimple_set_modified (stmt, true);
2078 else if (code == PLUS_EXPR
2079 && integer_onep (rhs1))
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);
2093 if (rhs2 && TREE_CODE (rhs2) == SSA_NAME)
2095 gimple def_stmt = SSA_NAME_DEF_STMT (rhs2);
2096 if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt))
2098 enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
2099 if (def_code == PLUS_EXPR
2100 || def_code == MINUS_EXPR)
2102 tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2103 tree def_rhs2 = gimple_assign_rhs2 (def_stmt);
2104 if (operand_equal_p (def_rhs1, rhs1, 0)
2105 && code == MINUS_EXPR)
2107 /* A - (A +- B) -> -+ B. */
2108 code = ((def_code == PLUS_EXPR)
2109 ? NEGATE_EXPR : TREE_CODE (def_rhs2));
2112 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2113 gcc_assert (gsi_stmt (gsi) == stmt);
2114 gimple_set_modified (stmt, true);
2116 else if (operand_equal_p (def_rhs2, rhs1, 0)
2117 && code != def_code)
2119 /* A +- (B +- A) -> +- B. */
2120 code = ((code == PLUS_EXPR)
2121 ? TREE_CODE (def_rhs1) : NEGATE_EXPR);
2124 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2125 gcc_assert (gsi_stmt (gsi) == stmt);
2126 gimple_set_modified (stmt, true);
2128 else if (TREE_CODE (rhs1) == INTEGER_CST
2129 && TREE_CODE (def_rhs1) == INTEGER_CST)
2131 /* CST +- (CST +- A) -> CST +- A. */
2132 tree cst = fold_binary (code, TREE_TYPE (rhs2),
2134 if (cst && !TREE_OVERFLOW (cst))
2136 code = (code == def_code ? PLUS_EXPR : MINUS_EXPR);
2137 gimple_assign_set_rhs_code (stmt, code);
2139 gimple_assign_set_rhs1 (stmt, rhs1);
2141 gimple_assign_set_rhs2 (stmt, rhs2);
2142 gimple_set_modified (stmt, true);
2145 else if (TREE_CODE (rhs1) == INTEGER_CST
2146 && TREE_CODE (def_rhs2) == INTEGER_CST)
2148 /* CST +- (A +- CST) -> CST +- A. */
2149 tree cst = fold_binary (def_code == code
2150 ? PLUS_EXPR : MINUS_EXPR,
2153 if (cst && !TREE_OVERFLOW (cst))
2156 gimple_assign_set_rhs1 (stmt, rhs1);
2158 gimple_assign_set_rhs2 (stmt, rhs2);
2159 gimple_set_modified (stmt, true);
2163 else if (def_code == BIT_NOT_EXPR
2164 && INTEGRAL_TYPE_P (TREE_TYPE (rhs2)))
2166 tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2167 if (code == PLUS_EXPR
2168 && operand_equal_p (def_rhs1, rhs1, 0))
2172 rhs1 = build_int_cst_type (TREE_TYPE (rhs1), -1);
2174 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2175 gcc_assert (gsi_stmt (gsi) == stmt);
2176 gimple_set_modified (stmt, true);
2183 if (gimple_modified_p (stmt))
2185 fold_stmt_inplace (stmt);
2187 if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
2188 && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
2195 /* Combine two conversions in a row for the second conversion at *GSI.
2196 Returns true if there were any changes made. */
2199 combine_conversions (gimple_stmt_iterator *gsi)
2201 gimple stmt = gsi_stmt (*gsi);
2204 enum tree_code code = gimple_assign_rhs_code (stmt);
2206 gcc_checking_assert (CONVERT_EXPR_CODE_P (code)
2207 || code == FLOAT_EXPR
2208 || code == FIX_TRUNC_EXPR);
2210 lhs = gimple_assign_lhs (stmt);
2211 op0 = gimple_assign_rhs1 (stmt);
2212 if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (op0)))
2214 gimple_assign_set_rhs_code (stmt, TREE_CODE (op0));
2218 if (TREE_CODE (op0) != SSA_NAME)
2221 def_stmt = SSA_NAME_DEF_STMT (op0);
2222 if (!is_gimple_assign (def_stmt))
2225 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
2227 tree defop0 = gimple_assign_rhs1 (def_stmt);
2228 tree type = TREE_TYPE (lhs);
2229 tree inside_type = TREE_TYPE (defop0);
2230 tree inter_type = TREE_TYPE (op0);
2231 int inside_int = INTEGRAL_TYPE_P (inside_type);
2232 int inside_ptr = POINTER_TYPE_P (inside_type);
2233 int inside_float = FLOAT_TYPE_P (inside_type);
2234 int inside_vec = TREE_CODE (inside_type) == VECTOR_TYPE;
2235 unsigned int inside_prec = TYPE_PRECISION (inside_type);
2236 int inside_unsignedp = TYPE_UNSIGNED (inside_type);
2237 int inter_int = INTEGRAL_TYPE_P (inter_type);
2238 int inter_ptr = POINTER_TYPE_P (inter_type);
2239 int inter_float = FLOAT_TYPE_P (inter_type);
2240 int inter_vec = TREE_CODE (inter_type) == VECTOR_TYPE;
2241 unsigned int inter_prec = TYPE_PRECISION (inter_type);
2242 int inter_unsignedp = TYPE_UNSIGNED (inter_type);
2243 int final_int = INTEGRAL_TYPE_P (type);
2244 int final_ptr = POINTER_TYPE_P (type);
2245 int final_float = FLOAT_TYPE_P (type);
2246 int final_vec = TREE_CODE (type) == VECTOR_TYPE;
2247 unsigned int final_prec = TYPE_PRECISION (type);
2248 int final_unsignedp = TYPE_UNSIGNED (type);
2250 /* In addition to the cases of two conversions in a row
2251 handled below, if we are converting something to its own
2252 type via an object of identical or wider precision, neither
2253 conversion is needed. */
2254 if (useless_type_conversion_p (type, inside_type)
2255 && (((inter_int || inter_ptr) && final_int)
2256 || (inter_float && final_float))
2257 && inter_prec >= final_prec)
2259 gimple_assign_set_rhs1 (stmt, unshare_expr (defop0));
2260 gimple_assign_set_rhs_code (stmt, TREE_CODE (defop0));
2265 /* Likewise, if the intermediate and initial types are either both
2266 float or both integer, we don't need the middle conversion if the
2267 former is wider than the latter and doesn't change the signedness
2268 (for integers). Avoid this if the final type is a pointer since
2269 then we sometimes need the middle conversion. Likewise if the
2270 final type has a precision not equal to the size of its mode. */
2271 if (((inter_int && inside_int)
2272 || (inter_float && inside_float)
2273 || (inter_vec && inside_vec))
2274 && inter_prec >= inside_prec
2275 && (inter_float || inter_vec
2276 || inter_unsignedp == inside_unsignedp)
2277 && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (type))
2278 && TYPE_MODE (type) == TYPE_MODE (inter_type))
2280 && (! final_vec || inter_prec == inside_prec))
2282 gimple_assign_set_rhs1 (stmt, defop0);
2287 /* If we have a sign-extension of a zero-extended value, we can
2288 replace that by a single zero-extension. */
2289 if (inside_int && inter_int && final_int
2290 && inside_prec < inter_prec && inter_prec < final_prec
2291 && inside_unsignedp && !inter_unsignedp)
2293 gimple_assign_set_rhs1 (stmt, defop0);
2298 /* Two conversions in a row are not needed unless:
2299 - some conversion is floating-point (overstrict for now), or
2300 - some conversion is a vector (overstrict for now), or
2301 - the intermediate type is narrower than both initial and
2303 - the intermediate type and innermost type differ in signedness,
2304 and the outermost type is wider than the intermediate, or
2305 - the initial type is a pointer type and the precisions of the
2306 intermediate and final types differ, or
2307 - the final type is a pointer type and the precisions of the
2308 initial and intermediate types differ. */
2309 if (! inside_float && ! inter_float && ! final_float
2310 && ! inside_vec && ! inter_vec && ! final_vec
2311 && (inter_prec >= inside_prec || inter_prec >= final_prec)
2312 && ! (inside_int && inter_int
2313 && inter_unsignedp != inside_unsignedp
2314 && inter_prec < final_prec)
2315 && ((inter_unsignedp && inter_prec > inside_prec)
2316 == (final_unsignedp && final_prec > inter_prec))
2317 && ! (inside_ptr && inter_prec != final_prec)
2318 && ! (final_ptr && inside_prec != inter_prec)
2319 && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (type))
2320 && TYPE_MODE (type) == TYPE_MODE (inter_type)))
2322 gimple_assign_set_rhs1 (stmt, defop0);
2327 /* A truncation to an unsigned type should be canonicalized as
2328 bitwise and of a mask. */
2329 if (final_int && inter_int && inside_int
2330 && final_prec == inside_prec
2331 && final_prec > inter_prec
2335 tem = fold_build2 (BIT_AND_EXPR, inside_type,
2338 (inside_type, double_int_mask (inter_prec)));
2339 if (!useless_type_conversion_p (type, inside_type))
2341 tem = force_gimple_operand_gsi (gsi, tem, true, NULL_TREE, true,
2343 gimple_assign_set_rhs1 (stmt, tem);
2346 gimple_assign_set_rhs_from_tree (gsi, tem);
2347 update_stmt (gsi_stmt (*gsi));
2355 /* Main entry point for the forward propagation and statement combine
2359 ssa_forward_propagate_and_combine (void)
2362 unsigned int todoflags = 0;
2364 cfg_changed = false;
2368 gimple_stmt_iterator gsi, prev;
2369 bool prev_initialized;
2371 /* Apply forward propagation to all stmts in the basic-block.
2372 Note we update GSI within the loop as necessary. */
2373 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2375 gimple stmt = gsi_stmt (gsi);
2377 enum tree_code code;
2379 if (!is_gimple_assign (stmt))
2385 lhs = gimple_assign_lhs (stmt);
2386 rhs = gimple_assign_rhs1 (stmt);
2387 code = gimple_assign_rhs_code (stmt);
2388 if (TREE_CODE (lhs) != SSA_NAME
2389 || has_zero_uses (lhs))
2395 /* If this statement sets an SSA_NAME to an address,
2396 try to propagate the address into the uses of the SSA_NAME. */
2397 if (code == ADDR_EXPR
2398 /* Handle pointer conversions on invariant addresses
2399 as well, as this is valid gimple. */
2400 || (CONVERT_EXPR_CODE_P (code)
2401 && TREE_CODE (rhs) == ADDR_EXPR
2402 && POINTER_TYPE_P (TREE_TYPE (lhs))))
2404 tree base = get_base_address (TREE_OPERAND (rhs, 0));
2407 || decl_address_invariant_p (base))
2408 && !stmt_references_abnormal_ssa_name (stmt)
2409 && forward_propagate_addr_expr (lhs, rhs))
2411 release_defs (stmt);
2412 todoflags |= TODO_remove_unused_locals;
2413 gsi_remove (&gsi, true);
2418 else if (code == POINTER_PLUS_EXPR && can_propagate_from (stmt))
2420 if (TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST
2421 /* ??? Better adjust the interface to that function
2422 instead of building new trees here. */
2423 && forward_propagate_addr_expr
2427 fold_build2 (MEM_REF,
2428 TREE_TYPE (TREE_TYPE (rhs)),
2432 gimple_assign_rhs2 (stmt))))))
2434 release_defs (stmt);
2435 todoflags |= TODO_remove_unused_locals;
2436 gsi_remove (&gsi, true);
2438 else if (is_gimple_min_invariant (rhs))
2440 /* Make sure to fold &a[0] + off_1 here. */
2441 fold_stmt_inplace (stmt);
2443 if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
2449 else if (TREE_CODE_CLASS (code) == tcc_comparison)
2451 forward_propagate_comparison (stmt);
2458 /* Combine stmts with the stmts defining their operands.
2459 Note we update GSI within the loop as necessary. */
2460 prev_initialized = false;
2461 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
2463 gimple stmt = gsi_stmt (gsi);
2464 bool changed = false;
2466 switch (gimple_code (stmt))
2470 tree rhs1 = gimple_assign_rhs1 (stmt);
2471 enum tree_code code = gimple_assign_rhs_code (stmt);
2473 if ((code == BIT_NOT_EXPR
2474 || code == NEGATE_EXPR)
2475 && TREE_CODE (rhs1) == SSA_NAME)
2476 changed = simplify_not_neg_expr (&gsi);
2477 else if (code == COND_EXPR)
2479 /* In this case the entire COND_EXPR is in rhs1. */
2481 fold_defer_overflow_warnings ();
2482 did_something = forward_propagate_into_cond (&gsi);
2483 stmt = gsi_stmt (gsi);
2484 if (did_something == 2)
2486 fold_undefer_overflow_warnings
2487 (!TREE_NO_WARNING (rhs1) && did_something, stmt,
2488 WARN_STRICT_OVERFLOW_CONDITIONAL);
2489 changed = did_something != 0;
2491 else if (TREE_CODE_CLASS (code) == tcc_comparison)
2493 bool no_warning = gimple_no_warning_p (stmt);
2494 fold_defer_overflow_warnings ();
2495 changed = forward_propagate_into_comparison (&gsi);
2496 fold_undefer_overflow_warnings
2497 (!no_warning && changed,
2498 stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
2500 else if (code == BIT_AND_EXPR
2501 || code == BIT_IOR_EXPR
2502 || code == BIT_XOR_EXPR)
2503 changed = simplify_bitwise_binary (&gsi);
2504 else if (code == PLUS_EXPR
2505 || code == MINUS_EXPR)
2506 changed = associate_plusminus (stmt);
2507 else if (CONVERT_EXPR_CODE_P (code)
2508 || code == FLOAT_EXPR
2509 || code == FIX_TRUNC_EXPR)
2510 changed = combine_conversions (&gsi);
2515 changed = simplify_gimple_switch (stmt);
2521 fold_defer_overflow_warnings ();
2522 did_something = forward_propagate_into_gimple_cond (stmt);
2523 if (did_something == 2)
2525 fold_undefer_overflow_warnings
2526 (did_something, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
2527 changed = did_something != 0;
2533 tree callee = gimple_call_fndecl (stmt);
2534 if (callee != NULL_TREE
2535 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
2536 changed = simplify_builtin_call (&gsi, callee);
2545 /* If the stmt changed then re-visit it and the statements
2546 inserted before it. */
2547 if (!prev_initialized)
2548 gsi = gsi_start_bb (bb);
2558 prev_initialized = true;
2565 todoflags |= TODO_cleanup_cfg;
2572 gate_forwprop (void)
2574 return flag_tree_forwprop;
2577 struct gimple_opt_pass pass_forwprop =
2581 "forwprop", /* name */
2582 gate_forwprop, /* gate */
2583 ssa_forward_propagate_and_combine, /* execute */
2586 0, /* static_pass_number */
2587 TV_TREE_FORWPROP, /* tv_id */
2588 PROP_cfg | PROP_ssa, /* properties_required */
2589 0, /* properties_provided */
2590 0, /* properties_destroyed */
2591 0, /* todo_flags_start */
2594 | TODO_verify_ssa /* todo_flags_finish */