1 /* Forward propagation of expressions for single use variables.
2 Copyright (C) 2004, 2005, 2007, 2008, 2009 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
28 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
32 #include "tree-pass.h"
33 #include "tree-dump.h"
34 #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:
150 We also propagate casts into SWITCH_EXPR and COND_EXPR conditions to
151 allow us to remove the cast and {NOT_EXPR,NEG_EXPR} into a subsequent
154 This will (of course) be extended as other needs arise. */
156 static bool forward_propagate_addr_expr (tree name, tree rhs);
158 /* Set to true if we delete EH edges during the optimization. */
159 static bool cfg_changed;
161 static tree rhs_to_tree (tree type, gimple stmt);
163 /* Get the next statement we can propagate NAME's value into skipping
164 trivial copies. Returns the statement that is suitable as a
165 propagation destination or NULL_TREE if there is no such one.
166 This only returns destinations in a single-use chain. FINAL_NAME_P
167 if non-NULL is written to the ssa name that represents the use. */
170 get_prop_dest_stmt (tree name, tree *final_name_p)
176 /* If name has multiple uses, bail out. */
177 if (!single_imm_use (name, &use, &use_stmt))
180 /* If this is not a trivial copy, we found it. */
181 if (!gimple_assign_copy_p (use_stmt)
182 || TREE_CODE (gimple_assign_lhs (use_stmt)) != SSA_NAME
183 || gimple_assign_rhs1 (use_stmt) != name)
186 /* Continue searching uses of the copy destination. */
187 name = gimple_assign_lhs (use_stmt);
191 *final_name_p = name;
196 /* Get the statement we can propagate from into NAME skipping
197 trivial copies. Returns the statement which defines the
198 propagation source or NULL_TREE if there is no such one.
199 If SINGLE_USE_ONLY is set considers only sources which have
200 a single use chain up to NAME. If SINGLE_USE_P is non-null,
201 it is set to whether the chain to NAME is a single use chain
202 or not. SINGLE_USE_P is not written to if SINGLE_USE_ONLY is set. */
205 get_prop_source_stmt (tree name, bool single_use_only, bool *single_use_p)
207 bool single_use = true;
210 gimple def_stmt = SSA_NAME_DEF_STMT (name);
212 if (!has_single_use (name))
219 /* If name is defined by a PHI node or is the default def, bail out. */
220 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
223 /* If name is not a simple copy destination, we found it. */
224 if (!gimple_assign_copy_p (def_stmt)
225 || TREE_CODE (gimple_assign_rhs1 (def_stmt)) != SSA_NAME)
229 if (!single_use_only && single_use_p)
230 *single_use_p = single_use;
232 /* We can look through pointer conversions in the search
233 for a useful stmt for the comparison folding. */
234 rhs = gimple_assign_rhs1 (def_stmt);
235 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))
236 && TREE_CODE (rhs) == SSA_NAME
237 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (def_stmt)))
238 && POINTER_TYPE_P (TREE_TYPE (rhs)))
245 /* Continue searching the def of the copy source name. */
246 name = gimple_assign_rhs1 (def_stmt);
251 /* Checks if the destination ssa name in DEF_STMT can be used as
252 propagation source. Returns true if so, otherwise false. */
255 can_propagate_from (gimple def_stmt)
260 gcc_assert (is_gimple_assign (def_stmt));
261 /* If the rhs has side-effects we cannot propagate from it. */
262 if (gimple_has_volatile_ops (def_stmt))
265 /* If the rhs is a load we cannot propagate from it. */
266 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_reference
267 || TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_declaration)
270 /* Constants can be always propagated. */
271 if (is_gimple_min_invariant
272 (rhs_to_tree (TREE_TYPE (gimple_assign_lhs (def_stmt)), def_stmt)))
275 /* We cannot propagate ssa names that occur in abnormal phi nodes. */
276 FOR_EACH_SSA_USE_OPERAND (use_p, def_stmt, iter, SSA_OP_USE)
277 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
280 /* If the definition is a conversion of a pointer to a function type,
281 then we can not apply optimizations as some targets require
282 function pointers to be canonicalized and in this case this
283 optimization could eliminate a necessary canonicalization. */
284 if (is_gimple_assign (def_stmt)
285 && (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))))
287 tree rhs = gimple_assign_rhs1 (def_stmt);
288 if (POINTER_TYPE_P (TREE_TYPE (rhs))
289 && TREE_CODE (TREE_TYPE (TREE_TYPE (rhs))) == FUNCTION_TYPE)
295 /* Remove a copy chain ending in NAME along the defs but not
296 further or including UP_TO_STMT. If NAME was replaced in
297 its only use then this function can be used to clean up
298 dead stmts. Returns true if UP_TO_STMT can be removed
299 as well, otherwise false. */
302 remove_prop_source_from_use (tree name, gimple up_to_stmt)
304 gimple_stmt_iterator gsi;
308 if (!has_zero_uses (name))
311 stmt = SSA_NAME_DEF_STMT (name);
312 if (stmt == up_to_stmt)
315 gsi = gsi_for_stmt (stmt);
317 gsi_remove (&gsi, true);
319 name = (gimple_assign_copy_p (stmt)) ? gimple_assign_rhs1 (stmt) : NULL;
320 } while (name && TREE_CODE (name) == SSA_NAME);
325 /* Return the rhs of a gimple_assign STMT in a form of a single tree,
326 converted to type TYPE.
328 This should disappear, but is needed so we can combine expressions and use
329 the fold() interfaces. Long term, we need to develop folding and combine
330 routines that deal with gimple exclusively . */
333 rhs_to_tree (tree type, gimple stmt)
335 enum tree_code code = gimple_assign_rhs_code (stmt);
336 if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
337 return fold_build2 (code, type, gimple_assign_rhs1 (stmt),
338 gimple_assign_rhs2 (stmt));
339 else if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
340 return build1 (code, type, gimple_assign_rhs1 (stmt));
341 else if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
342 return gimple_assign_rhs1 (stmt);
347 /* Combine OP0 CODE OP1 in the context of a COND_EXPR. Returns
348 the folded result in a form suitable for COND_EXPR_COND or
349 NULL_TREE, if there is no suitable simplified form. If
350 INVARIANT_ONLY is true only gimple_min_invariant results are
351 considered simplified. */
354 combine_cond_expr_cond (enum tree_code code, tree type,
355 tree op0, tree op1, bool invariant_only)
359 gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
361 t = fold_binary (code, type, op0, op1);
365 /* Require that we got a boolean type out if we put one in. */
366 gcc_assert (TREE_CODE (TREE_TYPE (t)) == TREE_CODE (type));
368 /* Canonicalize the combined condition for use in a COND_EXPR. */
369 t = canonicalize_cond_expr_cond (t);
371 /* Bail out if we required an invariant but didn't get one. */
372 if (!t || (invariant_only && !is_gimple_min_invariant (t)))
378 /* Propagate from the ssa name definition statements of COND_EXPR
379 in GIMPLE_COND statement STMT into the conditional if that simplifies it.
380 Returns zero if no statement was changed, one if there were
381 changes and two if cfg_cleanup needs to run.
383 This must be kept in sync with forward_propagate_into_cond. */
386 forward_propagate_into_gimple_cond (gimple stmt)
388 int did_something = 0;
391 tree tmp = NULL_TREE;
392 tree name, rhs0 = NULL_TREE, rhs1 = NULL_TREE;
394 bool single_use0_p = false, single_use1_p = false;
395 enum tree_code code = gimple_cond_code (stmt);
397 /* We can do tree combining on SSA_NAME and comparison expressions. */
398 if (TREE_CODE_CLASS (gimple_cond_code (stmt)) == tcc_comparison
399 && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME)
401 /* For comparisons use the first operand, that is likely to
402 simplify comparisons against constants. */
403 name = gimple_cond_lhs (stmt);
404 def_stmt = get_prop_source_stmt (name, false, &single_use0_p);
405 if (def_stmt && can_propagate_from (def_stmt))
407 tree op1 = gimple_cond_rhs (stmt);
408 rhs0 = rhs_to_tree (TREE_TYPE (op1), def_stmt);
409 tmp = combine_cond_expr_cond (code, boolean_type_node, rhs0,
410 op1, !single_use0_p);
412 /* If that wasn't successful, try the second operand. */
414 && TREE_CODE (gimple_cond_rhs (stmt)) == SSA_NAME)
416 tree op0 = gimple_cond_lhs (stmt);
417 name = gimple_cond_rhs (stmt);
418 def_stmt = get_prop_source_stmt (name, false, &single_use1_p);
419 if (!def_stmt || !can_propagate_from (def_stmt))
420 return did_something;
422 rhs1 = rhs_to_tree (TREE_TYPE (op0), def_stmt);
423 tmp = combine_cond_expr_cond (code, boolean_type_node, op0, rhs1,
426 /* If that wasn't successful either, try both operands. */
429 && rhs1 != NULL_TREE)
430 tmp = combine_cond_expr_cond (code, boolean_type_node, rhs0,
431 fold_convert (TREE_TYPE (rhs0), rhs1),
432 !(single_use0_p && single_use1_p));
437 if (dump_file && tmp)
439 tree cond = build2 (gimple_cond_code (stmt),
441 gimple_cond_lhs (stmt),
442 gimple_cond_rhs (stmt));
443 fprintf (dump_file, " Replaced '");
444 print_generic_expr (dump_file, cond, 0);
445 fprintf (dump_file, "' with '");
446 print_generic_expr (dump_file, tmp, 0);
447 fprintf (dump_file, "'\n");
450 gimple_cond_set_condition_from_tree (stmt, unshare_expr (tmp));
453 /* Remove defining statements. */
454 remove_prop_source_from_use (name, NULL);
456 if (is_gimple_min_invariant (tmp))
458 else if (did_something == 0)
461 /* Continue combining. */
468 return did_something;
472 /* Propagate from the ssa name definition statements of COND_EXPR
473 in the rhs of statement STMT into the conditional if that simplifies it.
474 Returns zero if no statement was changed, one if there were
475 changes and two if cfg_cleanup needs to run.
477 This must be kept in sync with forward_propagate_into_gimple_cond. */
480 forward_propagate_into_cond (gimple_stmt_iterator *gsi_p)
482 gimple stmt = gsi_stmt (*gsi_p);
483 int did_something = 0;
486 tree tmp = NULL_TREE;
487 tree cond = gimple_assign_rhs1 (stmt);
488 tree name, rhs0 = NULL_TREE, rhs1 = NULL_TREE;
490 bool single_use0_p = false, single_use1_p = false;
492 /* We can do tree combining on SSA_NAME and comparison expressions. */
493 if (COMPARISON_CLASS_P (cond)
494 && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME)
496 /* For comparisons use the first operand, that is likely to
497 simplify comparisons against constants. */
498 name = TREE_OPERAND (cond, 0);
499 def_stmt = get_prop_source_stmt (name, false, &single_use0_p);
500 if (def_stmt && can_propagate_from (def_stmt))
502 tree op1 = TREE_OPERAND (cond, 1);
503 rhs0 = rhs_to_tree (TREE_TYPE (op1), def_stmt);
504 tmp = combine_cond_expr_cond (TREE_CODE (cond), boolean_type_node,
505 rhs0, op1, !single_use0_p);
507 /* If that wasn't successful, try the second operand. */
509 && TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME)
511 tree op0 = TREE_OPERAND (cond, 0);
512 name = TREE_OPERAND (cond, 1);
513 def_stmt = get_prop_source_stmt (name, false, &single_use1_p);
514 if (!def_stmt || !can_propagate_from (def_stmt))
515 return did_something;
517 rhs1 = rhs_to_tree (TREE_TYPE (op0), def_stmt);
518 tmp = combine_cond_expr_cond (TREE_CODE (cond), boolean_type_node,
519 op0, rhs1, !single_use1_p);
521 /* If that wasn't successful either, try both operands. */
524 && rhs1 != NULL_TREE)
525 tmp = combine_cond_expr_cond (TREE_CODE (cond), boolean_type_node,
526 rhs0, fold_convert (TREE_TYPE (rhs0),
528 !(single_use0_p && single_use1_p));
530 else if (TREE_CODE (cond) == SSA_NAME)
533 def_stmt = get_prop_source_stmt (name, true, NULL);
534 if (def_stmt || !can_propagate_from (def_stmt))
535 return did_something;
537 rhs0 = gimple_assign_rhs1 (def_stmt);
538 tmp = combine_cond_expr_cond (NE_EXPR, boolean_type_node, rhs0,
539 build_int_cst (TREE_TYPE (rhs0), 0),
545 if (dump_file && tmp)
547 fprintf (dump_file, " Replaced '");
548 print_generic_expr (dump_file, cond, 0);
549 fprintf (dump_file, "' with '");
550 print_generic_expr (dump_file, tmp, 0);
551 fprintf (dump_file, "'\n");
554 gimple_assign_set_rhs_from_tree (gsi_p, unshare_expr (tmp));
555 stmt = gsi_stmt (*gsi_p);
558 /* Remove defining statements. */
559 remove_prop_source_from_use (name, NULL);
561 if (is_gimple_min_invariant (tmp))
563 else if (did_something == 0)
566 /* Continue combining. */
573 return did_something;
576 /* We've just substituted an ADDR_EXPR into stmt. Update all the
577 relevant data structures to match. */
580 tidy_after_forward_propagate_addr (gimple stmt)
582 /* We may have turned a trapping insn into a non-trapping insn. */
583 if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
584 && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
587 if (TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR)
588 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt));
590 mark_symbols_for_renaming (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);
616 /* Get the offset's defining statement. */
617 offset_def = SSA_NAME_DEF_STMT (offset);
619 /* Try to find an expression for a proper index. This is either a
620 multiplication expression by the element size or just the ssa name we came
621 along in case the element size is one. In that case, however, we do not
622 allow multiplications because they can be computing index to a higher
623 level dimension (PR 37861). */
624 if (integer_onep (TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (def_rhs)))))
626 if (is_gimple_assign (offset_def)
627 && gimple_assign_rhs_code (offset_def) == MULT_EXPR)
634 /* The statement which defines OFFSET before type conversion
635 must be a simple GIMPLE_ASSIGN. */
636 if (!is_gimple_assign (offset_def))
639 /* The RHS of the statement which defines OFFSET must be a
640 multiplication of an object by the size of the array elements.
641 This implicitly verifies that the size of the array elements
643 offset = gimple_assign_rhs1 (offset_def);
644 if (gimple_assign_rhs_code (offset_def) != MULT_EXPR
645 || TREE_CODE (gimple_assign_rhs2 (offset_def)) != INTEGER_CST
646 || !simple_cst_equal (gimple_assign_rhs2 (offset_def),
647 TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (def_rhs)))))
650 /* The first operand to the MULT_EXPR is the desired index. */
654 /* Replace the pointer addition with array indexing. */
655 gimple_assign_set_rhs_from_tree (use_stmt_gsi, unshare_expr (def_rhs));
656 use_stmt = gsi_stmt (*use_stmt_gsi);
657 TREE_OPERAND (TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0), 1)
660 /* That should have created gimple, so there is no need to
661 record information to undo the propagation. */
662 fold_stmt_inplace (use_stmt);
663 tidy_after_forward_propagate_addr (use_stmt);
667 /* NAME is a SSA_NAME representing DEF_RHS which is of the form
668 ADDR_EXPR <whatever>.
670 Try to forward propagate the ADDR_EXPR into the use USE_STMT.
671 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
672 node or for recovery of array indexing from pointer arithmetic.
674 Return true if the propagation was successful (the propagation can
675 be not totally successful, yet things may have been changed). */
678 forward_propagate_addr_expr_1 (tree name, tree def_rhs,
679 gimple_stmt_iterator *use_stmt_gsi,
682 tree lhs, rhs, rhs2, array_ref;
684 gimple use_stmt = gsi_stmt (*use_stmt_gsi);
685 enum tree_code rhs_code;
687 gcc_assert (TREE_CODE (def_rhs) == ADDR_EXPR);
689 lhs = gimple_assign_lhs (use_stmt);
690 rhs_code = gimple_assign_rhs_code (use_stmt);
691 rhs = gimple_assign_rhs1 (use_stmt);
693 /* Trivial cases. The use statement could be a trivial copy or a
694 useless conversion. Recurse to the uses of the lhs as copyprop does
695 not copy through different variant pointers and FRE does not catch
696 all useless conversions. Treat the case of a single-use name and
697 a conversion to def_rhs type separate, though. */
698 if (TREE_CODE (lhs) == SSA_NAME
699 && ((rhs_code == SSA_NAME && rhs == name)
700 || CONVERT_EXPR_CODE_P (rhs_code)))
702 /* Only recurse if we don't deal with a single use or we cannot
703 do the propagation to the current statement. In particular
704 we can end up with a conversion needed for a non-invariant
705 address which we cannot do in a single statement. */
707 || (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs))
708 && !is_gimple_min_invariant (def_rhs)))
709 return forward_propagate_addr_expr (lhs, def_rhs);
711 gimple_assign_set_rhs1 (use_stmt, unshare_expr (def_rhs));
712 if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
713 gimple_assign_set_rhs_code (use_stmt, TREE_CODE (def_rhs));
715 gimple_assign_set_rhs_code (use_stmt, NOP_EXPR);
719 /* Now strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
720 ADDR_EXPR will not appear on the LHS. */
721 lhsp = gimple_assign_lhs_ptr (use_stmt);
722 while (handled_component_p (*lhsp))
723 lhsp = &TREE_OPERAND (*lhsp, 0);
726 /* Now see if the LHS node is an INDIRECT_REF using NAME. If so,
727 propagate the ADDR_EXPR into the use of NAME and fold the result. */
728 if (TREE_CODE (lhs) == INDIRECT_REF
729 && TREE_OPERAND (lhs, 0) == name
730 && may_propagate_address_into_dereference (def_rhs, lhs)
731 && (lhsp != gimple_assign_lhs_ptr (use_stmt)
732 || useless_type_conversion_p (TREE_TYPE (TREE_OPERAND (def_rhs, 0)),
735 *lhsp = unshare_expr (TREE_OPERAND (def_rhs, 0));
736 fold_stmt_inplace (use_stmt);
737 tidy_after_forward_propagate_addr (use_stmt);
739 /* Continue propagating into the RHS if this was not the only use. */
744 /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
745 nodes from the RHS. */
746 rhsp = gimple_assign_rhs1_ptr (use_stmt);
747 while (handled_component_p (*rhsp)
748 || TREE_CODE (*rhsp) == ADDR_EXPR)
749 rhsp = &TREE_OPERAND (*rhsp, 0);
752 /* Now see if the RHS node is an INDIRECT_REF using NAME. If so,
753 propagate the ADDR_EXPR into the use of NAME and fold the result. */
754 if (TREE_CODE (rhs) == INDIRECT_REF
755 && TREE_OPERAND (rhs, 0) == name
756 && may_propagate_address_into_dereference (def_rhs, rhs))
758 *rhsp = unshare_expr (TREE_OPERAND (def_rhs, 0));
759 fold_stmt_inplace (use_stmt);
760 tidy_after_forward_propagate_addr (use_stmt);
764 /* Now see if the RHS node is an INDIRECT_REF using NAME. If so,
765 propagate the ADDR_EXPR into the use of NAME and try to
766 create a VCE and fold the result. */
767 if (TREE_CODE (rhs) == INDIRECT_REF
768 && TREE_OPERAND (rhs, 0) == name
769 && TYPE_SIZE (TREE_TYPE (rhs))
770 && TYPE_SIZE (TREE_TYPE (TREE_OPERAND (def_rhs, 0)))
771 /* Function decls should not be used for VCE either as it could be a
772 function descriptor that we want and not the actual function code. */
773 && TREE_CODE (TREE_OPERAND (def_rhs, 0)) != FUNCTION_DECL
774 /* We should not convert volatile loads to non volatile loads. */
775 && !TYPE_VOLATILE (TREE_TYPE (rhs))
776 && !TYPE_VOLATILE (TREE_TYPE (TREE_OPERAND (def_rhs, 0)))
777 && operand_equal_p (TYPE_SIZE (TREE_TYPE (rhs)),
778 TYPE_SIZE (TREE_TYPE (TREE_OPERAND (def_rhs, 0))), 0))
780 tree def_rhs_base, new_rhs = unshare_expr (TREE_OPERAND (def_rhs, 0));
781 new_rhs = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (rhs), new_rhs);
782 if (TREE_CODE (new_rhs) != VIEW_CONVERT_EXPR)
784 /* If we have folded the VIEW_CONVERT_EXPR then the result is only
785 valid if we can replace the whole rhs of the use statement. */
786 if (rhs != gimple_assign_rhs1 (use_stmt))
788 new_rhs = force_gimple_operand_gsi (use_stmt_gsi, new_rhs, true, NULL,
790 gimple_assign_set_rhs1 (use_stmt, new_rhs);
791 tidy_after_forward_propagate_addr (use_stmt);
794 /* If the defining rhs comes from an indirect reference, then do not
795 convert into a VIEW_CONVERT_EXPR. */
796 def_rhs_base = TREE_OPERAND (def_rhs, 0);
797 while (handled_component_p (def_rhs_base))
798 def_rhs_base = TREE_OPERAND (def_rhs_base, 0);
799 if (!INDIRECT_REF_P (def_rhs_base))
801 /* We may have arbitrary VIEW_CONVERT_EXPRs in a nested component
802 reference. Place it there and fold the thing. */
804 fold_stmt_inplace (use_stmt);
805 tidy_after_forward_propagate_addr (use_stmt);
810 /* If the use of the ADDR_EXPR is not a POINTER_PLUS_EXPR, there
812 if (gimple_assign_rhs_code (use_stmt) != POINTER_PLUS_EXPR
813 || gimple_assign_rhs1 (use_stmt) != name)
816 /* The remaining cases are all for turning pointer arithmetic into
817 array indexing. They only apply when we have the address of
818 element zero in an array. If that is not the case then there
820 array_ref = TREE_OPERAND (def_rhs, 0);
821 if (TREE_CODE (array_ref) != ARRAY_REF
822 || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE
823 || !integer_zerop (TREE_OPERAND (array_ref, 1)))
826 rhs2 = gimple_assign_rhs2 (use_stmt);
827 /* Try to optimize &x[0] p+ C where C is a multiple of the size
828 of the elements in X into &x[C/element size]. */
829 if (TREE_CODE (rhs2) == INTEGER_CST)
831 tree new_rhs = maybe_fold_stmt_addition (gimple_expr_type (use_stmt),
835 gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs);
836 use_stmt = gsi_stmt (*use_stmt_gsi);
837 update_stmt (use_stmt);
838 tidy_after_forward_propagate_addr (use_stmt);
843 /* Try to optimize &x[0] p+ OFFSET where OFFSET is defined by
844 converting a multiplication of an index by the size of the
845 array elements, then the result is converted into the proper
846 type for the arithmetic. */
847 if (TREE_CODE (rhs2) == SSA_NAME
848 && useless_type_conversion_p (TREE_TYPE (name), TREE_TYPE (def_rhs))
849 /* Avoid problems with IVopts creating PLUS_EXPRs with a
850 different type than their operands. */
851 && useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
852 return forward_propagate_addr_into_variable_array_index (rhs2, def_rhs,
857 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
859 Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME.
860 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
861 node or for recovery of array indexing from pointer arithmetic.
862 Returns true, if all uses have been propagated into. */
865 forward_propagate_addr_expr (tree name, tree rhs)
867 int stmt_loop_depth = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_depth;
868 imm_use_iterator iter;
871 bool single_use_p = has_single_use (name);
873 FOR_EACH_IMM_USE_STMT (use_stmt, iter, name)
878 /* If the use is not in a simple assignment statement, then
879 there is nothing we can do. */
880 if (gimple_code (use_stmt) != GIMPLE_ASSIGN)
886 /* If the use is in a deeper loop nest, then we do not want
887 to propagate the ADDR_EXPR into the loop as that is likely
888 adding expression evaluations into the loop. */
889 if (gimple_bb (use_stmt)->loop_depth > stmt_loop_depth)
895 push_stmt_changes (&use_stmt);
898 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
899 result = forward_propagate_addr_expr_1 (name, rhs, &gsi,
901 use_stmt = gsi_stmt (gsi);
905 pop_stmt_changes (&use_stmt);
907 /* Remove intermediate now unused copy and conversion chains. */
908 use_rhs = gimple_assign_rhs1 (use_stmt);
910 && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
911 && (TREE_CODE (use_rhs) == SSA_NAME
912 || (CONVERT_EXPR_P (use_rhs)
913 && TREE_CODE (TREE_OPERAND (use_rhs, 0)) == SSA_NAME)))
915 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
916 release_defs (use_stmt);
917 gsi_remove (&gsi, true);
924 /* Forward propagate the comparison defined in STMT like
925 cond_1 = x CMP y to uses of the form
929 Returns true if stmt is now unused. */
932 forward_propagate_comparison (gimple stmt)
934 tree name = gimple_assign_lhs (stmt);
936 tree tmp = NULL_TREE;
938 /* Don't propagate ssa names that occur in abnormal phis. */
939 if ((TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
940 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)))
941 || (TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME
942 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs2 (stmt))))
945 /* Do not un-cse comparisons. But propagate through copies. */
946 use_stmt = get_prop_dest_stmt (name, &name);
950 /* Conversion of the condition result to another integral type. */
951 if (is_gimple_assign (use_stmt)
952 && (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt))
953 || TREE_CODE_CLASS (gimple_assign_rhs_code (use_stmt))
955 || gimple_assign_rhs_code (use_stmt) == TRUTH_NOT_EXPR)
956 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (use_stmt))))
958 tree lhs = gimple_assign_lhs (use_stmt);
960 /* We can propagate the condition into a conversion. */
961 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt)))
963 /* Avoid using fold here as that may create a COND_EXPR with
964 non-boolean condition as canonical form. */
965 tmp = build2 (gimple_assign_rhs_code (stmt), TREE_TYPE (lhs),
966 gimple_assign_rhs1 (stmt), gimple_assign_rhs2 (stmt));
968 /* We can propagate the condition into X op CST where op
969 is EQ_EXPR or NE_EXPR and CST is either one or zero. */
970 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (use_stmt))
972 && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == SSA_NAME
973 && TREE_CODE (gimple_assign_rhs2 (use_stmt)) == INTEGER_CST)
975 enum tree_code code = gimple_assign_rhs_code (use_stmt);
976 tree cst = gimple_assign_rhs2 (use_stmt);
979 cond = build2 (gimple_assign_rhs_code (stmt),
981 gimple_assign_rhs1 (stmt),
982 gimple_assign_rhs2 (stmt));
984 tmp = combine_cond_expr_cond (code, TREE_TYPE (lhs), cond, cst, false);
985 if (tmp == NULL_TREE)
988 /* We can propagate the condition into a statement that
989 computes the logical negation of the comparison result. */
990 else if (gimple_assign_rhs_code (use_stmt) == TRUTH_NOT_EXPR)
992 tree type = TREE_TYPE (gimple_assign_rhs1 (stmt));
993 bool nans = HONOR_NANS (TYPE_MODE (type));
995 code = invert_tree_comparison (gimple_assign_rhs_code (stmt), nans);
996 if (code == ERROR_MARK)
999 tmp = build2 (code, TREE_TYPE (lhs), gimple_assign_rhs1 (stmt),
1000 gimple_assign_rhs2 (stmt));
1006 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1007 gimple_assign_set_rhs_from_tree (&gsi, unshare_expr (tmp));
1008 use_stmt = gsi_stmt (gsi);
1009 update_stmt (use_stmt);
1012 /* Remove defining statements. */
1013 remove_prop_source_from_use (name, stmt);
1015 if (dump_file && (dump_flags & TDF_DETAILS))
1017 tree old_rhs = rhs_to_tree (TREE_TYPE (gimple_assign_lhs (stmt)),
1019 fprintf (dump_file, " Replaced '");
1020 print_generic_expr (dump_file, old_rhs, dump_flags);
1021 fprintf (dump_file, "' with '");
1022 print_generic_expr (dump_file, tmp, dump_flags);
1023 fprintf (dump_file, "'\n");
1032 /* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y.
1033 If so, we can change STMT into lhs = y which can later be copy
1034 propagated. Similarly for negation.
1036 This could trivially be formulated as a forward propagation
1037 to immediate uses. However, we already had an implementation
1038 from DOM which used backward propagation via the use-def links.
1040 It turns out that backward propagation is actually faster as
1041 there's less work to do for each NOT/NEG expression we find.
1042 Backwards propagation needs to look at the statement in a single
1043 backlink. Forward propagation needs to look at potentially more
1044 than one forward link. */
1047 simplify_not_neg_expr (gimple_stmt_iterator *gsi_p)
1049 gimple stmt = gsi_stmt (*gsi_p);
1050 tree rhs = gimple_assign_rhs1 (stmt);
1051 gimple rhs_def_stmt = SSA_NAME_DEF_STMT (rhs);
1053 /* See if the RHS_DEF_STMT has the same form as our statement. */
1054 if (is_gimple_assign (rhs_def_stmt)
1055 && gimple_assign_rhs_code (rhs_def_stmt) == gimple_assign_rhs_code (stmt))
1057 tree rhs_def_operand = gimple_assign_rhs1 (rhs_def_stmt);
1059 /* Verify that RHS_DEF_OPERAND is a suitable SSA_NAME. */
1060 if (TREE_CODE (rhs_def_operand) == SSA_NAME
1061 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand))
1063 gimple_assign_set_rhs_from_tree (gsi_p, rhs_def_operand);
1064 stmt = gsi_stmt (*gsi_p);
1070 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
1071 the condition which we may be able to optimize better. */
1074 simplify_gimple_switch (gimple stmt)
1076 tree cond = gimple_switch_index (stmt);
1080 /* The optimization that we really care about is removing unnecessary
1081 casts. That will let us do much better in propagating the inferred
1082 constant at the switch target. */
1083 if (TREE_CODE (cond) == SSA_NAME)
1085 def_stmt = SSA_NAME_DEF_STMT (cond);
1086 if (is_gimple_assign (def_stmt))
1088 if (gimple_assign_rhs_code (def_stmt) == NOP_EXPR)
1093 def = gimple_assign_rhs1 (def_stmt);
1095 #ifdef ENABLE_CHECKING
1096 /* ??? Why was Jeff testing this? We are gimple... */
1097 gcc_assert (is_gimple_val (def));
1100 to = TREE_TYPE (cond);
1101 ti = TREE_TYPE (def);
1103 /* If we have an extension that preserves value, then we
1104 can copy the source value into the switch. */
1106 need_precision = TYPE_PRECISION (ti);
1108 if (! INTEGRAL_TYPE_P (ti))
1110 else if (TYPE_UNSIGNED (to) && !TYPE_UNSIGNED (ti))
1112 else if (!TYPE_UNSIGNED (to) && TYPE_UNSIGNED (ti))
1113 need_precision += 1;
1114 if (TYPE_PRECISION (to) < need_precision)
1119 gimple_switch_set_index (stmt, def);
1127 /* Main entry point for the forward propagation optimizer. */
1130 tree_ssa_forward_propagate_single_use_vars (void)
1133 unsigned int todoflags = 0;
1135 cfg_changed = false;
1139 gimple_stmt_iterator gsi;
1141 /* Note we update GSI within the loop as necessary. */
1142 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
1144 gimple stmt = gsi_stmt (gsi);
1146 /* If this statement sets an SSA_NAME to an address,
1147 try to propagate the address into the uses of the SSA_NAME. */
1148 if (is_gimple_assign (stmt))
1150 tree lhs = gimple_assign_lhs (stmt);
1151 tree rhs = gimple_assign_rhs1 (stmt);
1153 if (TREE_CODE (lhs) != SSA_NAME)
1159 if (gimple_assign_rhs_code (stmt) == ADDR_EXPR
1160 /* Handle pointer conversions on invariant addresses
1161 as well, as this is valid gimple. */
1162 || (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
1163 && TREE_CODE (rhs) == ADDR_EXPR
1164 && POINTER_TYPE_P (TREE_TYPE (lhs))))
1167 if (!stmt_references_abnormal_ssa_name (stmt)
1168 && forward_propagate_addr_expr (lhs, rhs))
1170 release_defs (stmt);
1171 todoflags |= TODO_remove_unused_locals;
1172 gsi_remove (&gsi, true);
1177 else if ((gimple_assign_rhs_code (stmt) == BIT_NOT_EXPR
1178 || gimple_assign_rhs_code (stmt) == NEGATE_EXPR)
1179 && TREE_CODE (rhs) == SSA_NAME)
1181 simplify_not_neg_expr (&gsi);
1184 else if (gimple_assign_rhs_code (stmt) == COND_EXPR)
1186 /* In this case the entire COND_EXPR is in rhs1. */
1188 fold_defer_overflow_warnings ();
1189 did_something = forward_propagate_into_cond (&gsi);
1190 stmt = gsi_stmt (gsi);
1191 if (did_something == 2)
1193 fold_undefer_overflow_warnings (!TREE_NO_WARNING (rhs)
1194 && did_something, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
1197 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt))
1200 if (forward_propagate_comparison (stmt))
1202 release_defs (stmt);
1203 todoflags |= TODO_remove_unused_locals;
1204 gsi_remove (&gsi, true);
1212 else if (gimple_code (stmt) == GIMPLE_SWITCH)
1214 simplify_gimple_switch (stmt);
1217 else if (gimple_code (stmt) == GIMPLE_COND)
1220 fold_defer_overflow_warnings ();
1221 did_something = forward_propagate_into_gimple_cond (stmt);
1222 if (did_something == 2)
1224 fold_undefer_overflow_warnings (did_something, stmt,
1225 WARN_STRICT_OVERFLOW_CONDITIONAL);
1234 todoflags |= TODO_cleanup_cfg;
1240 gate_forwprop (void)
1245 struct gimple_opt_pass pass_forwprop =
1249 "forwprop", /* name */
1250 gate_forwprop, /* gate */
1251 tree_ssa_forward_propagate_single_use_vars, /* execute */
1254 0, /* static_pass_number */
1255 TV_TREE_FORWPROP, /* tv_id */
1256 PROP_cfg | PROP_ssa, /* properties_required */
1257 0, /* properties_provided */
1258 0, /* properties_destroyed */
1259 0, /* todo_flags_start */
1263 | TODO_verify_ssa /* todo_flags_finish */