1 /* Forward propagation of expressions for single use variables.
2 Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
27 #include "basic-block.h"
29 #include "gimple-pretty-print.h"
30 #include "tree-flow.h"
31 #include "tree-pass.h"
32 #include "tree-dump.h"
33 #include "langhooks.h"
38 /* This pass propagates the RHS of assignment statements into use
39 sites of the LHS of the assignment. It's basically a specialized
40 form of tree combination. It is hoped all of this can disappear
41 when we have a generalized tree combiner.
43 One class of common cases we handle is forward propagating a single use
44 variable into a COND_EXPR.
48 if (x) goto ... else goto ...
50 Will be transformed into:
53 if (a COND b) goto ... else goto ...
55 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
57 Or (assuming c1 and c2 are constants):
61 if (x EQ/NEQ c2) goto ... else goto ...
63 Will be transformed into:
66 if (a EQ/NEQ (c2 - c1)) goto ... else goto ...
68 Similarly for x = a - c1.
74 if (x) goto ... else goto ...
76 Will be transformed into:
79 if (a == 0) goto ... else goto ...
81 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
82 For these cases, we propagate A into all, possibly more than one,
83 COND_EXPRs that use X.
89 if (x) goto ... else goto ...
91 Will be transformed into:
94 if (a != 0) goto ... else goto ...
96 (Assuming a is an integral type and x is a boolean or x is an
97 integral and a is a boolean.)
99 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
100 For these cases, we propagate A into all, possibly more than one,
101 COND_EXPRs that use X.
103 In addition to eliminating the variable and the statement which assigns
104 a value to the variable, we may be able to later thread the jump without
105 adding insane complexity in the dominator optimizer.
107 Also note these transformations can cascade. We handle this by having
108 a worklist of COND_EXPR statements to examine. As we make a change to
109 a statement, we put it back on the worklist to examine on the next
110 iteration of the main loop.
112 A second class of propagation opportunities arises for ADDR_EXPR
123 ptr = (type1*)&type2var;
126 Will get turned into (if type1 and type2 are the same size
127 and neither have volatile on them):
128 res = VIEW_CONVERT_EXPR<type1>(type2var)
133 ptr2 = ptr + <constant>;
137 ptr2 = &x[constant/elementsize];
142 offset = index * element_size;
143 offset_p = (pointer) offset;
144 ptr2 = ptr + offset_p
146 Will get turned into:
154 Provided that decl has known alignment >= 2, will get turned into
158 We also propagate casts into SWITCH_EXPR and COND_EXPR conditions to
159 allow us to remove the cast and {NOT_EXPR,NEG_EXPR} into a subsequent
162 This will (of course) be extended as other needs arise. */
164 static bool forward_propagate_addr_expr (tree name, tree rhs);
166 /* Set to true if we delete EH edges during the optimization. */
167 static bool cfg_changed;
169 static tree rhs_to_tree (tree type, gimple stmt);
171 /* Get the next statement we can propagate NAME's value into skipping
172 trivial copies. Returns the statement that is suitable as a
173 propagation destination or NULL_TREE if there is no such one.
174 This only returns destinations in a single-use chain. FINAL_NAME_P
175 if non-NULL is written to the ssa name that represents the use. */
178 get_prop_dest_stmt (tree name, tree *final_name_p)
184 /* If name has multiple uses, bail out. */
185 if (!single_imm_use (name, &use, &use_stmt))
188 /* If this is not a trivial copy, we found it. */
189 if (!gimple_assign_ssa_name_copy_p (use_stmt)
190 || gimple_assign_rhs1 (use_stmt) != name)
193 /* Continue searching uses of the copy destination. */
194 name = gimple_assign_lhs (use_stmt);
198 *final_name_p = name;
203 /* Get the statement we can propagate from into NAME skipping
204 trivial copies. Returns the statement which defines the
205 propagation source or NULL_TREE if there is no such one.
206 If SINGLE_USE_ONLY is set considers only sources which have
207 a single use chain up to NAME. If SINGLE_USE_P is non-null,
208 it is set to whether the chain to NAME is a single use chain
209 or not. SINGLE_USE_P is not written to if SINGLE_USE_ONLY is set. */
212 get_prop_source_stmt (tree name, bool single_use_only, bool *single_use_p)
214 bool single_use = true;
217 gimple def_stmt = SSA_NAME_DEF_STMT (name);
219 if (!has_single_use (name))
226 /* If name is defined by a PHI node or is the default def, bail out. */
227 if (!is_gimple_assign (def_stmt))
230 /* If def_stmt is not a simple copy, we possibly found it. */
231 if (!gimple_assign_ssa_name_copy_p (def_stmt))
235 if (!single_use_only && single_use_p)
236 *single_use_p = single_use;
238 /* We can look through pointer conversions in the search
239 for a useful stmt for the comparison folding. */
240 rhs = gimple_assign_rhs1 (def_stmt);
241 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))
242 && TREE_CODE (rhs) == SSA_NAME
243 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (def_stmt)))
244 && POINTER_TYPE_P (TREE_TYPE (rhs)))
251 /* Continue searching the def of the copy source name. */
252 name = gimple_assign_rhs1 (def_stmt);
257 /* Checks if the destination ssa name in DEF_STMT can be used as
258 propagation source. Returns true if so, otherwise false. */
261 can_propagate_from (gimple def_stmt)
263 gcc_assert (is_gimple_assign (def_stmt));
265 /* If the rhs has side-effects we cannot propagate from it. */
266 if (gimple_has_volatile_ops (def_stmt))
269 /* If the rhs is a load we cannot propagate from it. */
270 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_reference
271 || TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_declaration)
274 /* Constants can be always propagated. */
275 if (gimple_assign_single_p (def_stmt)
276 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt)))
279 /* We cannot propagate ssa names that occur in abnormal phi nodes. */
280 if (stmt_references_abnormal_ssa_name (def_stmt))
283 /* If the definition is a conversion of a pointer to a function type,
284 then we can not apply optimizations as some targets require
285 function pointers to be canonicalized and in this case this
286 optimization could eliminate a necessary canonicalization. */
287 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
289 tree rhs = gimple_assign_rhs1 (def_stmt);
290 if (POINTER_TYPE_P (TREE_TYPE (rhs))
291 && TREE_CODE (TREE_TYPE (TREE_TYPE (rhs))) == FUNCTION_TYPE)
298 /* Remove a chain of dead statements starting at the definition of
299 NAME. The chain is linked via the first operand of the defining statements.
300 If NAME was replaced in its only use then this function can be used
301 to clean up dead stmts. The function handles already released SSA
303 Returns true if cleanup-cfg has to run. */
306 remove_prop_source_from_use (tree name)
308 gimple_stmt_iterator gsi;
310 bool cfg_changed = false;
315 if (SSA_NAME_IN_FREE_LIST (name)
316 || SSA_NAME_IS_DEFAULT_DEF (name)
317 || !has_zero_uses (name))
320 stmt = SSA_NAME_DEF_STMT (name);
321 if (gimple_code (stmt) == GIMPLE_PHI
322 || gimple_has_side_effects (stmt))
325 bb = gimple_bb (stmt);
326 gsi = gsi_for_stmt (stmt);
327 unlink_stmt_vdef (stmt);
328 gsi_remove (&gsi, true);
330 cfg_changed |= gimple_purge_dead_eh_edges (bb);
332 name = is_gimple_assign (stmt) ? gimple_assign_rhs1 (stmt) : NULL_TREE;
333 } while (name && TREE_CODE (name) == SSA_NAME);
338 /* Return the rhs of a gimple_assign STMT in a form of a single tree,
339 converted to type TYPE.
341 This should disappear, but is needed so we can combine expressions and use
342 the fold() interfaces. Long term, we need to develop folding and combine
343 routines that deal with gimple exclusively . */
346 rhs_to_tree (tree type, gimple stmt)
348 location_t loc = gimple_location (stmt);
349 enum tree_code code = gimple_assign_rhs_code (stmt);
350 if (get_gimple_rhs_class (code) == GIMPLE_TERNARY_RHS)
351 return fold_build3_loc (loc, code, type, gimple_assign_rhs1 (stmt),
352 gimple_assign_rhs2 (stmt),
353 gimple_assign_rhs3 (stmt));
354 else if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
355 return fold_build2_loc (loc, code, type, gimple_assign_rhs1 (stmt),
356 gimple_assign_rhs2 (stmt));
357 else if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
358 return build1 (code, type, gimple_assign_rhs1 (stmt));
359 else if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
360 return gimple_assign_rhs1 (stmt);
365 /* Combine OP0 CODE OP1 in the context of a COND_EXPR. Returns
366 the folded result in a form suitable for COND_EXPR_COND or
367 NULL_TREE, if there is no suitable simplified form. If
368 INVARIANT_ONLY is true only gimple_min_invariant results are
369 considered simplified. */
372 combine_cond_expr_cond (gimple stmt, enum tree_code code, tree type,
373 tree op0, tree op1, bool invariant_only)
377 gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
379 fold_defer_overflow_warnings ();
380 t = fold_binary_loc (gimple_location (stmt), code, type, op0, op1);
383 fold_undefer_overflow_warnings (false, NULL, 0);
387 /* Require that we got a boolean type out if we put one in. */
388 gcc_assert (TREE_CODE (TREE_TYPE (t)) == TREE_CODE (type));
390 /* Canonicalize the combined condition for use in a COND_EXPR. */
391 t = canonicalize_cond_expr_cond (t);
393 /* Bail out if we required an invariant but didn't get one. */
394 if (!t || (invariant_only && !is_gimple_min_invariant (t)))
396 fold_undefer_overflow_warnings (false, NULL, 0);
400 fold_undefer_overflow_warnings (!gimple_no_warning_p (stmt), stmt, 0);
405 /* Combine the comparison OP0 CODE OP1 at LOC with the defining statements
406 of its operand. Return a new comparison tree or NULL_TREE if there
407 were no simplifying combines. */
410 forward_propagate_into_comparison_1 (gimple stmt,
411 enum tree_code code, tree type,
414 tree tmp = NULL_TREE;
415 tree rhs0 = NULL_TREE, rhs1 = NULL_TREE;
416 bool single_use0_p = false, single_use1_p = false;
418 /* For comparisons use the first operand, that is likely to
419 simplify comparisons against constants. */
420 if (TREE_CODE (op0) == SSA_NAME)
422 gimple def_stmt = get_prop_source_stmt (op0, false, &single_use0_p);
423 if (def_stmt && can_propagate_from (def_stmt))
425 rhs0 = rhs_to_tree (TREE_TYPE (op1), def_stmt);
426 tmp = combine_cond_expr_cond (stmt, code, type,
427 rhs0, op1, !single_use0_p);
433 /* If that wasn't successful, try the second operand. */
434 if (TREE_CODE (op1) == SSA_NAME)
436 gimple def_stmt = get_prop_source_stmt (op1, false, &single_use1_p);
437 if (def_stmt && can_propagate_from (def_stmt))
439 rhs1 = rhs_to_tree (TREE_TYPE (op0), def_stmt);
440 tmp = combine_cond_expr_cond (stmt, code, type,
441 op0, rhs1, !single_use1_p);
447 /* If that wasn't successful either, try both operands. */
448 if (rhs0 != NULL_TREE
449 && rhs1 != NULL_TREE)
450 tmp = combine_cond_expr_cond (stmt, code, type,
452 !(single_use0_p && single_use1_p));
457 /* Propagate from the ssa name definition statements of the assignment
458 from a comparison at *GSI into the conditional if that simplifies it.
459 Returns 1 if the stmt was modified and 2 if the CFG needs cleanup,
460 otherwise returns 0. */
463 forward_propagate_into_comparison (gimple_stmt_iterator *gsi)
465 gimple stmt = gsi_stmt (*gsi);
467 bool cfg_changed = false;
468 tree type = TREE_TYPE (gimple_assign_lhs (stmt));
469 tree rhs1 = gimple_assign_rhs1 (stmt);
470 tree rhs2 = gimple_assign_rhs2 (stmt);
472 /* Combine the comparison with defining statements. */
473 tmp = forward_propagate_into_comparison_1 (stmt,
474 gimple_assign_rhs_code (stmt),
476 if (tmp && useless_type_conversion_p (type, TREE_TYPE (tmp)))
478 gimple_assign_set_rhs_from_tree (gsi, tmp);
480 update_stmt (gsi_stmt (*gsi));
482 if (TREE_CODE (rhs1) == SSA_NAME)
483 cfg_changed |= remove_prop_source_from_use (rhs1);
484 if (TREE_CODE (rhs2) == SSA_NAME)
485 cfg_changed |= remove_prop_source_from_use (rhs2);
486 return cfg_changed ? 2 : 1;
492 /* Propagate from the ssa name definition statements of COND_EXPR
493 in GIMPLE_COND statement STMT into the conditional if that simplifies it.
494 Returns zero if no statement was changed, one if there were
495 changes and two if cfg_cleanup needs to run.
497 This must be kept in sync with forward_propagate_into_cond. */
500 forward_propagate_into_gimple_cond (gimple stmt)
503 enum tree_code code = gimple_cond_code (stmt);
504 bool cfg_changed = false;
505 tree rhs1 = gimple_cond_lhs (stmt);
506 tree rhs2 = gimple_cond_rhs (stmt);
508 /* We can do tree combining on SSA_NAME and comparison expressions. */
509 if (TREE_CODE_CLASS (gimple_cond_code (stmt)) != tcc_comparison)
512 tmp = forward_propagate_into_comparison_1 (stmt, code,
517 if (dump_file && tmp)
519 fprintf (dump_file, " Replaced '");
520 print_gimple_expr (dump_file, stmt, 0, 0);
521 fprintf (dump_file, "' with '");
522 print_generic_expr (dump_file, tmp, 0);
523 fprintf (dump_file, "'\n");
526 gimple_cond_set_condition_from_tree (stmt, unshare_expr (tmp));
529 if (TREE_CODE (rhs1) == SSA_NAME)
530 cfg_changed |= remove_prop_source_from_use (rhs1);
531 if (TREE_CODE (rhs2) == SSA_NAME)
532 cfg_changed |= remove_prop_source_from_use (rhs2);
533 return (cfg_changed || is_gimple_min_invariant (tmp)) ? 2 : 1;
536 /* Canonicalize _Bool == 0 and _Bool != 1 to _Bool != 0 by swapping edges. */
537 if ((TREE_CODE (TREE_TYPE (rhs1)) == BOOLEAN_TYPE
538 || (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
539 && TYPE_PRECISION (TREE_TYPE (rhs1)) == 1))
541 && integer_zerop (rhs2))
543 && integer_onep (rhs2))))
545 basic_block bb = gimple_bb (stmt);
546 gimple_cond_set_code (stmt, NE_EXPR);
547 gimple_cond_set_rhs (stmt, build_zero_cst (TREE_TYPE (rhs1)));
548 EDGE_SUCC (bb, 0)->flags ^= (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
549 EDGE_SUCC (bb, 1)->flags ^= (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
557 /* Propagate from the ssa name definition statements of COND_EXPR
558 in the rhs of statement STMT into the conditional if that simplifies it.
559 Returns true zero if the stmt was changed. */
562 forward_propagate_into_cond (gimple_stmt_iterator *gsi_p)
564 gimple stmt = gsi_stmt (*gsi_p);
565 tree tmp = NULL_TREE;
566 tree cond = gimple_assign_rhs1 (stmt);
569 /* We can do tree combining on SSA_NAME and comparison expressions. */
570 if (COMPARISON_CLASS_P (cond))
571 tmp = forward_propagate_into_comparison_1 (stmt, TREE_CODE (cond),
573 TREE_OPERAND (cond, 0),
574 TREE_OPERAND (cond, 1));
575 else if (TREE_CODE (cond) == SSA_NAME)
579 gimple def_stmt = get_prop_source_stmt (name, true, NULL);
580 if (!def_stmt || !can_propagate_from (def_stmt))
583 code = gimple_assign_rhs_code (def_stmt);
584 if (TREE_CODE_CLASS (code) == tcc_comparison)
585 tmp = fold_build2_loc (gimple_location (def_stmt),
588 gimple_assign_rhs1 (def_stmt),
589 gimple_assign_rhs2 (def_stmt));
590 else if ((code == BIT_NOT_EXPR
591 && TYPE_PRECISION (TREE_TYPE (cond)) == 1)
592 || (code == BIT_XOR_EXPR
593 && integer_onep (gimple_assign_rhs2 (def_stmt))))
595 tmp = gimple_assign_rhs1 (def_stmt);
601 && is_gimple_condexpr (tmp))
603 if (dump_file && tmp)
605 fprintf (dump_file, " Replaced '");
606 print_generic_expr (dump_file, cond, 0);
607 fprintf (dump_file, "' with '");
608 print_generic_expr (dump_file, tmp, 0);
609 fprintf (dump_file, "'\n");
612 if (integer_onep (tmp))
613 gimple_assign_set_rhs_from_tree (gsi_p, gimple_assign_rhs2 (stmt));
614 else if (integer_zerop (tmp))
615 gimple_assign_set_rhs_from_tree (gsi_p, gimple_assign_rhs3 (stmt));
618 gimple_assign_set_rhs1 (stmt, unshare_expr (tmp));
621 tree t = gimple_assign_rhs2 (stmt);
622 gimple_assign_set_rhs2 (stmt, gimple_assign_rhs3 (stmt));
623 gimple_assign_set_rhs3 (stmt, t);
626 stmt = gsi_stmt (*gsi_p);
635 /* We've just substituted an ADDR_EXPR into stmt. Update all the
636 relevant data structures to match. */
639 tidy_after_forward_propagate_addr (gimple stmt)
641 /* We may have turned a trapping insn into a non-trapping insn. */
642 if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
643 && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
646 if (TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR)
647 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt));
650 /* DEF_RHS contains the address of the 0th element in an array.
651 USE_STMT uses type of DEF_RHS to compute the address of an
652 arbitrary element within the array. The (variable) byte offset
653 of the element is contained in OFFSET.
655 We walk back through the use-def chains of OFFSET to verify that
656 it is indeed computing the offset of an element within the array
657 and extract the index corresponding to the given byte offset.
659 We then try to fold the entire address expression into a form
662 If we are successful, we replace the right hand side of USE_STMT
663 with the new address computation. */
666 forward_propagate_addr_into_variable_array_index (tree offset,
668 gimple_stmt_iterator *use_stmt_gsi)
671 gimple offset_def, use_stmt = gsi_stmt (*use_stmt_gsi);
674 if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == ARRAY_REF)
675 tunit = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (def_rhs)));
676 else if (TREE_CODE (TREE_TYPE (TREE_OPERAND (def_rhs, 0))) == ARRAY_TYPE)
677 tunit = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (TREE_TYPE (def_rhs))));
680 if (!host_integerp (tunit, 1))
683 /* Get the offset's defining statement. */
684 offset_def = SSA_NAME_DEF_STMT (offset);
686 /* Try to find an expression for a proper index. This is either a
687 multiplication expression by the element size or just the ssa name we came
688 along in case the element size is one. In that case, however, we do not
689 allow multiplications because they can be computing index to a higher
690 level dimension (PR 37861). */
691 if (integer_onep (tunit))
693 if (is_gimple_assign (offset_def)
694 && gimple_assign_rhs_code (offset_def) == MULT_EXPR)
701 /* The statement which defines OFFSET before type conversion
702 must be a simple GIMPLE_ASSIGN. */
703 if (!is_gimple_assign (offset_def))
706 /* The RHS of the statement which defines OFFSET must be a
707 multiplication of an object by the size of the array elements.
708 This implicitly verifies that the size of the array elements
710 if (gimple_assign_rhs_code (offset_def) == MULT_EXPR
711 && TREE_CODE (gimple_assign_rhs2 (offset_def)) == INTEGER_CST
712 && tree_int_cst_equal (gimple_assign_rhs2 (offset_def), tunit))
714 /* The first operand to the MULT_EXPR is the desired index. */
715 index = gimple_assign_rhs1 (offset_def);
717 /* If we have idx * tunit + CST * tunit re-associate that. */
718 else if ((gimple_assign_rhs_code (offset_def) == PLUS_EXPR
719 || gimple_assign_rhs_code (offset_def) == MINUS_EXPR)
720 && TREE_CODE (gimple_assign_rhs1 (offset_def)) == SSA_NAME
721 && TREE_CODE (gimple_assign_rhs2 (offset_def)) == INTEGER_CST
722 && (tmp = div_if_zero_remainder (EXACT_DIV_EXPR,
723 gimple_assign_rhs2 (offset_def),
724 tunit)) != NULL_TREE)
726 gimple offset_def2 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (offset_def));
727 if (is_gimple_assign (offset_def2)
728 && gimple_assign_rhs_code (offset_def2) == MULT_EXPR
729 && TREE_CODE (gimple_assign_rhs2 (offset_def2)) == INTEGER_CST
730 && tree_int_cst_equal (gimple_assign_rhs2 (offset_def2), tunit))
732 index = fold_build2 (gimple_assign_rhs_code (offset_def),
734 gimple_assign_rhs1 (offset_def2), tmp);
743 /* Replace the pointer addition with array indexing. */
744 index = force_gimple_operand_gsi (use_stmt_gsi, index, true, NULL_TREE,
745 true, GSI_SAME_STMT);
746 if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == ARRAY_REF)
748 new_rhs = unshare_expr (def_rhs);
749 TREE_OPERAND (TREE_OPERAND (new_rhs, 0), 1) = index;
753 new_rhs = build4 (ARRAY_REF, TREE_TYPE (TREE_TYPE (TREE_TYPE (def_rhs))),
754 unshare_expr (TREE_OPERAND (def_rhs, 0)),
755 index, integer_zero_node, NULL_TREE);
756 new_rhs = build_fold_addr_expr (new_rhs);
757 if (!useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (use_stmt)),
758 TREE_TYPE (new_rhs)))
760 new_rhs = force_gimple_operand_gsi (use_stmt_gsi, new_rhs, true,
761 NULL_TREE, true, GSI_SAME_STMT);
762 new_rhs = fold_convert (TREE_TYPE (gimple_assign_lhs (use_stmt)),
766 gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs);
767 fold_stmt (use_stmt_gsi);
768 tidy_after_forward_propagate_addr (gsi_stmt (*use_stmt_gsi));
772 /* NAME is a SSA_NAME representing DEF_RHS which is of the form
773 ADDR_EXPR <whatever>.
775 Try to forward propagate the ADDR_EXPR into the use USE_STMT.
776 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
777 node or for recovery of array indexing from pointer arithmetic.
779 Return true if the propagation was successful (the propagation can
780 be not totally successful, yet things may have been changed). */
783 forward_propagate_addr_expr_1 (tree name, tree def_rhs,
784 gimple_stmt_iterator *use_stmt_gsi,
787 tree lhs, rhs, rhs2, array_ref;
788 gimple use_stmt = gsi_stmt (*use_stmt_gsi);
789 enum tree_code rhs_code;
792 gcc_assert (TREE_CODE (def_rhs) == ADDR_EXPR);
794 lhs = gimple_assign_lhs (use_stmt);
795 rhs_code = gimple_assign_rhs_code (use_stmt);
796 rhs = gimple_assign_rhs1 (use_stmt);
798 /* Trivial cases. The use statement could be a trivial copy or a
799 useless conversion. Recurse to the uses of the lhs as copyprop does
800 not copy through different variant pointers and FRE does not catch
801 all useless conversions. Treat the case of a single-use name and
802 a conversion to def_rhs type separate, though. */
803 if (TREE_CODE (lhs) == SSA_NAME
804 && ((rhs_code == SSA_NAME && rhs == name)
805 || CONVERT_EXPR_CODE_P (rhs_code)))
807 /* Only recurse if we don't deal with a single use or we cannot
808 do the propagation to the current statement. In particular
809 we can end up with a conversion needed for a non-invariant
810 address which we cannot do in a single statement. */
812 || (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs))
813 && (!is_gimple_min_invariant (def_rhs)
814 || (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
815 && POINTER_TYPE_P (TREE_TYPE (def_rhs))
816 && (TYPE_PRECISION (TREE_TYPE (lhs))
817 > TYPE_PRECISION (TREE_TYPE (def_rhs)))))))
818 return forward_propagate_addr_expr (lhs, def_rhs);
820 gimple_assign_set_rhs1 (use_stmt, unshare_expr (def_rhs));
821 if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
822 gimple_assign_set_rhs_code (use_stmt, TREE_CODE (def_rhs));
824 gimple_assign_set_rhs_code (use_stmt, NOP_EXPR);
828 /* Propagate through constant pointer adjustments. */
829 if (TREE_CODE (lhs) == SSA_NAME
830 && rhs_code == POINTER_PLUS_EXPR
832 && TREE_CODE (gimple_assign_rhs2 (use_stmt)) == INTEGER_CST)
835 /* As we come here with non-invariant addresses in def_rhs we need
836 to make sure we can build a valid constant offsetted address
837 for further propagation. Simply rely on fold building that
838 and check after the fact. */
839 new_def_rhs = fold_build2 (MEM_REF, TREE_TYPE (TREE_TYPE (rhs)),
841 fold_convert (ptr_type_node,
842 gimple_assign_rhs2 (use_stmt)));
843 if (TREE_CODE (new_def_rhs) == MEM_REF
844 && !is_gimple_mem_ref_addr (TREE_OPERAND (new_def_rhs, 0)))
846 new_def_rhs = build_fold_addr_expr_with_type (new_def_rhs,
849 /* Recurse. If we could propagate into all uses of lhs do not
850 bother to replace into the current use but just pretend we did. */
851 if (TREE_CODE (new_def_rhs) == ADDR_EXPR
852 && forward_propagate_addr_expr (lhs, new_def_rhs))
855 if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (new_def_rhs)))
856 gimple_assign_set_rhs_with_ops (use_stmt_gsi, TREE_CODE (new_def_rhs),
857 new_def_rhs, NULL_TREE);
858 else if (is_gimple_min_invariant (new_def_rhs))
859 gimple_assign_set_rhs_with_ops (use_stmt_gsi, NOP_EXPR,
860 new_def_rhs, NULL_TREE);
863 gcc_assert (gsi_stmt (*use_stmt_gsi) == use_stmt);
864 update_stmt (use_stmt);
868 /* Now strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
869 ADDR_EXPR will not appear on the LHS. */
870 lhs = gimple_assign_lhs (use_stmt);
871 while (handled_component_p (lhs))
872 lhs = TREE_OPERAND (lhs, 0);
874 /* Now see if the LHS node is a MEM_REF using NAME. If so,
875 propagate the ADDR_EXPR into the use of NAME and fold the result. */
876 if (TREE_CODE (lhs) == MEM_REF
877 && TREE_OPERAND (lhs, 0) == name)
880 HOST_WIDE_INT def_rhs_offset;
881 /* If the address is invariant we can always fold it. */
882 if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0),
885 double_int off = mem_ref_offset (lhs);
887 off = double_int_add (off,
888 shwi_to_double_int (def_rhs_offset));
889 if (TREE_CODE (def_rhs_base) == MEM_REF)
891 off = double_int_add (off, mem_ref_offset (def_rhs_base));
892 new_ptr = TREE_OPERAND (def_rhs_base, 0);
895 new_ptr = build_fold_addr_expr (def_rhs_base);
896 TREE_OPERAND (lhs, 0) = new_ptr;
897 TREE_OPERAND (lhs, 1)
898 = double_int_to_tree (TREE_TYPE (TREE_OPERAND (lhs, 1)), off);
899 tidy_after_forward_propagate_addr (use_stmt);
900 /* Continue propagating into the RHS if this was not the only use. */
904 /* If the LHS is a plain dereference and the value type is the same as
905 that of the pointed-to type of the address we can put the
906 dereferenced address on the LHS preserving the original alias-type. */
907 else if (gimple_assign_lhs (use_stmt) == lhs
908 && useless_type_conversion_p
909 (TREE_TYPE (TREE_OPERAND (def_rhs, 0)),
910 TREE_TYPE (gimple_assign_rhs1 (use_stmt))))
912 tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0);
913 tree new_offset, new_base, saved, new_lhs;
914 while (handled_component_p (*def_rhs_basep))
915 def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0);
916 saved = *def_rhs_basep;
917 if (TREE_CODE (*def_rhs_basep) == MEM_REF)
919 new_base = TREE_OPERAND (*def_rhs_basep, 0);
921 = int_const_binop (PLUS_EXPR, TREE_OPERAND (lhs, 1),
922 TREE_OPERAND (*def_rhs_basep, 1));
926 new_base = build_fold_addr_expr (*def_rhs_basep);
927 new_offset = TREE_OPERAND (lhs, 1);
929 *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep),
930 new_base, new_offset);
931 TREE_THIS_VOLATILE (*def_rhs_basep) = TREE_THIS_VOLATILE (lhs);
932 TREE_THIS_NOTRAP (*def_rhs_basep) = TREE_THIS_NOTRAP (lhs);
933 new_lhs = unshare_expr (TREE_OPERAND (def_rhs, 0));
934 gimple_assign_set_lhs (use_stmt, new_lhs);
935 TREE_THIS_VOLATILE (new_lhs) = TREE_THIS_VOLATILE (lhs);
936 *def_rhs_basep = saved;
937 tidy_after_forward_propagate_addr (use_stmt);
938 /* Continue propagating into the RHS if this was not the
944 /* We can have a struct assignment dereferencing our name twice.
945 Note that we didn't propagate into the lhs to not falsely
946 claim we did when propagating into the rhs. */
950 /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
951 nodes from the RHS. */
952 rhs = gimple_assign_rhs1 (use_stmt);
953 if (TREE_CODE (rhs) == ADDR_EXPR)
954 rhs = TREE_OPERAND (rhs, 0);
955 while (handled_component_p (rhs))
956 rhs = TREE_OPERAND (rhs, 0);
958 /* Now see if the RHS node is a MEM_REF using NAME. If so,
959 propagate the ADDR_EXPR into the use of NAME and fold the result. */
960 if (TREE_CODE (rhs) == MEM_REF
961 && TREE_OPERAND (rhs, 0) == name)
964 HOST_WIDE_INT def_rhs_offset;
965 if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0),
968 double_int off = mem_ref_offset (rhs);
970 off = double_int_add (off,
971 shwi_to_double_int (def_rhs_offset));
972 if (TREE_CODE (def_rhs_base) == MEM_REF)
974 off = double_int_add (off, mem_ref_offset (def_rhs_base));
975 new_ptr = TREE_OPERAND (def_rhs_base, 0);
978 new_ptr = build_fold_addr_expr (def_rhs_base);
979 TREE_OPERAND (rhs, 0) = new_ptr;
980 TREE_OPERAND (rhs, 1)
981 = double_int_to_tree (TREE_TYPE (TREE_OPERAND (rhs, 1)), off);
982 fold_stmt_inplace (use_stmt_gsi);
983 tidy_after_forward_propagate_addr (use_stmt);
986 /* If the RHS is a plain dereference and the value type is the same as
987 that of the pointed-to type of the address we can put the
988 dereferenced address on the RHS preserving the original alias-type. */
989 else if (gimple_assign_rhs1 (use_stmt) == rhs
990 && useless_type_conversion_p
991 (TREE_TYPE (gimple_assign_lhs (use_stmt)),
992 TREE_TYPE (TREE_OPERAND (def_rhs, 0))))
994 tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0);
995 tree new_offset, new_base, saved, new_rhs;
996 while (handled_component_p (*def_rhs_basep))
997 def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0);
998 saved = *def_rhs_basep;
999 if (TREE_CODE (*def_rhs_basep) == MEM_REF)
1001 new_base = TREE_OPERAND (*def_rhs_basep, 0);
1003 = int_const_binop (PLUS_EXPR, TREE_OPERAND (rhs, 1),
1004 TREE_OPERAND (*def_rhs_basep, 1));
1008 new_base = build_fold_addr_expr (*def_rhs_basep);
1009 new_offset = TREE_OPERAND (rhs, 1);
1011 *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep),
1012 new_base, new_offset);
1013 TREE_THIS_VOLATILE (*def_rhs_basep) = TREE_THIS_VOLATILE (rhs);
1014 TREE_THIS_NOTRAP (*def_rhs_basep) = TREE_THIS_NOTRAP (rhs);
1015 new_rhs = unshare_expr (TREE_OPERAND (def_rhs, 0));
1016 gimple_assign_set_rhs1 (use_stmt, new_rhs);
1017 TREE_THIS_VOLATILE (new_rhs) = TREE_THIS_VOLATILE (rhs);
1018 *def_rhs_basep = saved;
1019 fold_stmt_inplace (use_stmt_gsi);
1020 tidy_after_forward_propagate_addr (use_stmt);
1025 /* If the use of the ADDR_EXPR is not a POINTER_PLUS_EXPR, there
1026 is nothing to do. */
1027 if (gimple_assign_rhs_code (use_stmt) != POINTER_PLUS_EXPR
1028 || gimple_assign_rhs1 (use_stmt) != name)
1031 /* The remaining cases are all for turning pointer arithmetic into
1032 array indexing. They only apply when we have the address of
1033 element zero in an array. If that is not the case then there
1034 is nothing to do. */
1035 array_ref = TREE_OPERAND (def_rhs, 0);
1036 if ((TREE_CODE (array_ref) != ARRAY_REF
1037 || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE
1038 || TREE_CODE (TREE_OPERAND (array_ref, 1)) != INTEGER_CST)
1039 && TREE_CODE (TREE_TYPE (array_ref)) != ARRAY_TYPE)
1042 rhs2 = gimple_assign_rhs2 (use_stmt);
1043 /* Optimize &x[C1] p+ C2 to &x p+ C3 with C3 = C1 * element_size + C2. */
1044 if (TREE_CODE (rhs2) == INTEGER_CST)
1046 tree new_rhs = build1_loc (gimple_location (use_stmt),
1047 ADDR_EXPR, TREE_TYPE (def_rhs),
1048 fold_build2 (MEM_REF,
1049 TREE_TYPE (TREE_TYPE (def_rhs)),
1050 unshare_expr (def_rhs),
1051 fold_convert (ptr_type_node,
1053 gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs);
1054 use_stmt = gsi_stmt (*use_stmt_gsi);
1055 update_stmt (use_stmt);
1056 tidy_after_forward_propagate_addr (use_stmt);
1060 /* Try to optimize &x[0] p+ OFFSET where OFFSET is defined by
1061 converting a multiplication of an index by the size of the
1062 array elements, then the result is converted into the proper
1063 type for the arithmetic. */
1064 if (TREE_CODE (rhs2) == SSA_NAME
1065 && (TREE_CODE (array_ref) != ARRAY_REF
1066 || integer_zerop (TREE_OPERAND (array_ref, 1)))
1067 && useless_type_conversion_p (TREE_TYPE (name), TREE_TYPE (def_rhs))
1068 /* Avoid problems with IVopts creating PLUS_EXPRs with a
1069 different type than their operands. */
1070 && useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
1071 return forward_propagate_addr_into_variable_array_index (rhs2, def_rhs,
1076 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
1078 Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME.
1079 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
1080 node or for recovery of array indexing from pointer arithmetic.
1081 Returns true, if all uses have been propagated into. */
1084 forward_propagate_addr_expr (tree name, tree rhs)
1086 int stmt_loop_depth = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_depth;
1087 imm_use_iterator iter;
1090 bool single_use_p = has_single_use (name);
1092 FOR_EACH_IMM_USE_STMT (use_stmt, iter, name)
1097 /* If the use is not in a simple assignment statement, then
1098 there is nothing we can do. */
1099 if (gimple_code (use_stmt) != GIMPLE_ASSIGN)
1101 if (!is_gimple_debug (use_stmt))
1106 /* If the use is in a deeper loop nest, then we do not want
1107 to propagate non-invariant ADDR_EXPRs into the loop as that
1108 is likely adding expression evaluations into the loop. */
1109 if (gimple_bb (use_stmt)->loop_depth > stmt_loop_depth
1110 && !is_gimple_min_invariant (rhs))
1117 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1118 result = forward_propagate_addr_expr_1 (name, rhs, &gsi,
1120 /* If the use has moved to a different statement adjust
1121 the update machinery for the old statement too. */
1122 if (use_stmt != gsi_stmt (gsi))
1124 update_stmt (use_stmt);
1125 use_stmt = gsi_stmt (gsi);
1128 update_stmt (use_stmt);
1132 /* Remove intermediate now unused copy and conversion chains. */
1133 use_rhs = gimple_assign_rhs1 (use_stmt);
1135 && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
1136 && TREE_CODE (use_rhs) == SSA_NAME
1137 && has_zero_uses (gimple_assign_lhs (use_stmt)))
1139 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1140 release_defs (use_stmt);
1141 gsi_remove (&gsi, true);
1145 return all && has_zero_uses (name);
1149 /* Forward propagate the comparison defined in STMT like
1150 cond_1 = x CMP y to uses of the form
1154 Returns true if stmt is now unused. */
1157 forward_propagate_comparison (gimple stmt)
1159 tree name = gimple_assign_lhs (stmt);
1161 tree tmp = NULL_TREE;
1162 gimple_stmt_iterator gsi;
1163 enum tree_code code;
1166 /* Don't propagate ssa names that occur in abnormal phis. */
1167 if ((TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
1168 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)))
1169 || (TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME
1170 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs2 (stmt))))
1173 /* Do not un-cse comparisons. But propagate through copies. */
1174 use_stmt = get_prop_dest_stmt (name, &name);
1176 || !is_gimple_assign (use_stmt))
1179 code = gimple_assign_rhs_code (use_stmt);
1180 lhs = gimple_assign_lhs (use_stmt);
1181 if (!INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
1184 /* We can propagate the condition into a statement that
1185 computes the logical negation of the comparison result. */
1186 if ((code == BIT_NOT_EXPR
1187 && TYPE_PRECISION (TREE_TYPE (lhs)) == 1)
1188 || (code == BIT_XOR_EXPR
1189 && integer_onep (gimple_assign_rhs2 (use_stmt))))
1191 tree type = TREE_TYPE (gimple_assign_rhs1 (stmt));
1192 bool nans = HONOR_NANS (TYPE_MODE (type));
1193 enum tree_code inv_code;
1194 inv_code = invert_tree_comparison (gimple_assign_rhs_code (stmt), nans);
1195 if (inv_code == ERROR_MARK)
1198 tmp = build2 (inv_code, TREE_TYPE (lhs), gimple_assign_rhs1 (stmt),
1199 gimple_assign_rhs2 (stmt));
1204 gsi = gsi_for_stmt (use_stmt);
1205 gimple_assign_set_rhs_from_tree (&gsi, unshare_expr (tmp));
1206 use_stmt = gsi_stmt (gsi);
1207 update_stmt (use_stmt);
1209 if (dump_file && (dump_flags & TDF_DETAILS))
1211 fprintf (dump_file, " Replaced '");
1212 print_gimple_expr (dump_file, stmt, 0, dump_flags);
1213 fprintf (dump_file, "' with '");
1214 print_gimple_expr (dump_file, use_stmt, 0, dump_flags);
1215 fprintf (dump_file, "'\n");
1218 /* Remove defining statements. */
1219 return remove_prop_source_from_use (name);
1223 /* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y.
1224 If so, we can change STMT into lhs = y which can later be copy
1225 propagated. Similarly for negation.
1227 This could trivially be formulated as a forward propagation
1228 to immediate uses. However, we already had an implementation
1229 from DOM which used backward propagation via the use-def links.
1231 It turns out that backward propagation is actually faster as
1232 there's less work to do for each NOT/NEG expression we find.
1233 Backwards propagation needs to look at the statement in a single
1234 backlink. Forward propagation needs to look at potentially more
1235 than one forward link.
1237 Returns true when the statement was changed. */
1240 simplify_not_neg_expr (gimple_stmt_iterator *gsi_p)
1242 gimple stmt = gsi_stmt (*gsi_p);
1243 tree rhs = gimple_assign_rhs1 (stmt);
1244 gimple rhs_def_stmt = SSA_NAME_DEF_STMT (rhs);
1246 /* See if the RHS_DEF_STMT has the same form as our statement. */
1247 if (is_gimple_assign (rhs_def_stmt)
1248 && gimple_assign_rhs_code (rhs_def_stmt) == gimple_assign_rhs_code (stmt))
1250 tree rhs_def_operand = gimple_assign_rhs1 (rhs_def_stmt);
1252 /* Verify that RHS_DEF_OPERAND is a suitable SSA_NAME. */
1253 if (TREE_CODE (rhs_def_operand) == SSA_NAME
1254 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand))
1256 gimple_assign_set_rhs_from_tree (gsi_p, rhs_def_operand);
1257 stmt = gsi_stmt (*gsi_p);
1266 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
1267 the condition which we may be able to optimize better. */
1270 simplify_gimple_switch (gimple stmt)
1272 tree cond = gimple_switch_index (stmt);
1276 /* The optimization that we really care about is removing unnecessary
1277 casts. That will let us do much better in propagating the inferred
1278 constant at the switch target. */
1279 if (TREE_CODE (cond) == SSA_NAME)
1281 def_stmt = SSA_NAME_DEF_STMT (cond);
1282 if (is_gimple_assign (def_stmt))
1284 if (gimple_assign_rhs_code (def_stmt) == NOP_EXPR)
1289 def = gimple_assign_rhs1 (def_stmt);
1291 /* ??? Why was Jeff testing this? We are gimple... */
1292 gcc_checking_assert (is_gimple_val (def));
1294 to = TREE_TYPE (cond);
1295 ti = TREE_TYPE (def);
1297 /* If we have an extension that preserves value, then we
1298 can copy the source value into the switch. */
1300 need_precision = TYPE_PRECISION (ti);
1302 if (! INTEGRAL_TYPE_P (ti))
1304 else if (TYPE_UNSIGNED (to) && !TYPE_UNSIGNED (ti))
1306 else if (!TYPE_UNSIGNED (to) && TYPE_UNSIGNED (ti))
1307 need_precision += 1;
1308 if (TYPE_PRECISION (to) < need_precision)
1313 gimple_switch_set_index (stmt, def);
1324 /* For pointers p2 and p1 return p2 - p1 if the
1325 difference is known and constant, otherwise return NULL. */
1328 constant_pointer_difference (tree p1, tree p2)
1331 #define CPD_ITERATIONS 5
1332 tree exps[2][CPD_ITERATIONS];
1333 tree offs[2][CPD_ITERATIONS];
1336 for (i = 0; i < 2; i++)
1338 tree p = i ? p1 : p2;
1339 tree off = size_zero_node;
1341 enum tree_code code;
1343 /* For each of p1 and p2 we need to iterate at least
1344 twice, to handle ADDR_EXPR directly in p1/p2,
1345 SSA_NAME with ADDR_EXPR or POINTER_PLUS_EXPR etc.
1346 on definition's stmt RHS. Iterate a few extra times. */
1350 if (!POINTER_TYPE_P (TREE_TYPE (p)))
1352 if (TREE_CODE (p) == ADDR_EXPR)
1354 tree q = TREE_OPERAND (p, 0);
1355 HOST_WIDE_INT offset;
1356 tree base = get_addr_base_and_unit_offset (q, &offset);
1361 off = size_binop (PLUS_EXPR, off, size_int (offset));
1363 if (TREE_CODE (q) == MEM_REF
1364 && TREE_CODE (TREE_OPERAND (q, 0)) == SSA_NAME)
1366 p = TREE_OPERAND (q, 0);
1367 off = size_binop (PLUS_EXPR, off,
1368 double_int_to_tree (sizetype,
1369 mem_ref_offset (q)));
1378 if (TREE_CODE (p) != SSA_NAME)
1382 if (j == CPD_ITERATIONS)
1384 stmt = SSA_NAME_DEF_STMT (p);
1385 if (!is_gimple_assign (stmt) || gimple_assign_lhs (stmt) != p)
1387 code = gimple_assign_rhs_code (stmt);
1388 if (code == POINTER_PLUS_EXPR)
1390 if (TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST)
1392 off = size_binop (PLUS_EXPR, off, gimple_assign_rhs2 (stmt));
1393 p = gimple_assign_rhs1 (stmt);
1395 else if (code == ADDR_EXPR || code == NOP_EXPR)
1396 p = gimple_assign_rhs1 (stmt);
1404 for (i = 0; i < cnt[0]; i++)
1405 for (j = 0; j < cnt[1]; j++)
1406 if (exps[0][i] == exps[1][j])
1407 return size_binop (MINUS_EXPR, offs[0][i], offs[1][j]);
1412 /* *GSI_P is a GIMPLE_CALL to a builtin function.
1414 memcpy (p, "abcd", 4);
1415 memset (p + 4, ' ', 3);
1417 memcpy (p, "abcd ", 7);
1418 call if the latter can be stored by pieces during expansion. */
1421 simplify_builtin_call (gimple_stmt_iterator *gsi_p, tree callee2)
1423 gimple stmt1, stmt2 = gsi_stmt (*gsi_p);
1424 tree vuse = gimple_vuse (stmt2);
1427 stmt1 = SSA_NAME_DEF_STMT (vuse);
1429 switch (DECL_FUNCTION_CODE (callee2))
1431 case BUILT_IN_MEMSET:
1432 if (gimple_call_num_args (stmt2) != 3
1433 || gimple_call_lhs (stmt2)
1435 || BITS_PER_UNIT != 8)
1440 tree ptr1, src1, str1, off1, len1, lhs1;
1441 tree ptr2 = gimple_call_arg (stmt2, 0);
1442 tree val2 = gimple_call_arg (stmt2, 1);
1443 tree len2 = gimple_call_arg (stmt2, 2);
1444 tree diff, vdef, new_str_cst;
1446 unsigned int ptr1_align;
1447 unsigned HOST_WIDE_INT src_len;
1449 use_operand_p use_p;
1451 if (!host_integerp (val2, 0)
1452 || !host_integerp (len2, 1))
1454 if (is_gimple_call (stmt1))
1456 /* If first stmt is a call, it needs to be memcpy
1457 or mempcpy, with string literal as second argument and
1459 callee1 = gimple_call_fndecl (stmt1);
1460 if (callee1 == NULL_TREE
1461 || DECL_BUILT_IN_CLASS (callee1) != BUILT_IN_NORMAL
1462 || gimple_call_num_args (stmt1) != 3)
1464 if (DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMCPY
1465 && DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMPCPY)
1467 ptr1 = gimple_call_arg (stmt1, 0);
1468 src1 = gimple_call_arg (stmt1, 1);
1469 len1 = gimple_call_arg (stmt1, 2);
1470 lhs1 = gimple_call_lhs (stmt1);
1471 if (!host_integerp (len1, 1))
1473 str1 = string_constant (src1, &off1);
1474 if (str1 == NULL_TREE)
1476 if (!host_integerp (off1, 1)
1477 || compare_tree_int (off1, TREE_STRING_LENGTH (str1) - 1) > 0
1478 || compare_tree_int (len1, TREE_STRING_LENGTH (str1)
1479 - tree_low_cst (off1, 1)) > 0
1480 || TREE_CODE (TREE_TYPE (str1)) != ARRAY_TYPE
1481 || TYPE_MODE (TREE_TYPE (TREE_TYPE (str1)))
1482 != TYPE_MODE (char_type_node))
1485 else if (gimple_assign_single_p (stmt1))
1487 /* Otherwise look for length 1 memcpy optimized into
1489 ptr1 = gimple_assign_lhs (stmt1);
1490 src1 = gimple_assign_rhs1 (stmt1);
1491 if (TREE_CODE (ptr1) != MEM_REF
1492 || TYPE_MODE (TREE_TYPE (ptr1)) != TYPE_MODE (char_type_node)
1493 || !host_integerp (src1, 0))
1495 ptr1 = build_fold_addr_expr (ptr1);
1496 callee1 = NULL_TREE;
1497 len1 = size_one_node;
1499 off1 = size_zero_node;
1505 diff = constant_pointer_difference (ptr1, ptr2);
1506 if (diff == NULL && lhs1 != NULL)
1508 diff = constant_pointer_difference (lhs1, ptr2);
1509 if (DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1511 diff = size_binop (PLUS_EXPR, diff,
1512 fold_convert (sizetype, len1));
1514 /* If the difference between the second and first destination pointer
1515 is not constant, or is bigger than memcpy length, bail out. */
1517 || !host_integerp (diff, 1)
1518 || tree_int_cst_lt (len1, diff))
1521 /* Use maximum of difference plus memset length and memcpy length
1522 as the new memcpy length, if it is too big, bail out. */
1523 src_len = tree_low_cst (diff, 1);
1524 src_len += tree_low_cst (len2, 1);
1525 if (src_len < (unsigned HOST_WIDE_INT) tree_low_cst (len1, 1))
1526 src_len = tree_low_cst (len1, 1);
1530 /* If mempcpy value is used elsewhere, bail out, as mempcpy
1531 with bigger length will return different result. */
1532 if (lhs1 != NULL_TREE
1533 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1534 && (TREE_CODE (lhs1) != SSA_NAME
1535 || !single_imm_use (lhs1, &use_p, &use_stmt)
1536 || use_stmt != stmt2))
1539 /* If anything reads memory in between memcpy and memset
1540 call, the modified memcpy call might change it. */
1541 vdef = gimple_vdef (stmt1);
1543 && (!single_imm_use (vdef, &use_p, &use_stmt)
1544 || use_stmt != stmt2))
1547 ptr1_align = get_pointer_alignment (ptr1);
1548 /* Construct the new source string literal. */
1549 src_buf = XALLOCAVEC (char, src_len + 1);
1552 TREE_STRING_POINTER (str1) + tree_low_cst (off1, 1),
1553 tree_low_cst (len1, 1));
1555 src_buf[0] = tree_low_cst (src1, 0);
1556 memset (src_buf + tree_low_cst (diff, 1),
1557 tree_low_cst (val2, 1), tree_low_cst (len2, 1));
1558 src_buf[src_len] = '\0';
1559 /* Neither builtin_strncpy_read_str nor builtin_memcpy_read_str
1560 handle embedded '\0's. */
1561 if (strlen (src_buf) != src_len)
1563 rtl_profile_for_bb (gimple_bb (stmt2));
1564 /* If the new memcpy wouldn't be emitted by storing the literal
1565 by pieces, this optimization might enlarge .rodata too much,
1566 as commonly used string literals couldn't be shared any
1568 if (!can_store_by_pieces (src_len,
1569 builtin_strncpy_read_str,
1570 src_buf, ptr1_align, false))
1573 new_str_cst = build_string_literal (src_len, src_buf);
1576 /* If STMT1 is a mem{,p}cpy call, adjust it and remove
1578 if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1579 gimple_call_set_lhs (stmt1, NULL_TREE);
1580 gimple_call_set_arg (stmt1, 1, new_str_cst);
1581 gimple_call_set_arg (stmt1, 2,
1582 build_int_cst (TREE_TYPE (len1), src_len));
1583 update_stmt (stmt1);
1584 unlink_stmt_vdef (stmt2);
1585 gsi_remove (gsi_p, true);
1586 release_defs (stmt2);
1587 if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1588 release_ssa_name (lhs1);
1593 /* Otherwise, if STMT1 is length 1 memcpy optimized into
1594 assignment, remove STMT1 and change memset call into
1596 gimple_stmt_iterator gsi = gsi_for_stmt (stmt1);
1598 if (!is_gimple_val (ptr1))
1599 ptr1 = force_gimple_operand_gsi (gsi_p, ptr1, true, NULL_TREE,
1600 true, GSI_SAME_STMT);
1601 gimple_call_set_fndecl (stmt2,
1602 builtin_decl_explicit (BUILT_IN_MEMCPY));
1603 gimple_call_set_arg (stmt2, 0, ptr1);
1604 gimple_call_set_arg (stmt2, 1, new_str_cst);
1605 gimple_call_set_arg (stmt2, 2,
1606 build_int_cst (TREE_TYPE (len2), src_len));
1607 unlink_stmt_vdef (stmt1);
1608 gsi_remove (&gsi, true);
1609 release_defs (stmt1);
1610 update_stmt (stmt2);
1621 /* Checks if expression has type of one-bit precision, or is a known
1622 truth-valued expression. */
1624 truth_valued_ssa_name (tree name)
1627 tree type = TREE_TYPE (name);
1629 if (!INTEGRAL_TYPE_P (type))
1631 /* Don't check here for BOOLEAN_TYPE as the precision isn't
1632 necessarily one and so ~X is not equal to !X. */
1633 if (TYPE_PRECISION (type) == 1)
1635 def = SSA_NAME_DEF_STMT (name);
1636 if (is_gimple_assign (def))
1637 return truth_value_p (gimple_assign_rhs_code (def));
1641 /* Helper routine for simplify_bitwise_binary_1 function.
1642 Return for the SSA name NAME the expression X if it mets condition
1643 NAME = !X. Otherwise return NULL_TREE.
1644 Detected patterns for NAME = !X are:
1645 !X and X == 0 for X with integral type.
1646 X ^ 1, X != 1,or ~X for X with integral type with precision of one. */
1648 lookup_logical_inverted_value (tree name)
1651 enum tree_code code;
1654 /* If name has none-intergal type, or isn't a SSA_NAME, then
1656 if (TREE_CODE (name) != SSA_NAME
1657 || !INTEGRAL_TYPE_P (TREE_TYPE (name)))
1659 def = SSA_NAME_DEF_STMT (name);
1660 if (!is_gimple_assign (def))
1663 code = gimple_assign_rhs_code (def);
1664 op1 = gimple_assign_rhs1 (def);
1667 /* Get for EQ_EXPR or BIT_XOR_EXPR operation the second operand.
1668 If CODE isn't an EQ_EXPR, BIT_XOR_EXPR, or BIT_NOT_EXPR, then return. */
1669 if (code == EQ_EXPR || code == NE_EXPR
1670 || code == BIT_XOR_EXPR)
1671 op2 = gimple_assign_rhs2 (def);
1676 if (truth_valued_ssa_name (name))
1680 /* Check if we have X == 0 and X has an integral type. */
1681 if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)))
1683 if (integer_zerop (op2))
1687 /* Check if we have X != 1 and X is a truth-valued. */
1688 if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)))
1690 if (integer_onep (op2) && truth_valued_ssa_name (op1))
1694 /* Check if we have X ^ 1 and X is truth valued. */
1695 if (integer_onep (op2) && truth_valued_ssa_name (op1))
1705 /* Optimize ARG1 CODE ARG2 to a constant for bitwise binary
1706 operations CODE, if one operand has the logically inverted
1707 value of the other. */
1709 simplify_bitwise_binary_1 (enum tree_code code, tree type,
1710 tree arg1, tree arg2)
1714 /* If CODE isn't a bitwise binary operation, return NULL_TREE. */
1715 if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR
1716 && code != BIT_XOR_EXPR)
1719 /* First check if operands ARG1 and ARG2 are equal. If so
1720 return NULL_TREE as this optimization is handled fold_stmt. */
1723 /* See if we have in arguments logical-not patterns. */
1724 if (((anot = lookup_logical_inverted_value (arg1)) == NULL_TREE
1726 && ((anot = lookup_logical_inverted_value (arg2)) == NULL_TREE
1731 if (code == BIT_AND_EXPR)
1732 return fold_convert (type, integer_zero_node);
1733 /* X | !X -> 1 and X ^ !X -> 1, if X is truth-valued. */
1734 if (truth_valued_ssa_name (anot))
1735 return fold_convert (type, integer_one_node);
1737 /* ??? Otherwise result is (X != 0 ? X : 1). not handled. */
1741 /* Simplify bitwise binary operations.
1742 Return true if a transformation applied, otherwise return false. */
1745 simplify_bitwise_binary (gimple_stmt_iterator *gsi)
1747 gimple stmt = gsi_stmt (*gsi);
1748 tree arg1 = gimple_assign_rhs1 (stmt);
1749 tree arg2 = gimple_assign_rhs2 (stmt);
1750 enum tree_code code = gimple_assign_rhs_code (stmt);
1752 gimple def1 = NULL, def2 = NULL;
1753 tree def1_arg1, def2_arg1;
1754 enum tree_code def1_code, def2_code;
1756 def1_code = TREE_CODE (arg1);
1758 if (TREE_CODE (arg1) == SSA_NAME)
1760 def1 = SSA_NAME_DEF_STMT (arg1);
1761 if (is_gimple_assign (def1))
1763 def1_code = gimple_assign_rhs_code (def1);
1764 def1_arg1 = gimple_assign_rhs1 (def1);
1768 def2_code = TREE_CODE (arg2);
1770 if (TREE_CODE (arg2) == SSA_NAME)
1772 def2 = SSA_NAME_DEF_STMT (arg2);
1773 if (is_gimple_assign (def2))
1775 def2_code = gimple_assign_rhs_code (def2);
1776 def2_arg1 = gimple_assign_rhs1 (def2);
1780 /* Try to fold (type) X op CST -> (type) (X op ((type-x) CST)). */
1781 if (TREE_CODE (arg2) == INTEGER_CST
1782 && CONVERT_EXPR_CODE_P (def1_code)
1783 && INTEGRAL_TYPE_P (TREE_TYPE (def1_arg1))
1784 && int_fits_type_p (arg2, TREE_TYPE (def1_arg1)))
1787 tree tem = create_tmp_reg (TREE_TYPE (def1_arg1), NULL);
1789 gimple_build_assign_with_ops (code, tem, def1_arg1,
1790 fold_convert_loc (gimple_location (stmt),
1791 TREE_TYPE (def1_arg1),
1793 tem = make_ssa_name (tem, newop);
1794 gimple_assign_set_lhs (newop, tem);
1795 gimple_set_location (newop, gimple_location (stmt));
1796 gsi_insert_before (gsi, newop, GSI_SAME_STMT);
1797 gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
1798 tem, NULL_TREE, NULL_TREE);
1799 update_stmt (gsi_stmt (*gsi));
1803 /* For bitwise binary operations apply operand conversions to the
1804 binary operation result instead of to the operands. This allows
1805 to combine successive conversions and bitwise binary operations. */
1806 if (CONVERT_EXPR_CODE_P (def1_code)
1807 && CONVERT_EXPR_CODE_P (def2_code)
1808 && types_compatible_p (TREE_TYPE (def1_arg1), TREE_TYPE (def2_arg1))
1809 /* Make sure that the conversion widens the operands, or has same
1810 precision, or that it changes the operation to a bitfield
1812 && ((TYPE_PRECISION (TREE_TYPE (def1_arg1))
1813 <= TYPE_PRECISION (TREE_TYPE (arg1)))
1814 || (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (arg1)))
1816 || (TYPE_PRECISION (TREE_TYPE (arg1))
1817 != GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (arg1))))))
1820 tree tem = create_tmp_reg (TREE_TYPE (def1_arg1),
1822 newop = gimple_build_assign_with_ops (code, tem, def1_arg1, def2_arg1);
1823 tem = make_ssa_name (tem, newop);
1824 gimple_assign_set_lhs (newop, tem);
1825 gimple_set_location (newop, gimple_location (stmt));
1826 gsi_insert_before (gsi, newop, GSI_SAME_STMT);
1827 gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
1828 tem, NULL_TREE, NULL_TREE);
1829 update_stmt (gsi_stmt (*gsi));
1833 /* (a | CST1) & CST2 -> (a & CST2) | (CST1 & CST2). */
1834 if (code == BIT_AND_EXPR
1835 && def1_code == BIT_IOR_EXPR
1836 && TREE_CODE (arg2) == INTEGER_CST
1837 && TREE_CODE (gimple_assign_rhs2 (def1)) == INTEGER_CST)
1839 tree cst = fold_build2 (BIT_AND_EXPR, TREE_TYPE (arg2),
1840 arg2, gimple_assign_rhs2 (def1));
1843 if (integer_zerop (cst))
1845 gimple_assign_set_rhs1 (stmt, def1_arg1);
1849 tem = create_tmp_reg (TREE_TYPE (arg2), NULL);
1850 newop = gimple_build_assign_with_ops (BIT_AND_EXPR,
1851 tem, def1_arg1, arg2);
1852 tem = make_ssa_name (tem, newop);
1853 gimple_assign_set_lhs (newop, tem);
1854 gimple_set_location (newop, gimple_location (stmt));
1855 /* Make sure to re-process the new stmt as it's walking upwards. */
1856 gsi_insert_before (gsi, newop, GSI_NEW_STMT);
1857 gimple_assign_set_rhs1 (stmt, tem);
1858 gimple_assign_set_rhs2 (stmt, cst);
1859 gimple_assign_set_rhs_code (stmt, BIT_IOR_EXPR);
1864 /* Combine successive equal operations with constants. */
1865 if ((code == BIT_AND_EXPR
1866 || code == BIT_IOR_EXPR
1867 || code == BIT_XOR_EXPR)
1868 && def1_code == code
1869 && TREE_CODE (arg2) == INTEGER_CST
1870 && TREE_CODE (gimple_assign_rhs2 (def1)) == INTEGER_CST)
1872 tree cst = fold_build2 (code, TREE_TYPE (arg2),
1873 arg2, gimple_assign_rhs2 (def1));
1874 gimple_assign_set_rhs1 (stmt, def1_arg1);
1875 gimple_assign_set_rhs2 (stmt, cst);
1880 /* Canonicalize X ^ ~0 to ~X. */
1881 if (code == BIT_XOR_EXPR
1882 && TREE_CODE (arg2) == INTEGER_CST
1883 && integer_all_onesp (arg2))
1885 gimple_assign_set_rhs_with_ops (gsi, BIT_NOT_EXPR, arg1, NULL_TREE);
1886 gcc_assert (gsi_stmt (*gsi) == stmt);
1891 /* Try simple folding for X op !X, and X op X. */
1892 res = simplify_bitwise_binary_1 (code, TREE_TYPE (arg1), arg1, arg2);
1893 if (res != NULL_TREE)
1895 gimple_assign_set_rhs_from_tree (gsi, res);
1896 update_stmt (gsi_stmt (*gsi));
1904 /* Perform re-associations of the plus or minus statement STMT that are
1905 always permitted. Returns true if the CFG was changed. */
1908 associate_plusminus (gimple_stmt_iterator *gsi)
1910 gimple stmt = gsi_stmt (*gsi);
1911 tree rhs1 = gimple_assign_rhs1 (stmt);
1912 tree rhs2 = gimple_assign_rhs2 (stmt);
1913 enum tree_code code = gimple_assign_rhs_code (stmt);
1916 /* We can't reassociate at all for saturating types. */
1917 if (TYPE_SATURATING (TREE_TYPE (rhs1)))
1920 /* First contract negates. */
1925 /* A +- (-B) -> A -+ B. */
1926 if (TREE_CODE (rhs2) == SSA_NAME)
1928 gimple def_stmt = SSA_NAME_DEF_STMT (rhs2);
1929 if (is_gimple_assign (def_stmt)
1930 && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR
1931 && can_propagate_from (def_stmt))
1933 code = (code == MINUS_EXPR) ? PLUS_EXPR : MINUS_EXPR;
1934 gimple_assign_set_rhs_code (stmt, code);
1935 rhs2 = gimple_assign_rhs1 (def_stmt);
1936 gimple_assign_set_rhs2 (stmt, rhs2);
1937 gimple_set_modified (stmt, true);
1942 /* (-A) + B -> B - A. */
1943 if (TREE_CODE (rhs1) == SSA_NAME
1944 && code == PLUS_EXPR)
1946 gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
1947 if (is_gimple_assign (def_stmt)
1948 && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR
1949 && can_propagate_from (def_stmt))
1952 gimple_assign_set_rhs_code (stmt, code);
1954 gimple_assign_set_rhs1 (stmt, rhs1);
1955 rhs2 = gimple_assign_rhs1 (def_stmt);
1956 gimple_assign_set_rhs2 (stmt, rhs2);
1957 gimple_set_modified (stmt, true);
1964 /* We can't reassociate floating-point or fixed-point plus or minus
1965 because of saturation to +-Inf. */
1966 if (FLOAT_TYPE_P (TREE_TYPE (rhs1))
1967 || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1)))
1970 /* Second match patterns that allow contracting a plus-minus pair
1971 irrespective of overflow issues.
1973 (A +- B) - A -> +- B
1975 (CST +- A) +- CST -> CST +- A
1976 (A + CST) +- CST -> A + CST
1979 A - (A +- B) -> -+ B
1980 A +- (B +- A) -> +- B
1981 CST +- (CST +- A) -> CST +- A
1982 CST +- (A +- CST) -> CST +- A
1985 via commutating the addition and contracting operations to zero
1986 by reassociation. */
1988 if (TREE_CODE (rhs1) == SSA_NAME)
1990 gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
1991 if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt))
1993 enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
1994 if (def_code == PLUS_EXPR
1995 || def_code == MINUS_EXPR)
1997 tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
1998 tree def_rhs2 = gimple_assign_rhs2 (def_stmt);
1999 if (operand_equal_p (def_rhs1, rhs2, 0)
2000 && code == MINUS_EXPR)
2002 /* (A +- B) - A -> +- B. */
2003 code = ((def_code == PLUS_EXPR)
2004 ? TREE_CODE (def_rhs2) : NEGATE_EXPR);
2007 gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2008 gcc_assert (gsi_stmt (*gsi) == stmt);
2009 gimple_set_modified (stmt, true);
2011 else if (operand_equal_p (def_rhs2, rhs2, 0)
2012 && code != def_code)
2014 /* (A +- B) -+ B -> A. */
2015 code = TREE_CODE (def_rhs1);
2018 gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2019 gcc_assert (gsi_stmt (*gsi) == stmt);
2020 gimple_set_modified (stmt, true);
2022 else if (TREE_CODE (rhs2) == INTEGER_CST
2023 && TREE_CODE (def_rhs1) == INTEGER_CST)
2025 /* (CST +- A) +- CST -> CST +- A. */
2026 tree cst = fold_binary (code, TREE_TYPE (rhs1),
2028 if (cst && !TREE_OVERFLOW (cst))
2031 gimple_assign_set_rhs_code (stmt, code);
2033 gimple_assign_set_rhs1 (stmt, rhs1);
2035 gimple_assign_set_rhs2 (stmt, rhs2);
2036 gimple_set_modified (stmt, true);
2039 else if (TREE_CODE (rhs2) == INTEGER_CST
2040 && TREE_CODE (def_rhs2) == INTEGER_CST
2041 && def_code == PLUS_EXPR)
2043 /* (A + CST) +- CST -> A + CST. */
2044 tree cst = fold_binary (code, TREE_TYPE (rhs1),
2046 if (cst && !TREE_OVERFLOW (cst))
2049 gimple_assign_set_rhs_code (stmt, code);
2051 gimple_assign_set_rhs1 (stmt, rhs1);
2053 gimple_assign_set_rhs2 (stmt, rhs2);
2054 gimple_set_modified (stmt, true);
2058 else if (def_code == BIT_NOT_EXPR
2059 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
2061 tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2062 if (code == PLUS_EXPR
2063 && operand_equal_p (def_rhs1, rhs2, 0))
2067 rhs1 = build_int_cst_type (TREE_TYPE (rhs2), -1);
2069 gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2070 gcc_assert (gsi_stmt (*gsi) == stmt);
2071 gimple_set_modified (stmt, true);
2073 else if (code == PLUS_EXPR
2074 && integer_onep (rhs1))
2080 gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2081 gcc_assert (gsi_stmt (*gsi) == stmt);
2082 gimple_set_modified (stmt, true);
2088 if (rhs2 && TREE_CODE (rhs2) == SSA_NAME)
2090 gimple def_stmt = SSA_NAME_DEF_STMT (rhs2);
2091 if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt))
2093 enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
2094 if (def_code == PLUS_EXPR
2095 || def_code == MINUS_EXPR)
2097 tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2098 tree def_rhs2 = gimple_assign_rhs2 (def_stmt);
2099 if (operand_equal_p (def_rhs1, rhs1, 0)
2100 && code == MINUS_EXPR)
2102 /* A - (A +- B) -> -+ B. */
2103 code = ((def_code == PLUS_EXPR)
2104 ? NEGATE_EXPR : TREE_CODE (def_rhs2));
2107 gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2108 gcc_assert (gsi_stmt (*gsi) == stmt);
2109 gimple_set_modified (stmt, true);
2111 else if (operand_equal_p (def_rhs2, rhs1, 0)
2112 && code != def_code)
2114 /* A +- (B +- A) -> +- B. */
2115 code = ((code == PLUS_EXPR)
2116 ? TREE_CODE (def_rhs1) : NEGATE_EXPR);
2119 gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2120 gcc_assert (gsi_stmt (*gsi) == stmt);
2121 gimple_set_modified (stmt, true);
2123 else if (TREE_CODE (rhs1) == INTEGER_CST
2124 && TREE_CODE (def_rhs1) == INTEGER_CST)
2126 /* CST +- (CST +- A) -> CST +- A. */
2127 tree cst = fold_binary (code, TREE_TYPE (rhs2),
2129 if (cst && !TREE_OVERFLOW (cst))
2131 code = (code == def_code ? PLUS_EXPR : MINUS_EXPR);
2132 gimple_assign_set_rhs_code (stmt, code);
2134 gimple_assign_set_rhs1 (stmt, rhs1);
2136 gimple_assign_set_rhs2 (stmt, rhs2);
2137 gimple_set_modified (stmt, true);
2140 else if (TREE_CODE (rhs1) == INTEGER_CST
2141 && TREE_CODE (def_rhs2) == INTEGER_CST)
2143 /* CST +- (A +- CST) -> CST +- A. */
2144 tree cst = fold_binary (def_code == code
2145 ? PLUS_EXPR : MINUS_EXPR,
2148 if (cst && !TREE_OVERFLOW (cst))
2151 gimple_assign_set_rhs1 (stmt, rhs1);
2153 gimple_assign_set_rhs2 (stmt, rhs2);
2154 gimple_set_modified (stmt, true);
2158 else if (def_code == BIT_NOT_EXPR
2159 && INTEGRAL_TYPE_P (TREE_TYPE (rhs2)))
2161 tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2162 if (code == PLUS_EXPR
2163 && operand_equal_p (def_rhs1, rhs1, 0))
2167 rhs1 = build_int_cst_type (TREE_TYPE (rhs1), -1);
2169 gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2170 gcc_assert (gsi_stmt (*gsi) == stmt);
2171 gimple_set_modified (stmt, true);
2178 if (gimple_modified_p (stmt))
2180 fold_stmt_inplace (gsi);
2182 if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
2183 && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
2190 /* Combine two conversions in a row for the second conversion at *GSI.
2191 Returns 1 if there were any changes made, 2 if cfg-cleanup needs to
2192 run. Else it returns 0. */
2195 combine_conversions (gimple_stmt_iterator *gsi)
2197 gimple stmt = gsi_stmt (*gsi);
2200 enum tree_code code = gimple_assign_rhs_code (stmt);
2202 gcc_checking_assert (CONVERT_EXPR_CODE_P (code)
2203 || code == FLOAT_EXPR
2204 || code == FIX_TRUNC_EXPR);
2206 lhs = gimple_assign_lhs (stmt);
2207 op0 = gimple_assign_rhs1 (stmt);
2208 if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (op0)))
2210 gimple_assign_set_rhs_code (stmt, TREE_CODE (op0));
2214 if (TREE_CODE (op0) != SSA_NAME)
2217 def_stmt = SSA_NAME_DEF_STMT (op0);
2218 if (!is_gimple_assign (def_stmt))
2221 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
2223 tree defop0 = gimple_assign_rhs1 (def_stmt);
2224 tree type = TREE_TYPE (lhs);
2225 tree inside_type = TREE_TYPE (defop0);
2226 tree inter_type = TREE_TYPE (op0);
2227 int inside_int = INTEGRAL_TYPE_P (inside_type);
2228 int inside_ptr = POINTER_TYPE_P (inside_type);
2229 int inside_float = FLOAT_TYPE_P (inside_type);
2230 int inside_vec = TREE_CODE (inside_type) == VECTOR_TYPE;
2231 unsigned int inside_prec = TYPE_PRECISION (inside_type);
2232 int inside_unsignedp = TYPE_UNSIGNED (inside_type);
2233 int inter_int = INTEGRAL_TYPE_P (inter_type);
2234 int inter_ptr = POINTER_TYPE_P (inter_type);
2235 int inter_float = FLOAT_TYPE_P (inter_type);
2236 int inter_vec = TREE_CODE (inter_type) == VECTOR_TYPE;
2237 unsigned int inter_prec = TYPE_PRECISION (inter_type);
2238 int inter_unsignedp = TYPE_UNSIGNED (inter_type);
2239 int final_int = INTEGRAL_TYPE_P (type);
2240 int final_ptr = POINTER_TYPE_P (type);
2241 int final_float = FLOAT_TYPE_P (type);
2242 int final_vec = TREE_CODE (type) == VECTOR_TYPE;
2243 unsigned int final_prec = TYPE_PRECISION (type);
2244 int final_unsignedp = TYPE_UNSIGNED (type);
2246 /* In addition to the cases of two conversions in a row
2247 handled below, if we are converting something to its own
2248 type via an object of identical or wider precision, neither
2249 conversion is needed. */
2250 if (useless_type_conversion_p (type, inside_type)
2251 && (((inter_int || inter_ptr) && final_int)
2252 || (inter_float && final_float))
2253 && inter_prec >= final_prec)
2255 gimple_assign_set_rhs1 (stmt, unshare_expr (defop0));
2256 gimple_assign_set_rhs_code (stmt, TREE_CODE (defop0));
2258 return remove_prop_source_from_use (op0) ? 2 : 1;
2261 /* Likewise, if the intermediate and initial types are either both
2262 float or both integer, we don't need the middle conversion if the
2263 former is wider than the latter and doesn't change the signedness
2264 (for integers). Avoid this if the final type is a pointer since
2265 then we sometimes need the middle conversion. Likewise if the
2266 final type has a precision not equal to the size of its mode. */
2267 if (((inter_int && inside_int)
2268 || (inter_float && inside_float)
2269 || (inter_vec && inside_vec))
2270 && inter_prec >= inside_prec
2271 && (inter_float || inter_vec
2272 || inter_unsignedp == inside_unsignedp)
2273 && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (type))
2274 && TYPE_MODE (type) == TYPE_MODE (inter_type))
2276 && (! final_vec || inter_prec == inside_prec))
2278 gimple_assign_set_rhs1 (stmt, defop0);
2280 return remove_prop_source_from_use (op0) ? 2 : 1;
2283 /* If we have a sign-extension of a zero-extended value, we can
2284 replace that by a single zero-extension. */
2285 if (inside_int && inter_int && final_int
2286 && inside_prec < inter_prec && inter_prec < final_prec
2287 && inside_unsignedp && !inter_unsignedp)
2289 gimple_assign_set_rhs1 (stmt, defop0);
2291 return remove_prop_source_from_use (op0) ? 2 : 1;
2294 /* Two conversions in a row are not needed unless:
2295 - some conversion is floating-point (overstrict for now), or
2296 - some conversion is a vector (overstrict for now), or
2297 - the intermediate type is narrower than both initial and
2299 - the intermediate type and innermost type differ in signedness,
2300 and the outermost type is wider than the intermediate, or
2301 - the initial type is a pointer type and the precisions of the
2302 intermediate and final types differ, or
2303 - the final type is a pointer type and the precisions of the
2304 initial and intermediate types differ. */
2305 if (! inside_float && ! inter_float && ! final_float
2306 && ! inside_vec && ! inter_vec && ! final_vec
2307 && (inter_prec >= inside_prec || inter_prec >= final_prec)
2308 && ! (inside_int && inter_int
2309 && inter_unsignedp != inside_unsignedp
2310 && inter_prec < final_prec)
2311 && ((inter_unsignedp && inter_prec > inside_prec)
2312 == (final_unsignedp && final_prec > inter_prec))
2313 && ! (inside_ptr && inter_prec != final_prec)
2314 && ! (final_ptr && inside_prec != inter_prec)
2315 && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (type))
2316 && TYPE_MODE (type) == TYPE_MODE (inter_type)))
2318 gimple_assign_set_rhs1 (stmt, defop0);
2320 return remove_prop_source_from_use (op0) ? 2 : 1;
2323 /* A truncation to an unsigned type should be canonicalized as
2324 bitwise and of a mask. */
2325 if (final_int && inter_int && inside_int
2326 && final_prec == inside_prec
2327 && final_prec > inter_prec
2331 tem = fold_build2 (BIT_AND_EXPR, inside_type,
2334 (inside_type, double_int_mask (inter_prec)));
2335 if (!useless_type_conversion_p (type, inside_type))
2337 tem = force_gimple_operand_gsi (gsi, tem, true, NULL_TREE, true,
2339 gimple_assign_set_rhs1 (stmt, tem);
2342 gimple_assign_set_rhs_from_tree (gsi, tem);
2343 update_stmt (gsi_stmt (*gsi));
2351 /* Main entry point for the forward propagation and statement combine
2355 ssa_forward_propagate_and_combine (void)
2358 unsigned int todoflags = 0;
2360 cfg_changed = false;
2364 gimple_stmt_iterator gsi, prev;
2365 bool prev_initialized;
2367 /* Apply forward propagation to all stmts in the basic-block.
2368 Note we update GSI within the loop as necessary. */
2369 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2371 gimple stmt = gsi_stmt (gsi);
2373 enum tree_code code;
2375 if (!is_gimple_assign (stmt))
2381 lhs = gimple_assign_lhs (stmt);
2382 rhs = gimple_assign_rhs1 (stmt);
2383 code = gimple_assign_rhs_code (stmt);
2384 if (TREE_CODE (lhs) != SSA_NAME
2385 || has_zero_uses (lhs))
2391 /* If this statement sets an SSA_NAME to an address,
2392 try to propagate the address into the uses of the SSA_NAME. */
2393 if (code == ADDR_EXPR
2394 /* Handle pointer conversions on invariant addresses
2395 as well, as this is valid gimple. */
2396 || (CONVERT_EXPR_CODE_P (code)
2397 && TREE_CODE (rhs) == ADDR_EXPR
2398 && POINTER_TYPE_P (TREE_TYPE (lhs))))
2400 tree base = get_base_address (TREE_OPERAND (rhs, 0));
2403 || decl_address_invariant_p (base))
2404 && !stmt_references_abnormal_ssa_name (stmt)
2405 && forward_propagate_addr_expr (lhs, rhs))
2407 release_defs (stmt);
2408 todoflags |= TODO_remove_unused_locals;
2409 gsi_remove (&gsi, true);
2414 else if (code == POINTER_PLUS_EXPR)
2416 tree off = gimple_assign_rhs2 (stmt);
2417 if (TREE_CODE (off) == INTEGER_CST
2418 && can_propagate_from (stmt)
2419 && !simple_iv_increment_p (stmt)
2420 /* ??? Better adjust the interface to that function
2421 instead of building new trees here. */
2422 && forward_propagate_addr_expr
2424 build1_loc (gimple_location (stmt),
2425 ADDR_EXPR, TREE_TYPE (rhs),
2426 fold_build2 (MEM_REF,
2427 TREE_TYPE (TREE_TYPE (rhs)),
2429 fold_convert (ptr_type_node,
2432 release_defs (stmt);
2433 todoflags |= TODO_remove_unused_locals;
2434 gsi_remove (&gsi, true);
2436 else if (is_gimple_min_invariant (rhs))
2438 /* Make sure to fold &a[0] + off_1 here. */
2439 fold_stmt_inplace (&gsi);
2441 if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
2447 else if (TREE_CODE_CLASS (code) == tcc_comparison)
2449 if (forward_propagate_comparison (stmt))
2457 /* Combine stmts with the stmts defining their operands.
2458 Note we update GSI within the loop as necessary. */
2459 prev_initialized = false;
2460 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
2462 gimple stmt = gsi_stmt (gsi);
2463 bool changed = false;
2465 switch (gimple_code (stmt))
2469 tree rhs1 = gimple_assign_rhs1 (stmt);
2470 enum tree_code code = gimple_assign_rhs_code (stmt);
2472 if ((code == BIT_NOT_EXPR
2473 || code == NEGATE_EXPR)
2474 && TREE_CODE (rhs1) == SSA_NAME)
2475 changed = simplify_not_neg_expr (&gsi);
2476 else if (code == COND_EXPR)
2478 /* In this case the entire COND_EXPR is in rhs1. */
2479 changed |= forward_propagate_into_cond (&gsi);
2480 stmt = gsi_stmt (gsi);
2482 else if (TREE_CODE_CLASS (code) == tcc_comparison)
2485 did_something = forward_propagate_into_comparison (&gsi);
2486 if (did_something == 2)
2488 changed = did_something != 0;
2490 else if (code == BIT_AND_EXPR
2491 || code == BIT_IOR_EXPR
2492 || code == BIT_XOR_EXPR)
2493 changed = simplify_bitwise_binary (&gsi);
2494 else if (code == PLUS_EXPR
2495 || code == MINUS_EXPR)
2496 changed = associate_plusminus (&gsi);
2497 else if (CONVERT_EXPR_CODE_P (code)
2498 || code == FLOAT_EXPR
2499 || code == FIX_TRUNC_EXPR)
2501 int did_something = combine_conversions (&gsi);
2502 if (did_something == 2)
2504 changed = did_something != 0;
2510 changed = simplify_gimple_switch (stmt);
2516 did_something = forward_propagate_into_gimple_cond (stmt);
2517 if (did_something == 2)
2519 changed = did_something != 0;
2525 tree callee = gimple_call_fndecl (stmt);
2526 if (callee != NULL_TREE
2527 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
2528 changed = simplify_builtin_call (&gsi, callee);
2537 /* If the stmt changed then re-visit it and the statements
2538 inserted before it. */
2539 if (!prev_initialized)
2540 gsi = gsi_start_bb (bb);
2550 prev_initialized = true;
2557 todoflags |= TODO_cleanup_cfg;
2564 gate_forwprop (void)
2566 return flag_tree_forwprop;
2569 struct gimple_opt_pass pass_forwprop =
2573 "forwprop", /* name */
2574 gate_forwprop, /* gate */
2575 ssa_forward_propagate_and_combine, /* execute */
2578 0, /* static_pass_number */
2579 TV_TREE_FORWPROP, /* tv_id */
2580 PROP_cfg | PROP_ssa, /* properties_required */
2581 0, /* properties_provided */
2582 0, /* properties_destroyed */
2583 0, /* todo_flags_start */
2586 | TODO_verify_ssa /* todo_flags_finish */