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 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 bb = gimple_bb (stmt);
319 gsi = gsi_for_stmt (stmt);
321 gsi_remove (&gsi, true);
322 cfg_changed |= gimple_purge_dead_eh_edges (bb);
324 name = (gimple_assign_copy_p (stmt)) ? gimple_assign_rhs1 (stmt) : NULL;
325 } while (name && TREE_CODE (name) == SSA_NAME);
330 /* Return the rhs of a gimple_assign STMT in a form of a single tree,
331 converted to type TYPE.
333 This should disappear, but is needed so we can combine expressions and use
334 the fold() interfaces. Long term, we need to develop folding and combine
335 routines that deal with gimple exclusively . */
338 rhs_to_tree (tree type, gimple stmt)
340 location_t loc = gimple_location (stmt);
341 enum tree_code code = gimple_assign_rhs_code (stmt);
342 if (get_gimple_rhs_class (code) == GIMPLE_TERNARY_RHS)
343 return fold_build3_loc (loc, code, type, gimple_assign_rhs1 (stmt),
344 gimple_assign_rhs2 (stmt),
345 gimple_assign_rhs3 (stmt));
346 else if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
347 return fold_build2_loc (loc, code, type, gimple_assign_rhs1 (stmt),
348 gimple_assign_rhs2 (stmt));
349 else if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
350 return build1 (code, type, gimple_assign_rhs1 (stmt));
351 else if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
352 return gimple_assign_rhs1 (stmt);
357 /* Combine OP0 CODE OP1 in the context of a COND_EXPR. Returns
358 the folded result in a form suitable for COND_EXPR_COND or
359 NULL_TREE, if there is no suitable simplified form. If
360 INVARIANT_ONLY is true only gimple_min_invariant results are
361 considered simplified. */
364 combine_cond_expr_cond (location_t loc, enum tree_code code, tree type,
365 tree op0, tree op1, bool invariant_only)
369 gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
371 t = fold_binary_loc (loc, code, type, op0, op1);
375 /* Require that we got a boolean type out if we put one in. */
376 gcc_assert (TREE_CODE (TREE_TYPE (t)) == TREE_CODE (type));
378 /* Canonicalize the combined condition for use in a COND_EXPR. */
379 t = canonicalize_cond_expr_cond (t);
381 /* Bail out if we required an invariant but didn't get one. */
382 if (!t || (invariant_only && !is_gimple_min_invariant (t)))
388 /* Combine the comparison OP0 CODE OP1 at LOC with the defining statements
389 of its operand. Return a new comparison tree or NULL_TREE if there
390 were no simplifying combines. */
393 forward_propagate_into_comparison_1 (location_t loc,
394 enum tree_code code, tree type,
397 tree tmp = NULL_TREE;
398 tree rhs0 = NULL_TREE, rhs1 = NULL_TREE;
399 bool single_use0_p = false, single_use1_p = false;
401 /* For comparisons use the first operand, that is likely to
402 simplify comparisons against constants. */
403 if (TREE_CODE (op0) == SSA_NAME)
405 gimple def_stmt = get_prop_source_stmt (op0, false, &single_use0_p);
406 if (def_stmt && can_propagate_from (def_stmt))
408 rhs0 = rhs_to_tree (TREE_TYPE (op1), def_stmt);
409 tmp = combine_cond_expr_cond (loc, code, type,
410 rhs0, op1, !single_use0_p);
416 /* If that wasn't successful, try the second operand. */
417 if (TREE_CODE (op1) == SSA_NAME)
419 gimple def_stmt = get_prop_source_stmt (op1, false, &single_use1_p);
420 if (def_stmt && can_propagate_from (def_stmt))
422 rhs1 = rhs_to_tree (TREE_TYPE (op0), def_stmt);
423 tmp = combine_cond_expr_cond (loc, code, type,
424 op0, rhs1, !single_use1_p);
430 /* If that wasn't successful either, try both operands. */
431 if (rhs0 != NULL_TREE
432 && rhs1 != NULL_TREE)
433 tmp = combine_cond_expr_cond (loc, code, type,
435 !(single_use0_p && single_use1_p));
440 /* Propagate from the ssa name definition statements of the assignment
441 from a comparison at *GSI into the conditional if that simplifies it.
442 Returns 1 if the stmt was modified and 2 if the CFG needs cleanup,
443 otherwise returns 0. */
446 forward_propagate_into_comparison (gimple_stmt_iterator *gsi)
448 gimple stmt = gsi_stmt (*gsi);
450 bool cfg_changed = false;
451 tree rhs1 = gimple_assign_rhs1 (stmt);
452 tree rhs2 = gimple_assign_rhs2 (stmt);
454 /* Combine the comparison with defining statements. */
455 tmp = forward_propagate_into_comparison_1 (gimple_location (stmt),
456 gimple_assign_rhs_code (stmt),
458 (gimple_assign_lhs (stmt)),
462 gimple_assign_set_rhs_from_tree (gsi, tmp);
464 if (TREE_CODE (rhs1) == SSA_NAME)
465 cfg_changed |= remove_prop_source_from_use (rhs1);
466 if (TREE_CODE (rhs2) == SSA_NAME)
467 cfg_changed |= remove_prop_source_from_use (rhs2);
468 return cfg_changed ? 2 : 1;
474 /* Propagate from the ssa name definition statements of COND_EXPR
475 in GIMPLE_COND statement STMT into the conditional if that simplifies it.
476 Returns zero if no statement was changed, one if there were
477 changes and two if cfg_cleanup needs to run.
479 This must be kept in sync with forward_propagate_into_cond. */
482 forward_propagate_into_gimple_cond (gimple stmt)
484 location_t loc = gimple_location (stmt);
486 enum tree_code code = gimple_cond_code (stmt);
487 bool cfg_changed = false;
488 tree rhs1 = gimple_cond_lhs (stmt);
489 tree rhs2 = gimple_cond_rhs (stmt);
491 /* We can do tree combining on SSA_NAME and comparison expressions. */
492 if (TREE_CODE_CLASS (gimple_cond_code (stmt)) != tcc_comparison)
495 tmp = forward_propagate_into_comparison_1 (loc, code,
500 if (dump_file && tmp)
502 fprintf (dump_file, " Replaced '");
503 print_gimple_expr (dump_file, stmt, 0, 0);
504 fprintf (dump_file, "' with '");
505 print_generic_expr (dump_file, tmp, 0);
506 fprintf (dump_file, "'\n");
509 gimple_cond_set_condition_from_tree (stmt, unshare_expr (tmp));
512 if (TREE_CODE (rhs1) == SSA_NAME)
513 cfg_changed |= remove_prop_source_from_use (rhs1);
514 if (TREE_CODE (rhs2) == SSA_NAME)
515 cfg_changed |= remove_prop_source_from_use (rhs2);
516 return (cfg_changed || is_gimple_min_invariant (tmp)) ? 2 : 1;
523 /* Propagate from the ssa name definition statements of COND_EXPR
524 in the rhs of statement STMT into the conditional if that simplifies it.
525 Returns zero if no statement was changed, one if there were
526 changes and two if cfg_cleanup needs to run.
528 This must be kept in sync with forward_propagate_into_gimple_cond. */
531 forward_propagate_into_cond (gimple_stmt_iterator *gsi_p)
533 gimple stmt = gsi_stmt (*gsi_p);
534 location_t loc = gimple_location (stmt);
535 tree tmp = NULL_TREE;
536 tree cond = gimple_assign_rhs1 (stmt);
538 /* We can do tree combining on SSA_NAME and comparison expressions. */
539 if (COMPARISON_CLASS_P (cond))
540 tmp = forward_propagate_into_comparison_1 (loc, TREE_CODE (cond),
542 TREE_OPERAND (cond, 0),
543 TREE_OPERAND (cond, 1));
544 else if (TREE_CODE (cond) == SSA_NAME)
546 tree name = cond, rhs0;
547 gimple def_stmt = get_prop_source_stmt (name, true, NULL);
548 if (!def_stmt || !can_propagate_from (def_stmt))
551 rhs0 = gimple_assign_rhs1 (def_stmt);
552 tmp = combine_cond_expr_cond (loc, NE_EXPR, boolean_type_node, rhs0,
553 build_int_cst (TREE_TYPE (rhs0), 0),
559 if (dump_file && tmp)
561 fprintf (dump_file, " Replaced '");
562 print_generic_expr (dump_file, cond, 0);
563 fprintf (dump_file, "' with '");
564 print_generic_expr (dump_file, tmp, 0);
565 fprintf (dump_file, "'\n");
568 gimple_assign_set_rhs_from_tree (gsi_p, unshare_expr (tmp));
569 stmt = gsi_stmt (*gsi_p);
572 return is_gimple_min_invariant (tmp) ? 2 : 1;
578 /* We've just substituted an ADDR_EXPR into stmt. Update all the
579 relevant data structures to match. */
582 tidy_after_forward_propagate_addr (gimple stmt)
584 /* We may have turned a trapping insn into a non-trapping insn. */
585 if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
586 && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
589 if (TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR)
590 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt));
593 /* DEF_RHS contains the address of the 0th element in an array.
594 USE_STMT uses type of DEF_RHS to compute the address of an
595 arbitrary element within the array. The (variable) byte offset
596 of the element is contained in OFFSET.
598 We walk back through the use-def chains of OFFSET to verify that
599 it is indeed computing the offset of an element within the array
600 and extract the index corresponding to the given byte offset.
602 We then try to fold the entire address expression into a form
605 If we are successful, we replace the right hand side of USE_STMT
606 with the new address computation. */
609 forward_propagate_addr_into_variable_array_index (tree offset,
611 gimple_stmt_iterator *use_stmt_gsi)
614 gimple offset_def, use_stmt = gsi_stmt (*use_stmt_gsi);
617 if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == ARRAY_REF)
618 tunit = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (def_rhs)));
619 else if (TREE_CODE (TREE_TYPE (TREE_OPERAND (def_rhs, 0))) == ARRAY_TYPE)
620 tunit = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (TREE_TYPE (def_rhs))));
623 if (!host_integerp (tunit, 1))
626 /* Get the offset's defining statement. */
627 offset_def = SSA_NAME_DEF_STMT (offset);
629 /* Try to find an expression for a proper index. This is either a
630 multiplication expression by the element size or just the ssa name we came
631 along in case the element size is one. In that case, however, we do not
632 allow multiplications because they can be computing index to a higher
633 level dimension (PR 37861). */
634 if (integer_onep (tunit))
636 if (is_gimple_assign (offset_def)
637 && gimple_assign_rhs_code (offset_def) == MULT_EXPR)
644 /* The statement which defines OFFSET before type conversion
645 must be a simple GIMPLE_ASSIGN. */
646 if (!is_gimple_assign (offset_def))
649 /* The RHS of the statement which defines OFFSET must be a
650 multiplication of an object by the size of the array elements.
651 This implicitly verifies that the size of the array elements
653 if (gimple_assign_rhs_code (offset_def) == MULT_EXPR
654 && TREE_CODE (gimple_assign_rhs2 (offset_def)) == INTEGER_CST
655 && tree_int_cst_equal (gimple_assign_rhs2 (offset_def), tunit))
657 /* The first operand to the MULT_EXPR is the desired index. */
658 index = gimple_assign_rhs1 (offset_def);
660 /* If we have idx * tunit + CST * tunit re-associate that. */
661 else if ((gimple_assign_rhs_code (offset_def) == PLUS_EXPR
662 || gimple_assign_rhs_code (offset_def) == MINUS_EXPR)
663 && TREE_CODE (gimple_assign_rhs1 (offset_def)) == SSA_NAME
664 && TREE_CODE (gimple_assign_rhs2 (offset_def)) == INTEGER_CST
665 && (tmp = div_if_zero_remainder (EXACT_DIV_EXPR,
666 gimple_assign_rhs2 (offset_def),
667 tunit)) != NULL_TREE)
669 gimple offset_def2 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (offset_def));
670 if (is_gimple_assign (offset_def2)
671 && gimple_assign_rhs_code (offset_def2) == MULT_EXPR
672 && TREE_CODE (gimple_assign_rhs2 (offset_def2)) == INTEGER_CST
673 && tree_int_cst_equal (gimple_assign_rhs2 (offset_def2), tunit))
675 index = fold_build2 (gimple_assign_rhs_code (offset_def),
677 gimple_assign_rhs1 (offset_def2), tmp);
686 /* Replace the pointer addition with array indexing. */
687 index = force_gimple_operand_gsi (use_stmt_gsi, index, true, NULL_TREE,
688 true, GSI_SAME_STMT);
689 if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == ARRAY_REF)
691 new_rhs = unshare_expr (def_rhs);
692 TREE_OPERAND (TREE_OPERAND (new_rhs, 0), 1) = index;
696 new_rhs = build4 (ARRAY_REF, TREE_TYPE (TREE_TYPE (TREE_TYPE (def_rhs))),
697 unshare_expr (TREE_OPERAND (def_rhs, 0)),
698 index, integer_zero_node, NULL_TREE);
699 new_rhs = build_fold_addr_expr (new_rhs);
700 if (!useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (use_stmt)),
701 TREE_TYPE (new_rhs)))
703 new_rhs = force_gimple_operand_gsi (use_stmt_gsi, new_rhs, true,
704 NULL_TREE, true, GSI_SAME_STMT);
705 new_rhs = fold_convert (TREE_TYPE (gimple_assign_lhs (use_stmt)),
709 gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs);
710 use_stmt = gsi_stmt (*use_stmt_gsi);
712 /* That should have created gimple, so there is no need to
713 record information to undo the propagation. */
714 fold_stmt_inplace (use_stmt);
715 tidy_after_forward_propagate_addr (use_stmt);
719 /* NAME is a SSA_NAME representing DEF_RHS which is of the form
720 ADDR_EXPR <whatever>.
722 Try to forward propagate the ADDR_EXPR into the use USE_STMT.
723 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
724 node or for recovery of array indexing from pointer arithmetic.
726 Return true if the propagation was successful (the propagation can
727 be not totally successful, yet things may have been changed). */
730 forward_propagate_addr_expr_1 (tree name, tree def_rhs,
731 gimple_stmt_iterator *use_stmt_gsi,
734 tree lhs, rhs, rhs2, array_ref;
735 gimple use_stmt = gsi_stmt (*use_stmt_gsi);
736 enum tree_code rhs_code;
739 gcc_assert (TREE_CODE (def_rhs) == ADDR_EXPR);
741 lhs = gimple_assign_lhs (use_stmt);
742 rhs_code = gimple_assign_rhs_code (use_stmt);
743 rhs = gimple_assign_rhs1 (use_stmt);
745 /* Trivial cases. The use statement could be a trivial copy or a
746 useless conversion. Recurse to the uses of the lhs as copyprop does
747 not copy through different variant pointers and FRE does not catch
748 all useless conversions. Treat the case of a single-use name and
749 a conversion to def_rhs type separate, though. */
750 if (TREE_CODE (lhs) == SSA_NAME
751 && ((rhs_code == SSA_NAME && rhs == name)
752 || CONVERT_EXPR_CODE_P (rhs_code)))
754 /* Only recurse if we don't deal with a single use or we cannot
755 do the propagation to the current statement. In particular
756 we can end up with a conversion needed for a non-invariant
757 address which we cannot do in a single statement. */
759 || (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs))
760 && (!is_gimple_min_invariant (def_rhs)
761 || (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
762 && POINTER_TYPE_P (TREE_TYPE (def_rhs))
763 && (TYPE_PRECISION (TREE_TYPE (lhs))
764 > TYPE_PRECISION (TREE_TYPE (def_rhs)))))))
765 return forward_propagate_addr_expr (lhs, def_rhs);
767 gimple_assign_set_rhs1 (use_stmt, unshare_expr (def_rhs));
768 if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
769 gimple_assign_set_rhs_code (use_stmt, TREE_CODE (def_rhs));
771 gimple_assign_set_rhs_code (use_stmt, NOP_EXPR);
775 /* Propagate through constant pointer adjustments. */
776 if (TREE_CODE (lhs) == SSA_NAME
777 && rhs_code == POINTER_PLUS_EXPR
779 && TREE_CODE (gimple_assign_rhs2 (use_stmt)) == INTEGER_CST)
782 /* As we come here with non-invariant addresses in def_rhs we need
783 to make sure we can build a valid constant offsetted address
784 for further propagation. Simply rely on fold building that
785 and check after the fact. */
786 new_def_rhs = fold_build2 (MEM_REF, TREE_TYPE (TREE_TYPE (rhs)),
788 fold_convert (ptr_type_node,
789 gimple_assign_rhs2 (use_stmt)));
790 if (TREE_CODE (new_def_rhs) == MEM_REF
791 && !is_gimple_mem_ref_addr (TREE_OPERAND (new_def_rhs, 0)))
793 new_def_rhs = build_fold_addr_expr_with_type (new_def_rhs,
796 /* Recurse. If we could propagate into all uses of lhs do not
797 bother to replace into the current use but just pretend we did. */
798 if (TREE_CODE (new_def_rhs) == ADDR_EXPR
799 && forward_propagate_addr_expr (lhs, new_def_rhs))
802 if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (new_def_rhs)))
803 gimple_assign_set_rhs_with_ops (use_stmt_gsi, TREE_CODE (new_def_rhs),
804 new_def_rhs, NULL_TREE);
805 else if (is_gimple_min_invariant (new_def_rhs))
806 gimple_assign_set_rhs_with_ops (use_stmt_gsi, NOP_EXPR,
807 new_def_rhs, NULL_TREE);
810 gcc_assert (gsi_stmt (*use_stmt_gsi) == use_stmt);
811 update_stmt (use_stmt);
815 /* Now strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
816 ADDR_EXPR will not appear on the LHS. */
817 lhs = gimple_assign_lhs (use_stmt);
818 while (handled_component_p (lhs))
819 lhs = TREE_OPERAND (lhs, 0);
821 /* Now see if the LHS node is a MEM_REF using NAME. If so,
822 propagate the ADDR_EXPR into the use of NAME and fold the result. */
823 if (TREE_CODE (lhs) == MEM_REF
824 && TREE_OPERAND (lhs, 0) == name)
827 HOST_WIDE_INT def_rhs_offset;
828 /* If the address is invariant we can always fold it. */
829 if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0),
832 double_int off = mem_ref_offset (lhs);
834 off = double_int_add (off,
835 shwi_to_double_int (def_rhs_offset));
836 if (TREE_CODE (def_rhs_base) == MEM_REF)
838 off = double_int_add (off, mem_ref_offset (def_rhs_base));
839 new_ptr = TREE_OPERAND (def_rhs_base, 0);
842 new_ptr = build_fold_addr_expr (def_rhs_base);
843 TREE_OPERAND (lhs, 0) = new_ptr;
844 TREE_OPERAND (lhs, 1)
845 = double_int_to_tree (TREE_TYPE (TREE_OPERAND (lhs, 1)), off);
846 tidy_after_forward_propagate_addr (use_stmt);
847 /* Continue propagating into the RHS if this was not the only use. */
851 /* If the LHS is a plain dereference and the value type is the same as
852 that of the pointed-to type of the address we can put the
853 dereferenced address on the LHS preserving the original alias-type. */
854 else if (gimple_assign_lhs (use_stmt) == lhs
855 && useless_type_conversion_p
856 (TREE_TYPE (TREE_OPERAND (def_rhs, 0)),
857 TREE_TYPE (gimple_assign_rhs1 (use_stmt))))
859 tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0);
860 tree new_offset, new_base, saved;
861 while (handled_component_p (*def_rhs_basep))
862 def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0);
863 saved = *def_rhs_basep;
864 if (TREE_CODE (*def_rhs_basep) == MEM_REF)
866 new_base = TREE_OPERAND (*def_rhs_basep, 0);
868 = int_const_binop (PLUS_EXPR, TREE_OPERAND (lhs, 1),
869 TREE_OPERAND (*def_rhs_basep, 1));
873 new_base = build_fold_addr_expr (*def_rhs_basep);
874 new_offset = TREE_OPERAND (lhs, 1);
876 *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep),
877 new_base, new_offset);
878 TREE_THIS_VOLATILE (*def_rhs_basep) = TREE_THIS_VOLATILE (lhs);
879 TREE_THIS_NOTRAP (*def_rhs_basep) = TREE_THIS_NOTRAP (lhs);
880 gimple_assign_set_lhs (use_stmt,
881 unshare_expr (TREE_OPERAND (def_rhs, 0)));
882 *def_rhs_basep = saved;
883 tidy_after_forward_propagate_addr (use_stmt);
884 /* Continue propagating into the RHS if this was not the
890 /* We can have a struct assignment dereferencing our name twice.
891 Note that we didn't propagate into the lhs to not falsely
892 claim we did when propagating into the rhs. */
896 /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
897 nodes from the RHS. */
898 rhs = gimple_assign_rhs1 (use_stmt);
899 if (TREE_CODE (rhs) == ADDR_EXPR)
900 rhs = TREE_OPERAND (rhs, 0);
901 while (handled_component_p (rhs))
902 rhs = TREE_OPERAND (rhs, 0);
904 /* Now see if the RHS node is a MEM_REF using NAME. If so,
905 propagate the ADDR_EXPR into the use of NAME and fold the result. */
906 if (TREE_CODE (rhs) == MEM_REF
907 && TREE_OPERAND (rhs, 0) == name)
910 HOST_WIDE_INT def_rhs_offset;
911 if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0),
914 double_int off = mem_ref_offset (rhs);
916 off = double_int_add (off,
917 shwi_to_double_int (def_rhs_offset));
918 if (TREE_CODE (def_rhs_base) == MEM_REF)
920 off = double_int_add (off, mem_ref_offset (def_rhs_base));
921 new_ptr = TREE_OPERAND (def_rhs_base, 0);
924 new_ptr = build_fold_addr_expr (def_rhs_base);
925 TREE_OPERAND (rhs, 0) = new_ptr;
926 TREE_OPERAND (rhs, 1)
927 = double_int_to_tree (TREE_TYPE (TREE_OPERAND (rhs, 1)), off);
928 fold_stmt_inplace (use_stmt);
929 tidy_after_forward_propagate_addr (use_stmt);
932 /* If the RHS is a plain dereference and the value type is the same as
933 that of the pointed-to type of the address we can put the
934 dereferenced address on the RHS preserving the original alias-type. */
935 else if (gimple_assign_rhs1 (use_stmt) == rhs
936 && useless_type_conversion_p
937 (TREE_TYPE (gimple_assign_lhs (use_stmt)),
938 TREE_TYPE (TREE_OPERAND (def_rhs, 0))))
940 tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0);
941 tree new_offset, new_base, saved;
942 while (handled_component_p (*def_rhs_basep))
943 def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0);
944 saved = *def_rhs_basep;
945 if (TREE_CODE (*def_rhs_basep) == MEM_REF)
947 new_base = TREE_OPERAND (*def_rhs_basep, 0);
949 = int_const_binop (PLUS_EXPR, TREE_OPERAND (rhs, 1),
950 TREE_OPERAND (*def_rhs_basep, 1));
954 new_base = build_fold_addr_expr (*def_rhs_basep);
955 new_offset = TREE_OPERAND (rhs, 1);
957 *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep),
958 new_base, new_offset);
959 TREE_THIS_VOLATILE (*def_rhs_basep) = TREE_THIS_VOLATILE (rhs);
960 TREE_THIS_NOTRAP (*def_rhs_basep) = TREE_THIS_NOTRAP (rhs);
961 gimple_assign_set_rhs1 (use_stmt,
962 unshare_expr (TREE_OPERAND (def_rhs, 0)));
963 *def_rhs_basep = saved;
964 fold_stmt_inplace (use_stmt);
965 tidy_after_forward_propagate_addr (use_stmt);
970 /* If the use of the ADDR_EXPR is not a POINTER_PLUS_EXPR, there
972 if (gimple_assign_rhs_code (use_stmt) != POINTER_PLUS_EXPR
973 || gimple_assign_rhs1 (use_stmt) != name)
976 /* The remaining cases are all for turning pointer arithmetic into
977 array indexing. They only apply when we have the address of
978 element zero in an array. If that is not the case then there
980 array_ref = TREE_OPERAND (def_rhs, 0);
981 if ((TREE_CODE (array_ref) != ARRAY_REF
982 || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE
983 || TREE_CODE (TREE_OPERAND (array_ref, 1)) != INTEGER_CST)
984 && TREE_CODE (TREE_TYPE (array_ref)) != ARRAY_TYPE)
987 rhs2 = gimple_assign_rhs2 (use_stmt);
988 /* Try to optimize &x[C1] p+ C2 where C2 is a multiple of the size
989 of the elements in X into &x[C1 + C2/element size]. */
990 if (TREE_CODE (rhs2) == INTEGER_CST)
992 tree new_rhs = maybe_fold_stmt_addition (gimple_location (use_stmt),
997 tree type = TREE_TYPE (gimple_assign_lhs (use_stmt));
998 new_rhs = unshare_expr (new_rhs);
999 if (!useless_type_conversion_p (type, TREE_TYPE (new_rhs)))
1001 if (!is_gimple_min_invariant (new_rhs))
1002 new_rhs = force_gimple_operand_gsi (use_stmt_gsi, new_rhs,
1004 true, GSI_SAME_STMT);
1005 new_rhs = fold_convert (type, new_rhs);
1007 gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs);
1008 use_stmt = gsi_stmt (*use_stmt_gsi);
1009 update_stmt (use_stmt);
1010 tidy_after_forward_propagate_addr (use_stmt);
1015 /* Try to optimize &x[0] p+ OFFSET where OFFSET is defined by
1016 converting a multiplication of an index by the size of the
1017 array elements, then the result is converted into the proper
1018 type for the arithmetic. */
1019 if (TREE_CODE (rhs2) == SSA_NAME
1020 && (TREE_CODE (array_ref) != ARRAY_REF
1021 || integer_zerop (TREE_OPERAND (array_ref, 1)))
1022 && useless_type_conversion_p (TREE_TYPE (name), TREE_TYPE (def_rhs))
1023 /* Avoid problems with IVopts creating PLUS_EXPRs with a
1024 different type than their operands. */
1025 && useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
1026 return forward_propagate_addr_into_variable_array_index (rhs2, def_rhs,
1031 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
1033 Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME.
1034 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
1035 node or for recovery of array indexing from pointer arithmetic.
1036 Returns true, if all uses have been propagated into. */
1039 forward_propagate_addr_expr (tree name, tree rhs)
1041 int stmt_loop_depth = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_depth;
1042 imm_use_iterator iter;
1045 bool single_use_p = has_single_use (name);
1047 FOR_EACH_IMM_USE_STMT (use_stmt, iter, name)
1052 /* If the use is not in a simple assignment statement, then
1053 there is nothing we can do. */
1054 if (gimple_code (use_stmt) != GIMPLE_ASSIGN)
1056 if (!is_gimple_debug (use_stmt))
1061 /* If the use is in a deeper loop nest, then we do not want
1062 to propagate non-invariant ADDR_EXPRs into the loop as that
1063 is likely adding expression evaluations into the loop. */
1064 if (gimple_bb (use_stmt)->loop_depth > stmt_loop_depth
1065 && !is_gimple_min_invariant (rhs))
1072 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1073 result = forward_propagate_addr_expr_1 (name, rhs, &gsi,
1075 /* If the use has moved to a different statement adjust
1076 the update machinery for the old statement too. */
1077 if (use_stmt != gsi_stmt (gsi))
1079 update_stmt (use_stmt);
1080 use_stmt = gsi_stmt (gsi);
1083 update_stmt (use_stmt);
1087 /* Remove intermediate now unused copy and conversion chains. */
1088 use_rhs = gimple_assign_rhs1 (use_stmt);
1090 && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
1091 && TREE_CODE (use_rhs) == SSA_NAME
1092 && has_zero_uses (gimple_assign_lhs (use_stmt)))
1094 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1095 release_defs (use_stmt);
1096 gsi_remove (&gsi, true);
1100 return all && has_zero_uses (name);
1104 /* Forward propagate the comparison defined in STMT like
1105 cond_1 = x CMP y to uses of the form
1109 Returns true if stmt is now unused. */
1112 forward_propagate_comparison (gimple stmt)
1114 tree name = gimple_assign_lhs (stmt);
1116 tree tmp = NULL_TREE;
1117 gimple_stmt_iterator gsi;
1118 enum tree_code code;
1121 /* Don't propagate ssa names that occur in abnormal phis. */
1122 if ((TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
1123 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)))
1124 || (TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME
1125 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs2 (stmt))))
1128 /* Do not un-cse comparisons. But propagate through copies. */
1129 use_stmt = get_prop_dest_stmt (name, &name);
1131 || !is_gimple_assign (use_stmt))
1134 code = gimple_assign_rhs_code (use_stmt);
1135 lhs = gimple_assign_lhs (use_stmt);
1136 if (!INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
1139 /* We can propagate the condition into a statement that
1140 computes the logical negation of the comparison result. */
1141 if ((code == BIT_NOT_EXPR
1142 && TYPE_PRECISION (TREE_TYPE (lhs)) == 1)
1143 || (code == BIT_XOR_EXPR
1144 && integer_onep (gimple_assign_rhs2 (use_stmt))))
1146 tree type = TREE_TYPE (gimple_assign_rhs1 (stmt));
1147 bool nans = HONOR_NANS (TYPE_MODE (type));
1148 enum tree_code inv_code;
1149 inv_code = invert_tree_comparison (gimple_assign_rhs_code (stmt), nans);
1150 if (inv_code == ERROR_MARK)
1153 tmp = build2 (inv_code, TREE_TYPE (lhs), gimple_assign_rhs1 (stmt),
1154 gimple_assign_rhs2 (stmt));
1159 gsi = gsi_for_stmt (use_stmt);
1160 gimple_assign_set_rhs_from_tree (&gsi, unshare_expr (tmp));
1161 use_stmt = gsi_stmt (gsi);
1162 update_stmt (use_stmt);
1164 if (dump_file && (dump_flags & TDF_DETAILS))
1166 fprintf (dump_file, " Replaced '");
1167 print_gimple_expr (dump_file, stmt, 0, dump_flags);
1168 fprintf (dump_file, "' with '");
1169 print_gimple_expr (dump_file, use_stmt, 0, dump_flags);
1170 fprintf (dump_file, "'\n");
1173 /* Remove defining statements. */
1174 return remove_prop_source_from_use (name);
1178 /* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y.
1179 If so, we can change STMT into lhs = y which can later be copy
1180 propagated. Similarly for negation.
1182 This could trivially be formulated as a forward propagation
1183 to immediate uses. However, we already had an implementation
1184 from DOM which used backward propagation via the use-def links.
1186 It turns out that backward propagation is actually faster as
1187 there's less work to do for each NOT/NEG expression we find.
1188 Backwards propagation needs to look at the statement in a single
1189 backlink. Forward propagation needs to look at potentially more
1190 than one forward link.
1192 Returns true when the statement was changed. */
1195 simplify_not_neg_expr (gimple_stmt_iterator *gsi_p)
1197 gimple stmt = gsi_stmt (*gsi_p);
1198 tree rhs = gimple_assign_rhs1 (stmt);
1199 gimple rhs_def_stmt = SSA_NAME_DEF_STMT (rhs);
1201 /* See if the RHS_DEF_STMT has the same form as our statement. */
1202 if (is_gimple_assign (rhs_def_stmt)
1203 && gimple_assign_rhs_code (rhs_def_stmt) == gimple_assign_rhs_code (stmt))
1205 tree rhs_def_operand = gimple_assign_rhs1 (rhs_def_stmt);
1207 /* Verify that RHS_DEF_OPERAND is a suitable SSA_NAME. */
1208 if (TREE_CODE (rhs_def_operand) == SSA_NAME
1209 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand))
1211 gimple_assign_set_rhs_from_tree (gsi_p, rhs_def_operand);
1212 stmt = gsi_stmt (*gsi_p);
1221 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
1222 the condition which we may be able to optimize better. */
1225 simplify_gimple_switch (gimple stmt)
1227 tree cond = gimple_switch_index (stmt);
1231 /* The optimization that we really care about is removing unnecessary
1232 casts. That will let us do much better in propagating the inferred
1233 constant at the switch target. */
1234 if (TREE_CODE (cond) == SSA_NAME)
1236 def_stmt = SSA_NAME_DEF_STMT (cond);
1237 if (is_gimple_assign (def_stmt))
1239 if (gimple_assign_rhs_code (def_stmt) == NOP_EXPR)
1244 def = gimple_assign_rhs1 (def_stmt);
1246 /* ??? Why was Jeff testing this? We are gimple... */
1247 gcc_checking_assert (is_gimple_val (def));
1249 to = TREE_TYPE (cond);
1250 ti = TREE_TYPE (def);
1252 /* If we have an extension that preserves value, then we
1253 can copy the source value into the switch. */
1255 need_precision = TYPE_PRECISION (ti);
1257 if (! INTEGRAL_TYPE_P (ti))
1259 else if (TYPE_UNSIGNED (to) && !TYPE_UNSIGNED (ti))
1261 else if (!TYPE_UNSIGNED (to) && TYPE_UNSIGNED (ti))
1262 need_precision += 1;
1263 if (TYPE_PRECISION (to) < need_precision)
1268 gimple_switch_set_index (stmt, def);
1279 /* For pointers p2 and p1 return p2 - p1 if the
1280 difference is known and constant, otherwise return NULL. */
1283 constant_pointer_difference (tree p1, tree p2)
1286 #define CPD_ITERATIONS 5
1287 tree exps[2][CPD_ITERATIONS];
1288 tree offs[2][CPD_ITERATIONS];
1291 for (i = 0; i < 2; i++)
1293 tree p = i ? p1 : p2;
1294 tree off = size_zero_node;
1296 enum tree_code code;
1298 /* For each of p1 and p2 we need to iterate at least
1299 twice, to handle ADDR_EXPR directly in p1/p2,
1300 SSA_NAME with ADDR_EXPR or POINTER_PLUS_EXPR etc.
1301 on definition's stmt RHS. Iterate a few extra times. */
1305 if (!POINTER_TYPE_P (TREE_TYPE (p)))
1307 if (TREE_CODE (p) == ADDR_EXPR)
1309 tree q = TREE_OPERAND (p, 0);
1310 HOST_WIDE_INT offset;
1311 tree base = get_addr_base_and_unit_offset (q, &offset);
1316 off = size_binop (PLUS_EXPR, off, size_int (offset));
1318 if (TREE_CODE (q) == MEM_REF
1319 && TREE_CODE (TREE_OPERAND (q, 0)) == SSA_NAME)
1321 p = TREE_OPERAND (q, 0);
1322 off = size_binop (PLUS_EXPR, off,
1323 double_int_to_tree (sizetype,
1324 mem_ref_offset (q)));
1333 if (TREE_CODE (p) != SSA_NAME)
1337 if (j == CPD_ITERATIONS)
1339 stmt = SSA_NAME_DEF_STMT (p);
1340 if (!is_gimple_assign (stmt) || gimple_assign_lhs (stmt) != p)
1342 code = gimple_assign_rhs_code (stmt);
1343 if (code == POINTER_PLUS_EXPR)
1345 if (TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST)
1347 off = size_binop (PLUS_EXPR, off, gimple_assign_rhs2 (stmt));
1348 p = gimple_assign_rhs1 (stmt);
1350 else if (code == ADDR_EXPR || code == NOP_EXPR)
1351 p = gimple_assign_rhs1 (stmt);
1359 for (i = 0; i < cnt[0]; i++)
1360 for (j = 0; j < cnt[1]; j++)
1361 if (exps[0][i] == exps[1][j])
1362 return size_binop (MINUS_EXPR, offs[0][i], offs[1][j]);
1367 /* *GSI_P is a GIMPLE_CALL to a builtin function.
1369 memcpy (p, "abcd", 4);
1370 memset (p + 4, ' ', 3);
1372 memcpy (p, "abcd ", 7);
1373 call if the latter can be stored by pieces during expansion. */
1376 simplify_builtin_call (gimple_stmt_iterator *gsi_p, tree callee2)
1378 gimple stmt1, stmt2 = gsi_stmt (*gsi_p);
1379 tree vuse = gimple_vuse (stmt2);
1382 stmt1 = SSA_NAME_DEF_STMT (vuse);
1384 switch (DECL_FUNCTION_CODE (callee2))
1386 case BUILT_IN_MEMSET:
1387 if (gimple_call_num_args (stmt2) != 3
1388 || gimple_call_lhs (stmt2)
1390 || BITS_PER_UNIT != 8)
1395 tree ptr1, src1, str1, off1, len1, lhs1;
1396 tree ptr2 = gimple_call_arg (stmt2, 0);
1397 tree val2 = gimple_call_arg (stmt2, 1);
1398 tree len2 = gimple_call_arg (stmt2, 2);
1399 tree diff, vdef, new_str_cst;
1401 unsigned int ptr1_align;
1402 unsigned HOST_WIDE_INT src_len;
1404 use_operand_p use_p;
1406 if (!host_integerp (val2, 0)
1407 || !host_integerp (len2, 1))
1409 if (is_gimple_call (stmt1))
1411 /* If first stmt is a call, it needs to be memcpy
1412 or mempcpy, with string literal as second argument and
1414 callee1 = gimple_call_fndecl (stmt1);
1415 if (callee1 == NULL_TREE
1416 || DECL_BUILT_IN_CLASS (callee1) != BUILT_IN_NORMAL
1417 || gimple_call_num_args (stmt1) != 3)
1419 if (DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMCPY
1420 && DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMPCPY)
1422 ptr1 = gimple_call_arg (stmt1, 0);
1423 src1 = gimple_call_arg (stmt1, 1);
1424 len1 = gimple_call_arg (stmt1, 2);
1425 lhs1 = gimple_call_lhs (stmt1);
1426 if (!host_integerp (len1, 1))
1428 str1 = string_constant (src1, &off1);
1429 if (str1 == NULL_TREE)
1431 if (!host_integerp (off1, 1)
1432 || compare_tree_int (off1, TREE_STRING_LENGTH (str1) - 1) > 0
1433 || compare_tree_int (len1, TREE_STRING_LENGTH (str1)
1434 - tree_low_cst (off1, 1)) > 0
1435 || TREE_CODE (TREE_TYPE (str1)) != ARRAY_TYPE
1436 || TYPE_MODE (TREE_TYPE (TREE_TYPE (str1)))
1437 != TYPE_MODE (char_type_node))
1440 else if (gimple_assign_single_p (stmt1))
1442 /* Otherwise look for length 1 memcpy optimized into
1444 ptr1 = gimple_assign_lhs (stmt1);
1445 src1 = gimple_assign_rhs1 (stmt1);
1446 if (TREE_CODE (ptr1) != MEM_REF
1447 || TYPE_MODE (TREE_TYPE (ptr1)) != TYPE_MODE (char_type_node)
1448 || !host_integerp (src1, 0))
1450 ptr1 = build_fold_addr_expr (ptr1);
1451 callee1 = NULL_TREE;
1452 len1 = size_one_node;
1454 off1 = size_zero_node;
1460 diff = constant_pointer_difference (ptr1, ptr2);
1461 if (diff == NULL && lhs1 != NULL)
1463 diff = constant_pointer_difference (lhs1, ptr2);
1464 if (DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1466 diff = size_binop (PLUS_EXPR, diff,
1467 fold_convert (sizetype, len1));
1469 /* If the difference between the second and first destination pointer
1470 is not constant, or is bigger than memcpy length, bail out. */
1472 || !host_integerp (diff, 1)
1473 || tree_int_cst_lt (len1, diff))
1476 /* Use maximum of difference plus memset length and memcpy length
1477 as the new memcpy length, if it is too big, bail out. */
1478 src_len = tree_low_cst (diff, 1);
1479 src_len += tree_low_cst (len2, 1);
1480 if (src_len < (unsigned HOST_WIDE_INT) tree_low_cst (len1, 1))
1481 src_len = tree_low_cst (len1, 1);
1485 /* If mempcpy value is used elsewhere, bail out, as mempcpy
1486 with bigger length will return different result. */
1487 if (lhs1 != NULL_TREE
1488 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1489 && (TREE_CODE (lhs1) != SSA_NAME
1490 || !single_imm_use (lhs1, &use_p, &use_stmt)
1491 || use_stmt != stmt2))
1494 /* If anything reads memory in between memcpy and memset
1495 call, the modified memcpy call might change it. */
1496 vdef = gimple_vdef (stmt1);
1498 && (!single_imm_use (vdef, &use_p, &use_stmt)
1499 || use_stmt != stmt2))
1502 ptr1_align = get_pointer_alignment (ptr1, BIGGEST_ALIGNMENT);
1503 /* Construct the new source string literal. */
1504 src_buf = XALLOCAVEC (char, src_len + 1);
1507 TREE_STRING_POINTER (str1) + tree_low_cst (off1, 1),
1508 tree_low_cst (len1, 1));
1510 src_buf[0] = tree_low_cst (src1, 0);
1511 memset (src_buf + tree_low_cst (diff, 1),
1512 tree_low_cst (val2, 1), tree_low_cst (len2, 1));
1513 src_buf[src_len] = '\0';
1514 /* Neither builtin_strncpy_read_str nor builtin_memcpy_read_str
1515 handle embedded '\0's. */
1516 if (strlen (src_buf) != src_len)
1518 rtl_profile_for_bb (gimple_bb (stmt2));
1519 /* If the new memcpy wouldn't be emitted by storing the literal
1520 by pieces, this optimization might enlarge .rodata too much,
1521 as commonly used string literals couldn't be shared any
1523 if (!can_store_by_pieces (src_len,
1524 builtin_strncpy_read_str,
1525 src_buf, ptr1_align, false))
1528 new_str_cst = build_string_literal (src_len, src_buf);
1531 /* If STMT1 is a mem{,p}cpy call, adjust it and remove
1533 if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1534 gimple_call_set_lhs (stmt1, NULL_TREE);
1535 gimple_call_set_arg (stmt1, 1, new_str_cst);
1536 gimple_call_set_arg (stmt1, 2,
1537 build_int_cst (TREE_TYPE (len1), src_len));
1538 update_stmt (stmt1);
1539 unlink_stmt_vdef (stmt2);
1540 gsi_remove (gsi_p, true);
1541 release_defs (stmt2);
1542 if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1543 release_ssa_name (lhs1);
1548 /* Otherwise, if STMT1 is length 1 memcpy optimized into
1549 assignment, remove STMT1 and change memset call into
1551 gimple_stmt_iterator gsi = gsi_for_stmt (stmt1);
1553 if (!is_gimple_val (ptr1))
1554 ptr1 = force_gimple_operand_gsi (gsi_p, ptr1, true, NULL_TREE,
1555 true, GSI_SAME_STMT);
1556 gimple_call_set_fndecl (stmt2, built_in_decls [BUILT_IN_MEMCPY]);
1557 gimple_call_set_arg (stmt2, 0, ptr1);
1558 gimple_call_set_arg (stmt2, 1, new_str_cst);
1559 gimple_call_set_arg (stmt2, 2,
1560 build_int_cst (TREE_TYPE (len2), src_len));
1561 unlink_stmt_vdef (stmt1);
1562 gsi_remove (&gsi, true);
1563 release_defs (stmt1);
1564 update_stmt (stmt2);
1575 /* Checks if expression has type of one-bit precision, or is a known
1576 truth-valued expression. */
1578 truth_valued_ssa_name (tree name)
1581 tree type = TREE_TYPE (name);
1583 if (!INTEGRAL_TYPE_P (type))
1585 /* Don't check here for BOOLEAN_TYPE as the precision isn't
1586 necessarily one and so ~X is not equal to !X. */
1587 if (TYPE_PRECISION (type) == 1)
1589 def = SSA_NAME_DEF_STMT (name);
1590 if (is_gimple_assign (def))
1591 return truth_value_p (gimple_assign_rhs_code (def));
1595 /* Helper routine for simplify_bitwise_binary_1 function.
1596 Return for the SSA name NAME the expression X if it mets condition
1597 NAME = !X. Otherwise return NULL_TREE.
1598 Detected patterns for NAME = !X are:
1599 !X and X == 0 for X with integral type.
1600 X ^ 1, X != 1,or ~X for X with integral type with precision of one. */
1602 lookup_logical_inverted_value (tree name)
1605 enum tree_code code;
1608 /* If name has none-intergal type, or isn't a SSA_NAME, then
1610 if (TREE_CODE (name) != SSA_NAME
1611 || !INTEGRAL_TYPE_P (TREE_TYPE (name)))
1613 def = SSA_NAME_DEF_STMT (name);
1614 if (!is_gimple_assign (def))
1617 code = gimple_assign_rhs_code (def);
1618 op1 = gimple_assign_rhs1 (def);
1621 /* Get for EQ_EXPR or BIT_XOR_EXPR operation the second operand.
1622 If CODE isn't an EQ_EXPR, BIT_XOR_EXPR, or BIT_NOT_EXPR, then return. */
1623 if (code == EQ_EXPR || code == NE_EXPR
1624 || code == BIT_XOR_EXPR)
1625 op2 = gimple_assign_rhs2 (def);
1630 if (truth_valued_ssa_name (name))
1634 /* Check if we have X == 0 and X has an integral type. */
1635 if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)))
1637 if (integer_zerop (op2))
1641 /* Check if we have X != 1 and X is a truth-valued. */
1642 if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)))
1644 if (integer_onep (op2) && truth_valued_ssa_name (op1))
1648 /* Check if we have X ^ 1 and X is truth valued. */
1649 if (integer_onep (op2) && truth_valued_ssa_name (op1))
1659 /* Optimize ARG1 CODE ARG2 to a constant for bitwise binary
1660 operations CODE, if one operand has the logically inverted
1661 value of the other. */
1663 simplify_bitwise_binary_1 (enum tree_code code, tree type,
1664 tree arg1, tree arg2)
1668 /* If CODE isn't a bitwise binary operation, return NULL_TREE. */
1669 if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR
1670 && code != BIT_XOR_EXPR)
1673 /* First check if operands ARG1 and ARG2 are equal. If so
1674 return NULL_TREE as this optimization is handled fold_stmt. */
1677 /* See if we have in arguments logical-not patterns. */
1678 if (((anot = lookup_logical_inverted_value (arg1)) == NULL_TREE
1680 && ((anot = lookup_logical_inverted_value (arg2)) == NULL_TREE
1685 if (code == BIT_AND_EXPR)
1686 return fold_convert (type, integer_zero_node);
1687 /* X | !X -> 1 and X ^ !X -> 1, if X is truth-valued. */
1688 if (truth_valued_ssa_name (anot))
1689 return fold_convert (type, integer_one_node);
1691 /* ??? Otherwise result is (X != 0 ? X : 1). not handled. */
1695 /* Simplify bitwise binary operations.
1696 Return true if a transformation applied, otherwise return false. */
1699 simplify_bitwise_binary (gimple_stmt_iterator *gsi)
1701 gimple stmt = gsi_stmt (*gsi);
1702 tree arg1 = gimple_assign_rhs1 (stmt);
1703 tree arg2 = gimple_assign_rhs2 (stmt);
1704 enum tree_code code = gimple_assign_rhs_code (stmt);
1706 gimple def1 = NULL, def2 = NULL;
1707 tree def1_arg1, def2_arg1;
1708 enum tree_code def1_code, def2_code;
1710 def1_code = TREE_CODE (arg1);
1712 if (TREE_CODE (arg1) == SSA_NAME)
1714 def1 = SSA_NAME_DEF_STMT (arg1);
1715 if (is_gimple_assign (def1))
1717 def1_code = gimple_assign_rhs_code (def1);
1718 def1_arg1 = gimple_assign_rhs1 (def1);
1722 def2_code = TREE_CODE (arg2);
1724 if (TREE_CODE (arg2) == SSA_NAME)
1726 def2 = SSA_NAME_DEF_STMT (arg2);
1727 if (is_gimple_assign (def2))
1729 def2_code = gimple_assign_rhs_code (def2);
1730 def2_arg1 = gimple_assign_rhs1 (def2);
1734 /* Try to fold (type) X op CST -> (type) (X op ((type-x) CST)). */
1735 if (TREE_CODE (arg2) == INTEGER_CST
1736 && CONVERT_EXPR_CODE_P (def1_code)
1737 && INTEGRAL_TYPE_P (TREE_TYPE (def1_arg1))
1738 && int_fits_type_p (arg2, TREE_TYPE (def1_arg1)))
1741 tree tem = create_tmp_reg (TREE_TYPE (def1_arg1), NULL);
1743 gimple_build_assign_with_ops (code, tem, def1_arg1,
1744 fold_convert_loc (gimple_location (stmt),
1745 TREE_TYPE (def1_arg1),
1747 tem = make_ssa_name (tem, newop);
1748 gimple_assign_set_lhs (newop, tem);
1749 gimple_set_location (newop, gimple_location (stmt));
1750 gsi_insert_before (gsi, newop, GSI_SAME_STMT);
1751 gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
1752 tem, NULL_TREE, NULL_TREE);
1753 update_stmt (gsi_stmt (*gsi));
1757 /* For bitwise binary operations apply operand conversions to the
1758 binary operation result instead of to the operands. This allows
1759 to combine successive conversions and bitwise binary operations. */
1760 if (CONVERT_EXPR_CODE_P (def1_code)
1761 && CONVERT_EXPR_CODE_P (def2_code)
1762 && types_compatible_p (TREE_TYPE (def1_arg1), TREE_TYPE (def2_arg1))
1763 /* Make sure that the conversion widens the operands, or has same
1764 precision, or that it changes the operation to a bitfield
1766 && ((TYPE_PRECISION (TREE_TYPE (def1_arg1))
1767 <= TYPE_PRECISION (TREE_TYPE (arg1)))
1768 || (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (arg1)))
1770 || (TYPE_PRECISION (TREE_TYPE (arg1))
1771 != GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (arg1))))))
1774 tree tem = create_tmp_reg (TREE_TYPE (def1_arg1),
1776 newop = gimple_build_assign_with_ops (code, tem, def1_arg1, def2_arg1);
1777 tem = make_ssa_name (tem, newop);
1778 gimple_assign_set_lhs (newop, tem);
1779 gimple_set_location (newop, gimple_location (stmt));
1780 gsi_insert_before (gsi, newop, GSI_SAME_STMT);
1781 gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
1782 tem, NULL_TREE, NULL_TREE);
1783 update_stmt (gsi_stmt (*gsi));
1787 /* (a | CST1) & CST2 -> (a & CST2) | (CST1 & CST2). */
1788 if (code == BIT_AND_EXPR
1789 && def1_code == BIT_IOR_EXPR
1790 && TREE_CODE (arg2) == INTEGER_CST
1791 && TREE_CODE (gimple_assign_rhs2 (def1)) == INTEGER_CST)
1793 tree cst = fold_build2 (BIT_AND_EXPR, TREE_TYPE (arg2),
1794 arg2, gimple_assign_rhs2 (def1));
1797 if (integer_zerop (cst))
1799 gimple_assign_set_rhs1 (stmt, def1_arg1);
1803 tem = create_tmp_reg (TREE_TYPE (arg2), NULL);
1804 newop = gimple_build_assign_with_ops (BIT_AND_EXPR,
1805 tem, def1_arg1, arg2);
1806 tem = make_ssa_name (tem, newop);
1807 gimple_assign_set_lhs (newop, tem);
1808 gimple_set_location (newop, gimple_location (stmt));
1809 /* Make sure to re-process the new stmt as it's walking upwards. */
1810 gsi_insert_before (gsi, newop, GSI_NEW_STMT);
1811 gimple_assign_set_rhs1 (stmt, tem);
1812 gimple_assign_set_rhs2 (stmt, cst);
1813 gimple_assign_set_rhs_code (stmt, BIT_IOR_EXPR);
1818 /* Combine successive equal operations with constants. */
1819 if ((code == BIT_AND_EXPR
1820 || code == BIT_IOR_EXPR
1821 || code == BIT_XOR_EXPR)
1822 && def1_code == code
1823 && TREE_CODE (arg2) == INTEGER_CST
1824 && TREE_CODE (gimple_assign_rhs2 (def1)) == INTEGER_CST)
1826 tree cst = fold_build2 (code, TREE_TYPE (arg2),
1827 arg2, gimple_assign_rhs2 (def1));
1828 gimple_assign_set_rhs1 (stmt, def1_arg1);
1829 gimple_assign_set_rhs2 (stmt, cst);
1834 /* Canonicalize X ^ ~0 to ~X. */
1835 if (code == BIT_XOR_EXPR
1836 && TREE_CODE (arg2) == INTEGER_CST
1837 && integer_all_onesp (arg2))
1839 gimple_assign_set_rhs_with_ops (gsi, BIT_NOT_EXPR, arg1, NULL_TREE);
1840 gcc_assert (gsi_stmt (*gsi) == stmt);
1845 /* Try simple folding for X op !X, and X op X. */
1846 res = simplify_bitwise_binary_1 (code, TREE_TYPE (arg1), arg1, arg2);
1847 if (res != NULL_TREE)
1849 gimple_assign_set_rhs_from_tree (gsi, res);
1850 update_stmt (gsi_stmt (*gsi));
1858 /* Perform re-associations of the plus or minus statement STMT that are
1859 always permitted. Returns true if the CFG was changed. */
1862 associate_plusminus (gimple stmt)
1864 tree rhs1 = gimple_assign_rhs1 (stmt);
1865 tree rhs2 = gimple_assign_rhs2 (stmt);
1866 enum tree_code code = gimple_assign_rhs_code (stmt);
1867 gimple_stmt_iterator gsi;
1870 /* We can't reassociate at all for saturating types. */
1871 if (TYPE_SATURATING (TREE_TYPE (rhs1)))
1874 /* First contract negates. */
1879 /* A +- (-B) -> A -+ B. */
1880 if (TREE_CODE (rhs2) == SSA_NAME)
1882 gimple def_stmt = SSA_NAME_DEF_STMT (rhs2);
1883 if (is_gimple_assign (def_stmt)
1884 && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR
1885 && can_propagate_from (def_stmt))
1887 code = (code == MINUS_EXPR) ? PLUS_EXPR : MINUS_EXPR;
1888 gimple_assign_set_rhs_code (stmt, code);
1889 rhs2 = gimple_assign_rhs1 (def_stmt);
1890 gimple_assign_set_rhs2 (stmt, rhs2);
1891 gimple_set_modified (stmt, true);
1896 /* (-A) + B -> B - A. */
1897 if (TREE_CODE (rhs1) == SSA_NAME
1898 && code == PLUS_EXPR)
1900 gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
1901 if (is_gimple_assign (def_stmt)
1902 && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR
1903 && can_propagate_from (def_stmt))
1906 gimple_assign_set_rhs_code (stmt, code);
1908 gimple_assign_set_rhs1 (stmt, rhs1);
1909 rhs2 = gimple_assign_rhs1 (def_stmt);
1910 gimple_assign_set_rhs2 (stmt, rhs2);
1911 gimple_set_modified (stmt, true);
1918 /* We can't reassociate floating-point or fixed-point plus or minus
1919 because of saturation to +-Inf. */
1920 if (FLOAT_TYPE_P (TREE_TYPE (rhs1))
1921 || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1)))
1924 /* Second match patterns that allow contracting a plus-minus pair
1925 irrespective of overflow issues.
1927 (A +- B) - A -> +- B
1929 (CST +- A) +- CST -> CST +- A
1930 (A + CST) +- CST -> A + CST
1933 A - (A +- B) -> -+ B
1934 A +- (B +- A) -> +- B
1935 CST +- (CST +- A) -> CST +- A
1936 CST +- (A +- CST) -> CST +- A
1939 via commutating the addition and contracting operations to zero
1940 by reassociation. */
1942 gsi = gsi_for_stmt (stmt);
1943 if (TREE_CODE (rhs1) == SSA_NAME)
1945 gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
1946 if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt))
1948 enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
1949 if (def_code == PLUS_EXPR
1950 || def_code == MINUS_EXPR)
1952 tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
1953 tree def_rhs2 = gimple_assign_rhs2 (def_stmt);
1954 if (operand_equal_p (def_rhs1, rhs2, 0)
1955 && code == MINUS_EXPR)
1957 /* (A +- B) - A -> +- B. */
1958 code = ((def_code == PLUS_EXPR)
1959 ? TREE_CODE (def_rhs2) : NEGATE_EXPR);
1962 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
1963 gcc_assert (gsi_stmt (gsi) == stmt);
1964 gimple_set_modified (stmt, true);
1966 else if (operand_equal_p (def_rhs2, rhs2, 0)
1967 && code != def_code)
1969 /* (A +- B) -+ B -> A. */
1970 code = TREE_CODE (def_rhs1);
1973 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
1974 gcc_assert (gsi_stmt (gsi) == stmt);
1975 gimple_set_modified (stmt, true);
1977 else if (TREE_CODE (rhs2) == INTEGER_CST
1978 && TREE_CODE (def_rhs1) == INTEGER_CST)
1980 /* (CST +- A) +- CST -> CST +- A. */
1981 tree cst = fold_binary (code, TREE_TYPE (rhs1),
1983 if (cst && !TREE_OVERFLOW (cst))
1986 gimple_assign_set_rhs_code (stmt, code);
1988 gimple_assign_set_rhs1 (stmt, rhs1);
1990 gimple_assign_set_rhs2 (stmt, rhs2);
1991 gimple_set_modified (stmt, true);
1994 else if (TREE_CODE (rhs2) == INTEGER_CST
1995 && TREE_CODE (def_rhs2) == INTEGER_CST
1996 && def_code == PLUS_EXPR)
1998 /* (A + CST) +- CST -> A + CST. */
1999 tree cst = fold_binary (code, TREE_TYPE (rhs1),
2001 if (cst && !TREE_OVERFLOW (cst))
2004 gimple_assign_set_rhs_code (stmt, code);
2006 gimple_assign_set_rhs1 (stmt, rhs1);
2008 gimple_assign_set_rhs2 (stmt, rhs2);
2009 gimple_set_modified (stmt, true);
2013 else if (def_code == BIT_NOT_EXPR
2014 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
2016 tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2017 if (code == PLUS_EXPR
2018 && operand_equal_p (def_rhs1, rhs2, 0))
2022 rhs1 = build_int_cst_type (TREE_TYPE (rhs2), -1);
2024 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2025 gcc_assert (gsi_stmt (gsi) == stmt);
2026 gimple_set_modified (stmt, true);
2028 else if (code == PLUS_EXPR
2029 && integer_onep (rhs1))
2035 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2036 gcc_assert (gsi_stmt (gsi) == stmt);
2037 gimple_set_modified (stmt, true);
2043 if (rhs2 && TREE_CODE (rhs2) == SSA_NAME)
2045 gimple def_stmt = SSA_NAME_DEF_STMT (rhs2);
2046 if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt))
2048 enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
2049 if (def_code == PLUS_EXPR
2050 || def_code == MINUS_EXPR)
2052 tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2053 tree def_rhs2 = gimple_assign_rhs2 (def_stmt);
2054 if (operand_equal_p (def_rhs1, rhs1, 0)
2055 && code == MINUS_EXPR)
2057 /* A - (A +- B) -> -+ B. */
2058 code = ((def_code == PLUS_EXPR)
2059 ? NEGATE_EXPR : TREE_CODE (def_rhs2));
2062 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2063 gcc_assert (gsi_stmt (gsi) == stmt);
2064 gimple_set_modified (stmt, true);
2066 else if (operand_equal_p (def_rhs2, rhs1, 0)
2067 && code != def_code)
2069 /* A +- (B +- A) -> +- B. */
2070 code = ((code == PLUS_EXPR)
2071 ? TREE_CODE (def_rhs1) : NEGATE_EXPR);
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 (TREE_CODE (rhs1) == INTEGER_CST
2079 && TREE_CODE (def_rhs1) == INTEGER_CST)
2081 /* CST +- (CST +- A) -> CST +- A. */
2082 tree cst = fold_binary (code, TREE_TYPE (rhs2),
2084 if (cst && !TREE_OVERFLOW (cst))
2086 code = (code == def_code ? PLUS_EXPR : MINUS_EXPR);
2087 gimple_assign_set_rhs_code (stmt, code);
2089 gimple_assign_set_rhs1 (stmt, rhs1);
2091 gimple_assign_set_rhs2 (stmt, rhs2);
2092 gimple_set_modified (stmt, true);
2095 else if (TREE_CODE (rhs1) == INTEGER_CST
2096 && TREE_CODE (def_rhs2) == INTEGER_CST)
2098 /* CST +- (A +- CST) -> CST +- A. */
2099 tree cst = fold_binary (def_code == code
2100 ? PLUS_EXPR : MINUS_EXPR,
2103 if (cst && !TREE_OVERFLOW (cst))
2106 gimple_assign_set_rhs1 (stmt, rhs1);
2108 gimple_assign_set_rhs2 (stmt, rhs2);
2109 gimple_set_modified (stmt, true);
2113 else if (def_code == BIT_NOT_EXPR
2114 && INTEGRAL_TYPE_P (TREE_TYPE (rhs2)))
2116 tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2117 if (code == PLUS_EXPR
2118 && operand_equal_p (def_rhs1, rhs1, 0))
2122 rhs1 = build_int_cst_type (TREE_TYPE (rhs1), -1);
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);
2133 if (gimple_modified_p (stmt))
2135 fold_stmt_inplace (stmt);
2137 if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
2138 && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
2145 /* Combine two conversions in a row for the second conversion at *GSI.
2146 Returns 1 if there were any changes made, 2 if cfg-cleanup needs to
2147 run. Else it returns 0. */
2150 combine_conversions (gimple_stmt_iterator *gsi)
2152 gimple stmt = gsi_stmt (*gsi);
2155 enum tree_code code = gimple_assign_rhs_code (stmt);
2157 gcc_checking_assert (CONVERT_EXPR_CODE_P (code)
2158 || code == FLOAT_EXPR
2159 || code == FIX_TRUNC_EXPR);
2161 lhs = gimple_assign_lhs (stmt);
2162 op0 = gimple_assign_rhs1 (stmt);
2163 if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (op0)))
2165 gimple_assign_set_rhs_code (stmt, TREE_CODE (op0));
2169 if (TREE_CODE (op0) != SSA_NAME)
2172 def_stmt = SSA_NAME_DEF_STMT (op0);
2173 if (!is_gimple_assign (def_stmt))
2176 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
2178 tree defop0 = gimple_assign_rhs1 (def_stmt);
2179 tree type = TREE_TYPE (lhs);
2180 tree inside_type = TREE_TYPE (defop0);
2181 tree inter_type = TREE_TYPE (op0);
2182 int inside_int = INTEGRAL_TYPE_P (inside_type);
2183 int inside_ptr = POINTER_TYPE_P (inside_type);
2184 int inside_float = FLOAT_TYPE_P (inside_type);
2185 int inside_vec = TREE_CODE (inside_type) == VECTOR_TYPE;
2186 unsigned int inside_prec = TYPE_PRECISION (inside_type);
2187 int inside_unsignedp = TYPE_UNSIGNED (inside_type);
2188 int inter_int = INTEGRAL_TYPE_P (inter_type);
2189 int inter_ptr = POINTER_TYPE_P (inter_type);
2190 int inter_float = FLOAT_TYPE_P (inter_type);
2191 int inter_vec = TREE_CODE (inter_type) == VECTOR_TYPE;
2192 unsigned int inter_prec = TYPE_PRECISION (inter_type);
2193 int inter_unsignedp = TYPE_UNSIGNED (inter_type);
2194 int final_int = INTEGRAL_TYPE_P (type);
2195 int final_ptr = POINTER_TYPE_P (type);
2196 int final_float = FLOAT_TYPE_P (type);
2197 int final_vec = TREE_CODE (type) == VECTOR_TYPE;
2198 unsigned int final_prec = TYPE_PRECISION (type);
2199 int final_unsignedp = TYPE_UNSIGNED (type);
2201 /* In addition to the cases of two conversions in a row
2202 handled below, if we are converting something to its own
2203 type via an object of identical or wider precision, neither
2204 conversion is needed. */
2205 if (useless_type_conversion_p (type, inside_type)
2206 && (((inter_int || inter_ptr) && final_int)
2207 || (inter_float && final_float))
2208 && inter_prec >= final_prec)
2210 gimple_assign_set_rhs1 (stmt, unshare_expr (defop0));
2211 gimple_assign_set_rhs_code (stmt, TREE_CODE (defop0));
2213 return remove_prop_source_from_use (op0) ? 2 : 1;
2216 /* Likewise, if the intermediate and initial types are either both
2217 float or both integer, we don't need the middle conversion if the
2218 former is wider than the latter and doesn't change the signedness
2219 (for integers). Avoid this if the final type is a pointer since
2220 then we sometimes need the middle conversion. Likewise if the
2221 final type has a precision not equal to the size of its mode. */
2222 if (((inter_int && inside_int)
2223 || (inter_float && inside_float)
2224 || (inter_vec && inside_vec))
2225 && inter_prec >= inside_prec
2226 && (inter_float || inter_vec
2227 || inter_unsignedp == inside_unsignedp)
2228 && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (type))
2229 && TYPE_MODE (type) == TYPE_MODE (inter_type))
2231 && (! final_vec || inter_prec == inside_prec))
2233 gimple_assign_set_rhs1 (stmt, defop0);
2235 return remove_prop_source_from_use (op0) ? 2 : 1;
2238 /* If we have a sign-extension of a zero-extended value, we can
2239 replace that by a single zero-extension. */
2240 if (inside_int && inter_int && final_int
2241 && inside_prec < inter_prec && inter_prec < final_prec
2242 && inside_unsignedp && !inter_unsignedp)
2244 gimple_assign_set_rhs1 (stmt, defop0);
2246 return remove_prop_source_from_use (op0) ? 2 : 1;
2249 /* Two conversions in a row are not needed unless:
2250 - some conversion is floating-point (overstrict for now), or
2251 - some conversion is a vector (overstrict for now), or
2252 - the intermediate type is narrower than both initial and
2254 - the intermediate type and innermost type differ in signedness,
2255 and the outermost type is wider than the intermediate, or
2256 - the initial type is a pointer type and the precisions of the
2257 intermediate and final types differ, or
2258 - the final type is a pointer type and the precisions of the
2259 initial and intermediate types differ. */
2260 if (! inside_float && ! inter_float && ! final_float
2261 && ! inside_vec && ! inter_vec && ! final_vec
2262 && (inter_prec >= inside_prec || inter_prec >= final_prec)
2263 && ! (inside_int && inter_int
2264 && inter_unsignedp != inside_unsignedp
2265 && inter_prec < final_prec)
2266 && ((inter_unsignedp && inter_prec > inside_prec)
2267 == (final_unsignedp && final_prec > inter_prec))
2268 && ! (inside_ptr && inter_prec != final_prec)
2269 && ! (final_ptr && inside_prec != inter_prec)
2270 && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (type))
2271 && TYPE_MODE (type) == TYPE_MODE (inter_type)))
2273 gimple_assign_set_rhs1 (stmt, defop0);
2275 return remove_prop_source_from_use (op0) ? 2 : 1;
2278 /* A truncation to an unsigned type should be canonicalized as
2279 bitwise and of a mask. */
2280 if (final_int && inter_int && inside_int
2281 && final_prec == inside_prec
2282 && final_prec > inter_prec
2286 tem = fold_build2 (BIT_AND_EXPR, inside_type,
2289 (inside_type, double_int_mask (inter_prec)));
2290 if (!useless_type_conversion_p (type, inside_type))
2292 tem = force_gimple_operand_gsi (gsi, tem, true, NULL_TREE, true,
2294 gimple_assign_set_rhs1 (stmt, tem);
2297 gimple_assign_set_rhs_from_tree (gsi, tem);
2298 update_stmt (gsi_stmt (*gsi));
2306 /* Main entry point for the forward propagation and statement combine
2310 ssa_forward_propagate_and_combine (void)
2313 unsigned int todoflags = 0;
2315 cfg_changed = false;
2319 gimple_stmt_iterator gsi, prev;
2320 bool prev_initialized;
2322 /* Apply forward propagation to all stmts in the basic-block.
2323 Note we update GSI within the loop as necessary. */
2324 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2326 gimple stmt = gsi_stmt (gsi);
2328 enum tree_code code;
2330 if (!is_gimple_assign (stmt))
2336 lhs = gimple_assign_lhs (stmt);
2337 rhs = gimple_assign_rhs1 (stmt);
2338 code = gimple_assign_rhs_code (stmt);
2339 if (TREE_CODE (lhs) != SSA_NAME
2340 || has_zero_uses (lhs))
2346 /* If this statement sets an SSA_NAME to an address,
2347 try to propagate the address into the uses of the SSA_NAME. */
2348 if (code == ADDR_EXPR
2349 /* Handle pointer conversions on invariant addresses
2350 as well, as this is valid gimple. */
2351 || (CONVERT_EXPR_CODE_P (code)
2352 && TREE_CODE (rhs) == ADDR_EXPR
2353 && POINTER_TYPE_P (TREE_TYPE (lhs))))
2355 tree base = get_base_address (TREE_OPERAND (rhs, 0));
2358 || decl_address_invariant_p (base))
2359 && !stmt_references_abnormal_ssa_name (stmt)
2360 && forward_propagate_addr_expr (lhs, rhs))
2362 release_defs (stmt);
2363 todoflags |= TODO_remove_unused_locals;
2364 gsi_remove (&gsi, true);
2369 else if (code == POINTER_PLUS_EXPR && can_propagate_from (stmt))
2371 if (TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST
2372 /* ??? Better adjust the interface to that function
2373 instead of building new trees here. */
2374 && forward_propagate_addr_expr
2378 fold_build2 (MEM_REF,
2379 TREE_TYPE (TREE_TYPE (rhs)),
2383 gimple_assign_rhs2 (stmt))))))
2385 release_defs (stmt);
2386 todoflags |= TODO_remove_unused_locals;
2387 gsi_remove (&gsi, true);
2389 else if (is_gimple_min_invariant (rhs))
2391 /* Make sure to fold &a[0] + off_1 here. */
2392 fold_stmt_inplace (stmt);
2394 if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
2400 else if (TREE_CODE_CLASS (code) == tcc_comparison)
2402 forward_propagate_comparison (stmt);
2409 /* Combine stmts with the stmts defining their operands.
2410 Note we update GSI within the loop as necessary. */
2411 prev_initialized = false;
2412 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
2414 gimple stmt = gsi_stmt (gsi);
2415 bool changed = false;
2417 switch (gimple_code (stmt))
2421 tree rhs1 = gimple_assign_rhs1 (stmt);
2422 enum tree_code code = gimple_assign_rhs_code (stmt);
2424 if ((code == BIT_NOT_EXPR
2425 || code == NEGATE_EXPR)
2426 && TREE_CODE (rhs1) == SSA_NAME)
2427 changed = simplify_not_neg_expr (&gsi);
2428 else if (code == COND_EXPR)
2430 /* In this case the entire COND_EXPR is in rhs1. */
2432 fold_defer_overflow_warnings ();
2433 did_something = forward_propagate_into_cond (&gsi);
2434 stmt = gsi_stmt (gsi);
2435 if (did_something == 2)
2437 fold_undefer_overflow_warnings
2438 (!TREE_NO_WARNING (rhs1) && did_something, stmt,
2439 WARN_STRICT_OVERFLOW_CONDITIONAL);
2440 changed = did_something != 0;
2442 else if (TREE_CODE_CLASS (code) == tcc_comparison)
2444 bool no_warning = gimple_no_warning_p (stmt);
2446 fold_defer_overflow_warnings ();
2447 did_something = forward_propagate_into_comparison (&gsi);
2448 if (did_something == 2)
2450 fold_undefer_overflow_warnings
2451 (!no_warning && changed,
2452 stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
2453 changed = did_something != 0;
2455 else if (code == BIT_AND_EXPR
2456 || code == BIT_IOR_EXPR
2457 || code == BIT_XOR_EXPR)
2458 changed = simplify_bitwise_binary (&gsi);
2459 else if (code == PLUS_EXPR
2460 || code == MINUS_EXPR)
2461 changed = associate_plusminus (stmt);
2462 else if (CONVERT_EXPR_CODE_P (code)
2463 || code == FLOAT_EXPR
2464 || code == FIX_TRUNC_EXPR)
2466 int did_something = combine_conversions (&gsi);
2467 if (did_something == 2)
2469 changed = did_something != 0;
2475 changed = simplify_gimple_switch (stmt);
2481 fold_defer_overflow_warnings ();
2482 did_something = forward_propagate_into_gimple_cond (stmt);
2483 if (did_something == 2)
2485 fold_undefer_overflow_warnings
2486 (did_something, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
2487 changed = did_something != 0;
2493 tree callee = gimple_call_fndecl (stmt);
2494 if (callee != NULL_TREE
2495 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
2496 changed = simplify_builtin_call (&gsi, callee);
2505 /* If the stmt changed then re-visit it and the statements
2506 inserted before it. */
2507 if (!prev_initialized)
2508 gsi = gsi_start_bb (bb);
2518 prev_initialized = true;
2525 todoflags |= TODO_cleanup_cfg;
2532 gate_forwprop (void)
2534 return flag_tree_forwprop;
2537 struct gimple_opt_pass pass_forwprop =
2541 "forwprop", /* name */
2542 gate_forwprop, /* gate */
2543 ssa_forward_propagate_and_combine, /* execute */
2546 0, /* static_pass_number */
2547 TV_TREE_FORWPROP, /* tv_id */
2548 PROP_cfg | PROP_ssa, /* properties_required */
2549 0, /* properties_provided */
2550 0, /* properties_destroyed */
2551 0, /* todo_flags_start */
2554 | TODO_verify_ssa /* todo_flags_finish */