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:
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
)
266 gcc_assert (is_gimple_assign (def_stmt
));
268 /* If the rhs has side-effects we cannot propagate from it. */
269 if (gimple_has_volatile_ops (def_stmt
))
272 /* If the rhs is a load we cannot propagate from it. */
273 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt
)) == tcc_reference
274 || TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt
)) == tcc_declaration
)
277 /* Constants can be always propagated. */
278 if (gimple_assign_single_p (def_stmt
)
279 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt
)))
282 /* We cannot propagate ssa names that occur in abnormal phi nodes. */
283 FOR_EACH_SSA_USE_OPERAND (use_p
, def_stmt
, iter
, SSA_OP_USE
)
284 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p
)))
287 /* If the definition is a conversion of a pointer to a function type,
288 then we can not apply optimizations as some targets require
289 function pointers to be canonicalized and in this case this
290 optimization could eliminate a necessary canonicalization. */
291 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
293 tree rhs
= gimple_assign_rhs1 (def_stmt
);
294 if (POINTER_TYPE_P (TREE_TYPE (rhs
))
295 && TREE_CODE (TREE_TYPE (TREE_TYPE (rhs
))) == FUNCTION_TYPE
)
302 /* Remove a copy chain ending in NAME along the defs but not
303 further or including UP_TO_STMT. If NAME was replaced in
304 its only use then this function can be used to clean up
305 dead stmts. Returns true if UP_TO_STMT can be removed
306 as well, otherwise false. */
309 remove_prop_source_from_use (tree name
, gimple up_to_stmt
)
311 gimple_stmt_iterator gsi
;
315 if (!has_zero_uses (name
))
318 stmt
= SSA_NAME_DEF_STMT (name
);
319 if (stmt
== up_to_stmt
)
322 gsi
= gsi_for_stmt (stmt
);
324 gsi_remove (&gsi
, true);
326 name
= (gimple_assign_copy_p (stmt
)) ? gimple_assign_rhs1 (stmt
) : NULL
;
327 } while (name
&& TREE_CODE (name
) == SSA_NAME
);
332 /* Return the rhs of a gimple_assign STMT in a form of a single tree,
333 converted to type TYPE.
335 This should disappear, but is needed so we can combine expressions and use
336 the fold() interfaces. Long term, we need to develop folding and combine
337 routines that deal with gimple exclusively . */
340 rhs_to_tree (tree type
, gimple stmt
)
342 enum tree_code code
= gimple_assign_rhs_code (stmt
);
343 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
344 return fold_build2 (code
, type
, gimple_assign_rhs1 (stmt
),
345 gimple_assign_rhs2 (stmt
));
346 else if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
347 return build1 (code
, type
, gimple_assign_rhs1 (stmt
));
348 else if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
349 return gimple_assign_rhs1 (stmt
);
354 /* Combine OP0 CODE OP1 in the context of a COND_EXPR. Returns
355 the folded result in a form suitable for COND_EXPR_COND or
356 NULL_TREE, if there is no suitable simplified form. If
357 INVARIANT_ONLY is true only gimple_min_invariant results are
358 considered simplified. */
361 combine_cond_expr_cond (enum tree_code code
, tree type
,
362 tree op0
, tree op1
, bool invariant_only
)
366 gcc_assert (TREE_CODE_CLASS (code
) == tcc_comparison
);
368 t
= fold_binary (code
, type
, op0
, op1
);
372 /* Require that we got a boolean type out if we put one in. */
373 gcc_assert (TREE_CODE (TREE_TYPE (t
)) == TREE_CODE (type
));
375 /* Canonicalize the combined condition for use in a COND_EXPR. */
376 t
= canonicalize_cond_expr_cond (t
);
378 /* Bail out if we required an invariant but didn't get one. */
379 if (!t
|| (invariant_only
&& !is_gimple_min_invariant (t
)))
385 /* Propagate from the ssa name definition statements of COND_EXPR
386 in GIMPLE_COND statement STMT into the conditional if that simplifies it.
387 Returns zero if no statement was changed, one if there were
388 changes and two if cfg_cleanup needs to run.
390 This must be kept in sync with forward_propagate_into_cond. */
393 forward_propagate_into_gimple_cond (gimple stmt
)
395 int did_something
= 0;
398 tree tmp
= NULL_TREE
;
399 tree name
, rhs0
= NULL_TREE
, rhs1
= NULL_TREE
;
401 bool single_use0_p
= false, single_use1_p
= false;
402 enum tree_code code
= gimple_cond_code (stmt
);
404 /* We can do tree combining on SSA_NAME and comparison expressions. */
405 if (TREE_CODE_CLASS (gimple_cond_code (stmt
)) == tcc_comparison
406 && TREE_CODE (gimple_cond_lhs (stmt
)) == SSA_NAME
)
408 /* For comparisons use the first operand, that is likely to
409 simplify comparisons against constants. */
410 name
= gimple_cond_lhs (stmt
);
411 def_stmt
= get_prop_source_stmt (name
, false, &single_use0_p
);
412 if (def_stmt
&& can_propagate_from (def_stmt
))
414 tree op1
= gimple_cond_rhs (stmt
);
415 rhs0
= rhs_to_tree (TREE_TYPE (op1
), def_stmt
);
416 tmp
= combine_cond_expr_cond (code
, boolean_type_node
, rhs0
,
417 op1
, !single_use0_p
);
419 /* If that wasn't successful, try the second operand. */
421 && TREE_CODE (gimple_cond_rhs (stmt
)) == SSA_NAME
)
423 tree op0
= gimple_cond_lhs (stmt
);
424 name
= gimple_cond_rhs (stmt
);
425 def_stmt
= get_prop_source_stmt (name
, false, &single_use1_p
);
426 if (!def_stmt
|| !can_propagate_from (def_stmt
))
427 return did_something
;
429 rhs1
= rhs_to_tree (TREE_TYPE (op0
), def_stmt
);
430 tmp
= combine_cond_expr_cond (code
, boolean_type_node
, op0
, rhs1
,
433 /* If that wasn't successful either, try both operands. */
436 && rhs1
!= NULL_TREE
)
437 tmp
= combine_cond_expr_cond (code
, boolean_type_node
, rhs0
,
438 fold_convert (TREE_TYPE (rhs0
), rhs1
),
439 !(single_use0_p
&& single_use1_p
));
444 if (dump_file
&& tmp
)
446 tree cond
= build2 (gimple_cond_code (stmt
),
448 gimple_cond_lhs (stmt
),
449 gimple_cond_rhs (stmt
));
450 fprintf (dump_file
, " Replaced '");
451 print_generic_expr (dump_file
, cond
, 0);
452 fprintf (dump_file
, "' with '");
453 print_generic_expr (dump_file
, tmp
, 0);
454 fprintf (dump_file
, "'\n");
457 gimple_cond_set_condition_from_tree (stmt
, unshare_expr (tmp
));
460 /* Remove defining statements. */
461 remove_prop_source_from_use (name
, NULL
);
463 if (is_gimple_min_invariant (tmp
))
465 else if (did_something
== 0)
468 /* Continue combining. */
475 return did_something
;
479 /* Propagate from the ssa name definition statements of COND_EXPR
480 in the rhs of statement STMT into the conditional if that simplifies it.
481 Returns zero if no statement was changed, one if there were
482 changes and two if cfg_cleanup needs to run.
484 This must be kept in sync with forward_propagate_into_gimple_cond. */
487 forward_propagate_into_cond (gimple_stmt_iterator
*gsi_p
)
489 gimple stmt
= gsi_stmt (*gsi_p
);
490 int did_something
= 0;
493 tree tmp
= NULL_TREE
;
494 tree cond
= gimple_assign_rhs1 (stmt
);
495 tree name
, rhs0
= NULL_TREE
, rhs1
= NULL_TREE
;
497 bool single_use0_p
= false, single_use1_p
= false;
499 /* We can do tree combining on SSA_NAME and comparison expressions. */
500 if (COMPARISON_CLASS_P (cond
)
501 && TREE_CODE (TREE_OPERAND (cond
, 0)) == SSA_NAME
)
503 /* For comparisons use the first operand, that is likely to
504 simplify comparisons against constants. */
505 name
= TREE_OPERAND (cond
, 0);
506 def_stmt
= get_prop_source_stmt (name
, false, &single_use0_p
);
507 if (def_stmt
&& can_propagate_from (def_stmt
))
509 tree op1
= TREE_OPERAND (cond
, 1);
510 rhs0
= rhs_to_tree (TREE_TYPE (op1
), def_stmt
);
511 tmp
= combine_cond_expr_cond (TREE_CODE (cond
), boolean_type_node
,
512 rhs0
, op1
, !single_use0_p
);
514 /* If that wasn't successful, try the second operand. */
516 && TREE_CODE (TREE_OPERAND (cond
, 1)) == SSA_NAME
)
518 tree op0
= TREE_OPERAND (cond
, 0);
519 name
= TREE_OPERAND (cond
, 1);
520 def_stmt
= get_prop_source_stmt (name
, false, &single_use1_p
);
521 if (!def_stmt
|| !can_propagate_from (def_stmt
))
522 return did_something
;
524 rhs1
= rhs_to_tree (TREE_TYPE (op0
), def_stmt
);
525 tmp
= combine_cond_expr_cond (TREE_CODE (cond
), boolean_type_node
,
526 op0
, rhs1
, !single_use1_p
);
528 /* If that wasn't successful either, try both operands. */
531 && rhs1
!= NULL_TREE
)
532 tmp
= combine_cond_expr_cond (TREE_CODE (cond
), boolean_type_node
,
533 rhs0
, fold_convert (TREE_TYPE (rhs0
),
535 !(single_use0_p
&& single_use1_p
));
537 else if (TREE_CODE (cond
) == SSA_NAME
)
540 def_stmt
= get_prop_source_stmt (name
, true, NULL
);
541 if (def_stmt
|| !can_propagate_from (def_stmt
))
542 return did_something
;
544 rhs0
= gimple_assign_rhs1 (def_stmt
);
545 tmp
= combine_cond_expr_cond (NE_EXPR
, boolean_type_node
, rhs0
,
546 build_int_cst (TREE_TYPE (rhs0
), 0),
552 if (dump_file
&& tmp
)
554 fprintf (dump_file
, " Replaced '");
555 print_generic_expr (dump_file
, cond
, 0);
556 fprintf (dump_file
, "' with '");
557 print_generic_expr (dump_file
, tmp
, 0);
558 fprintf (dump_file
, "'\n");
561 gimple_assign_set_rhs_from_tree (gsi_p
, unshare_expr (tmp
));
562 stmt
= gsi_stmt (*gsi_p
);
565 /* Remove defining statements. */
566 remove_prop_source_from_use (name
, NULL
);
568 if (is_gimple_min_invariant (tmp
))
570 else if (did_something
== 0)
573 /* Continue combining. */
580 return did_something
;
583 /* We've just substituted an ADDR_EXPR into stmt. Update all the
584 relevant data structures to match. */
587 tidy_after_forward_propagate_addr (gimple stmt
)
589 /* We may have turned a trapping insn into a non-trapping insn. */
590 if (maybe_clean_or_replace_eh_stmt (stmt
, stmt
)
591 && gimple_purge_dead_eh_edges (gimple_bb (stmt
)))
594 if (TREE_CODE (gimple_assign_rhs1 (stmt
)) == ADDR_EXPR
)
595 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt
));
598 /* DEF_RHS contains the address of the 0th element in an array.
599 USE_STMT uses type of DEF_RHS to compute the address of an
600 arbitrary element within the array. The (variable) byte offset
601 of the element is contained in OFFSET.
603 We walk back through the use-def chains of OFFSET to verify that
604 it is indeed computing the offset of an element within the array
605 and extract the index corresponding to the given byte offset.
607 We then try to fold the entire address expression into a form
610 If we are successful, we replace the right hand side of USE_STMT
611 with the new address computation. */
614 forward_propagate_addr_into_variable_array_index (tree offset
,
616 gimple_stmt_iterator
*use_stmt_gsi
)
619 gimple offset_def
, use_stmt
= gsi_stmt (*use_stmt_gsi
);
622 tunit
= TYPE_SIZE_UNIT (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 gimple_assign_set_rhs_from_tree (use_stmt_gsi
, unshare_expr (def_rhs
));
690 use_stmt
= gsi_stmt (*use_stmt_gsi
);
691 TREE_OPERAND (TREE_OPERAND (gimple_assign_rhs1 (use_stmt
), 0), 1)
694 /* That should have created gimple, so there is no need to
695 record information to undo the propagation. */
696 fold_stmt_inplace (use_stmt
);
697 tidy_after_forward_propagate_addr (use_stmt
);
701 /* NAME is a SSA_NAME representing DEF_RHS which is of the form
702 ADDR_EXPR <whatever>.
704 Try to forward propagate the ADDR_EXPR into the use USE_STMT.
705 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
706 node or for recovery of array indexing from pointer arithmetic.
708 Return true if the propagation was successful (the propagation can
709 be not totally successful, yet things may have been changed). */
712 forward_propagate_addr_expr_1 (tree name
, tree def_rhs
,
713 gimple_stmt_iterator
*use_stmt_gsi
,
716 tree lhs
, rhs
, rhs2
, array_ref
;
718 gimple use_stmt
= gsi_stmt (*use_stmt_gsi
);
719 enum tree_code rhs_code
;
721 gcc_assert (TREE_CODE (def_rhs
) == ADDR_EXPR
);
723 lhs
= gimple_assign_lhs (use_stmt
);
724 rhs_code
= gimple_assign_rhs_code (use_stmt
);
725 rhs
= gimple_assign_rhs1 (use_stmt
);
727 /* Trivial cases. The use statement could be a trivial copy or a
728 useless conversion. Recurse to the uses of the lhs as copyprop does
729 not copy through different variant pointers and FRE does not catch
730 all useless conversions. Treat the case of a single-use name and
731 a conversion to def_rhs type separate, though. */
732 if (TREE_CODE (lhs
) == SSA_NAME
733 && ((rhs_code
== SSA_NAME
&& rhs
== name
)
734 || CONVERT_EXPR_CODE_P (rhs_code
)))
736 /* Only recurse if we don't deal with a single use or we cannot
737 do the propagation to the current statement. In particular
738 we can end up with a conversion needed for a non-invariant
739 address which we cannot do in a single statement. */
741 || (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (def_rhs
))
742 && !is_gimple_min_invariant (def_rhs
)))
743 return forward_propagate_addr_expr (lhs
, def_rhs
);
745 gimple_assign_set_rhs1 (use_stmt
, unshare_expr (def_rhs
));
746 if (useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (def_rhs
)))
747 gimple_assign_set_rhs_code (use_stmt
, TREE_CODE (def_rhs
));
749 gimple_assign_set_rhs_code (use_stmt
, NOP_EXPR
);
753 /* Now strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
754 ADDR_EXPR will not appear on the LHS. */
755 lhsp
= gimple_assign_lhs_ptr (use_stmt
);
756 while (handled_component_p (*lhsp
))
757 lhsp
= &TREE_OPERAND (*lhsp
, 0);
760 /* Now see if the LHS node is an INDIRECT_REF using NAME. If so,
761 propagate the ADDR_EXPR into the use of NAME and fold the result. */
762 if (TREE_CODE (lhs
) == INDIRECT_REF
763 && TREE_OPERAND (lhs
, 0) == name
764 && may_propagate_address_into_dereference (def_rhs
, lhs
)
765 && (lhsp
!= gimple_assign_lhs_ptr (use_stmt
)
766 || useless_type_conversion_p (TREE_TYPE (TREE_OPERAND (def_rhs
, 0)),
769 *lhsp
= unshare_expr (TREE_OPERAND (def_rhs
, 0));
770 fold_stmt_inplace (use_stmt
);
771 tidy_after_forward_propagate_addr (use_stmt
);
773 /* Continue propagating into the RHS if this was not the only use. */
778 /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
779 nodes from the RHS. */
780 rhsp
= gimple_assign_rhs1_ptr (use_stmt
);
781 while (handled_component_p (*rhsp
)
782 || TREE_CODE (*rhsp
) == ADDR_EXPR
)
783 rhsp
= &TREE_OPERAND (*rhsp
, 0);
786 /* Now see if the RHS node is an INDIRECT_REF using NAME. If so,
787 propagate the ADDR_EXPR into the use of NAME and fold the result. */
788 if (TREE_CODE (rhs
) == INDIRECT_REF
789 && TREE_OPERAND (rhs
, 0) == name
790 && may_propagate_address_into_dereference (def_rhs
, rhs
))
792 *rhsp
= unshare_expr (TREE_OPERAND (def_rhs
, 0));
793 fold_stmt_inplace (use_stmt
);
794 tidy_after_forward_propagate_addr (use_stmt
);
798 /* Now see if the RHS node is an INDIRECT_REF using NAME. If so,
799 propagate the ADDR_EXPR into the use of NAME and try to
800 create a VCE and fold the result. */
801 if (TREE_CODE (rhs
) == INDIRECT_REF
802 && TREE_OPERAND (rhs
, 0) == name
803 && TYPE_SIZE (TREE_TYPE (rhs
))
804 && TYPE_SIZE (TREE_TYPE (TREE_OPERAND (def_rhs
, 0)))
805 /* Function decls should not be used for VCE either as it could be a
806 function descriptor that we want and not the actual function code. */
807 && TREE_CODE (TREE_OPERAND (def_rhs
, 0)) != FUNCTION_DECL
808 /* We should not convert volatile loads to non volatile loads. */
809 && !TYPE_VOLATILE (TREE_TYPE (rhs
))
810 && !TYPE_VOLATILE (TREE_TYPE (TREE_OPERAND (def_rhs
, 0)))
811 && operand_equal_p (TYPE_SIZE (TREE_TYPE (rhs
)),
812 TYPE_SIZE (TREE_TYPE (TREE_OPERAND (def_rhs
, 0))), 0))
814 tree def_rhs_base
, new_rhs
= unshare_expr (TREE_OPERAND (def_rhs
, 0));
815 new_rhs
= fold_build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (rhs
), new_rhs
);
816 if (TREE_CODE (new_rhs
) != VIEW_CONVERT_EXPR
)
818 /* If we have folded the VIEW_CONVERT_EXPR then the result is only
819 valid if we can replace the whole rhs of the use statement. */
820 if (rhs
!= gimple_assign_rhs1 (use_stmt
))
822 new_rhs
= force_gimple_operand_gsi (use_stmt_gsi
, new_rhs
, true, NULL
,
824 gimple_assign_set_rhs1 (use_stmt
, new_rhs
);
825 tidy_after_forward_propagate_addr (use_stmt
);
828 /* If the defining rhs comes from an indirect reference, then do not
829 convert into a VIEW_CONVERT_EXPR. */
830 def_rhs_base
= TREE_OPERAND (def_rhs
, 0);
831 while (handled_component_p (def_rhs_base
))
832 def_rhs_base
= TREE_OPERAND (def_rhs_base
, 0);
833 if (!INDIRECT_REF_P (def_rhs_base
))
835 /* We may have arbitrary VIEW_CONVERT_EXPRs in a nested component
836 reference. Place it there and fold the thing. */
838 fold_stmt_inplace (use_stmt
);
839 tidy_after_forward_propagate_addr (use_stmt
);
844 /* If the use of the ADDR_EXPR is not a POINTER_PLUS_EXPR, there
846 if (gimple_assign_rhs_code (use_stmt
) != POINTER_PLUS_EXPR
847 || gimple_assign_rhs1 (use_stmt
) != name
)
850 /* The remaining cases are all for turning pointer arithmetic into
851 array indexing. They only apply when we have the address of
852 element zero in an array. If that is not the case then there
854 array_ref
= TREE_OPERAND (def_rhs
, 0);
855 if (TREE_CODE (array_ref
) != ARRAY_REF
856 || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref
, 0))) != ARRAY_TYPE
857 || TREE_CODE (TREE_OPERAND (array_ref
, 1)) != INTEGER_CST
)
860 rhs2
= gimple_assign_rhs2 (use_stmt
);
861 /* Try to optimize &x[C1] p+ C2 where C2 is a multiple of the size
862 of the elements in X into &x[C1 + C2/element size]. */
863 if (TREE_CODE (rhs2
) == INTEGER_CST
)
865 tree new_rhs
= maybe_fold_stmt_addition (gimple_expr_type (use_stmt
),
869 gimple_assign_set_rhs_from_tree (use_stmt_gsi
,
870 unshare_expr (new_rhs
));
871 use_stmt
= gsi_stmt (*use_stmt_gsi
);
872 update_stmt (use_stmt
);
873 tidy_after_forward_propagate_addr (use_stmt
);
878 /* Try to optimize &x[0] p+ OFFSET where OFFSET is defined by
879 converting a multiplication of an index by the size of the
880 array elements, then the result is converted into the proper
881 type for the arithmetic. */
882 if (TREE_CODE (rhs2
) == SSA_NAME
883 && integer_zerop (TREE_OPERAND (array_ref
, 1))
884 && useless_type_conversion_p (TREE_TYPE (name
), TREE_TYPE (def_rhs
))
885 /* Avoid problems with IVopts creating PLUS_EXPRs with a
886 different type than their operands. */
887 && useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (def_rhs
)))
888 return forward_propagate_addr_into_variable_array_index (rhs2
, def_rhs
,
893 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
895 Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME.
896 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
897 node or for recovery of array indexing from pointer arithmetic.
898 Returns true, if all uses have been propagated into. */
901 forward_propagate_addr_expr (tree name
, tree rhs
)
903 int stmt_loop_depth
= gimple_bb (SSA_NAME_DEF_STMT (name
))->loop_depth
;
904 imm_use_iterator iter
;
907 bool single_use_p
= has_single_use (name
);
909 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, name
)
914 /* If the use is not in a simple assignment statement, then
915 there is nothing we can do. */
916 if (gimple_code (use_stmt
) != GIMPLE_ASSIGN
)
922 /* If the use is in a deeper loop nest, then we do not want
923 to propagate the ADDR_EXPR into the loop as that is likely
924 adding expression evaluations into the loop. */
925 if (gimple_bb (use_stmt
)->loop_depth
> stmt_loop_depth
)
932 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
933 push_stmt_changes (&use_stmt
);
934 result
= forward_propagate_addr_expr_1 (name
, rhs
, &gsi
,
936 /* If the use has moved to a different statement adjust
937 the update machinery. */
938 if (use_stmt
!= gsi_stmt (gsi
))
940 pop_stmt_changes (&use_stmt
);
941 use_stmt
= gsi_stmt (gsi
);
942 update_stmt (use_stmt
);
945 pop_stmt_changes (&use_stmt
);
949 /* Remove intermediate now unused copy and conversion chains. */
950 use_rhs
= gimple_assign_rhs1 (use_stmt
);
952 && TREE_CODE (gimple_assign_lhs (use_stmt
)) == SSA_NAME
953 && (TREE_CODE (use_rhs
) == SSA_NAME
954 || (CONVERT_EXPR_P (use_rhs
)
955 && TREE_CODE (TREE_OPERAND (use_rhs
, 0)) == SSA_NAME
)))
957 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
958 release_defs (use_stmt
);
959 gsi_remove (&gsi
, true);
966 /* Forward propagate the comparison defined in STMT like
967 cond_1 = x CMP y to uses of the form
971 Returns true if stmt is now unused. */
974 forward_propagate_comparison (gimple stmt
)
976 tree name
= gimple_assign_lhs (stmt
);
978 tree tmp
= NULL_TREE
;
980 /* Don't propagate ssa names that occur in abnormal phis. */
981 if ((TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
982 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt
)))
983 || (TREE_CODE (gimple_assign_rhs2 (stmt
)) == SSA_NAME
984 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs2 (stmt
))))
987 /* Do not un-cse comparisons. But propagate through copies. */
988 use_stmt
= get_prop_dest_stmt (name
, &name
);
992 /* Conversion of the condition result to another integral type. */
993 if (is_gimple_assign (use_stmt
)
994 && (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt
))
995 || TREE_CODE_CLASS (gimple_assign_rhs_code (use_stmt
))
997 || gimple_assign_rhs_code (use_stmt
) == TRUTH_NOT_EXPR
)
998 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (use_stmt
))))
1000 tree lhs
= gimple_assign_lhs (use_stmt
);
1002 /* We can propagate the condition into a conversion. */
1003 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt
)))
1005 /* Avoid using fold here as that may create a COND_EXPR with
1006 non-boolean condition as canonical form. */
1007 tmp
= build2 (gimple_assign_rhs_code (stmt
), TREE_TYPE (lhs
),
1008 gimple_assign_rhs1 (stmt
), gimple_assign_rhs2 (stmt
));
1010 /* We can propagate the condition into X op CST where op
1011 is EQ_EXPR or NE_EXPR and CST is either one or zero. */
1012 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (use_stmt
))
1014 && TREE_CODE (gimple_assign_rhs1 (use_stmt
)) == SSA_NAME
1015 && TREE_CODE (gimple_assign_rhs2 (use_stmt
)) == INTEGER_CST
)
1017 enum tree_code code
= gimple_assign_rhs_code (use_stmt
);
1018 tree cst
= gimple_assign_rhs2 (use_stmt
);
1021 cond
= build2 (gimple_assign_rhs_code (stmt
),
1023 gimple_assign_rhs1 (stmt
),
1024 gimple_assign_rhs2 (stmt
));
1026 tmp
= combine_cond_expr_cond (code
, TREE_TYPE (lhs
), cond
, cst
, false);
1027 if (tmp
== NULL_TREE
)
1030 /* We can propagate the condition into a statement that
1031 computes the logical negation of the comparison result. */
1032 else if (gimple_assign_rhs_code (use_stmt
) == TRUTH_NOT_EXPR
)
1034 tree type
= TREE_TYPE (gimple_assign_rhs1 (stmt
));
1035 bool nans
= HONOR_NANS (TYPE_MODE (type
));
1036 enum tree_code code
;
1037 code
= invert_tree_comparison (gimple_assign_rhs_code (stmt
), nans
);
1038 if (code
== ERROR_MARK
)
1041 tmp
= build2 (code
, TREE_TYPE (lhs
), gimple_assign_rhs1 (stmt
),
1042 gimple_assign_rhs2 (stmt
));
1048 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
1049 gimple_assign_set_rhs_from_tree (&gsi
, unshare_expr (tmp
));
1050 use_stmt
= gsi_stmt (gsi
);
1051 update_stmt (use_stmt
);
1054 /* Remove defining statements. */
1055 remove_prop_source_from_use (name
, stmt
);
1057 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1059 tree old_rhs
= rhs_to_tree (TREE_TYPE (gimple_assign_lhs (stmt
)),
1061 fprintf (dump_file
, " Replaced '");
1062 print_generic_expr (dump_file
, old_rhs
, dump_flags
);
1063 fprintf (dump_file
, "' with '");
1064 print_generic_expr (dump_file
, tmp
, dump_flags
);
1065 fprintf (dump_file
, "'\n");
1074 /* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y.
1075 If so, we can change STMT into lhs = y which can later be copy
1076 propagated. Similarly for negation.
1078 This could trivially be formulated as a forward propagation
1079 to immediate uses. However, we already had an implementation
1080 from DOM which used backward propagation via the use-def links.
1082 It turns out that backward propagation is actually faster as
1083 there's less work to do for each NOT/NEG expression we find.
1084 Backwards propagation needs to look at the statement in a single
1085 backlink. Forward propagation needs to look at potentially more
1086 than one forward link. */
1089 simplify_not_neg_expr (gimple_stmt_iterator
*gsi_p
)
1091 gimple stmt
= gsi_stmt (*gsi_p
);
1092 tree rhs
= gimple_assign_rhs1 (stmt
);
1093 gimple rhs_def_stmt
= SSA_NAME_DEF_STMT (rhs
);
1095 /* See if the RHS_DEF_STMT has the same form as our statement. */
1096 if (is_gimple_assign (rhs_def_stmt
)
1097 && gimple_assign_rhs_code (rhs_def_stmt
) == gimple_assign_rhs_code (stmt
))
1099 tree rhs_def_operand
= gimple_assign_rhs1 (rhs_def_stmt
);
1101 /* Verify that RHS_DEF_OPERAND is a suitable SSA_NAME. */
1102 if (TREE_CODE (rhs_def_operand
) == SSA_NAME
1103 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand
))
1105 gimple_assign_set_rhs_from_tree (gsi_p
, rhs_def_operand
);
1106 stmt
= gsi_stmt (*gsi_p
);
1112 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
1113 the condition which we may be able to optimize better. */
1116 simplify_gimple_switch (gimple stmt
)
1118 tree cond
= gimple_switch_index (stmt
);
1122 /* The optimization that we really care about is removing unnecessary
1123 casts. That will let us do much better in propagating the inferred
1124 constant at the switch target. */
1125 if (TREE_CODE (cond
) == SSA_NAME
)
1127 def_stmt
= SSA_NAME_DEF_STMT (cond
);
1128 if (is_gimple_assign (def_stmt
))
1130 if (gimple_assign_rhs_code (def_stmt
) == NOP_EXPR
)
1135 def
= gimple_assign_rhs1 (def_stmt
);
1137 #ifdef ENABLE_CHECKING
1138 /* ??? Why was Jeff testing this? We are gimple... */
1139 gcc_assert (is_gimple_val (def
));
1142 to
= TREE_TYPE (cond
);
1143 ti
= TREE_TYPE (def
);
1145 /* If we have an extension that preserves value, then we
1146 can copy the source value into the switch. */
1148 need_precision
= TYPE_PRECISION (ti
);
1150 if (! INTEGRAL_TYPE_P (ti
))
1152 else if (TYPE_UNSIGNED (to
) && !TYPE_UNSIGNED (ti
))
1154 else if (!TYPE_UNSIGNED (to
) && TYPE_UNSIGNED (ti
))
1155 need_precision
+= 1;
1156 if (TYPE_PRECISION (to
) < need_precision
)
1161 gimple_switch_set_index (stmt
, def
);
1169 /* Run bitwise and assignments throug the folder. If the first argument is an
1170 ssa name that is itself a result of a typecast of an ADDR_EXPR to an
1171 integer, feed the ADDR_EXPR to the folder rather than the ssa name.
1175 simplify_bitwise_and (gimple_stmt_iterator
*gsi
, gimple stmt
)
1178 tree arg1
= gimple_assign_rhs1 (stmt
);
1179 tree arg2
= gimple_assign_rhs2 (stmt
);
1181 if (TREE_CODE (arg2
) != INTEGER_CST
)
1184 if (TREE_CODE (arg1
) == SSA_NAME
&& !SSA_NAME_IS_DEFAULT_DEF (arg1
))
1186 gimple def
= SSA_NAME_DEF_STMT (arg1
);
1188 if (gimple_assign_cast_p (def
)
1189 && INTEGRAL_TYPE_P (gimple_expr_type (def
)))
1191 tree op
= gimple_assign_rhs1 (def
);
1193 if (TREE_CODE (op
) == ADDR_EXPR
)
1198 res
= fold_binary (BIT_AND_EXPR
, TREE_TYPE (gimple_assign_lhs (stmt
)),
1200 if (res
&& is_gimple_min_invariant (res
))
1202 gimple_assign_set_rhs_from_tree (gsi
, res
);
1208 /* Main entry point for the forward propagation optimizer. */
1211 tree_ssa_forward_propagate_single_use_vars (void)
1214 unsigned int todoflags
= 0;
1216 cfg_changed
= false;
1220 gimple_stmt_iterator gsi
;
1222 /* Note we update GSI within the loop as necessary. */
1223 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
1225 gimple stmt
= gsi_stmt (gsi
);
1227 /* If this statement sets an SSA_NAME to an address,
1228 try to propagate the address into the uses of the SSA_NAME. */
1229 if (is_gimple_assign (stmt
))
1231 tree lhs
= gimple_assign_lhs (stmt
);
1232 tree rhs
= gimple_assign_rhs1 (stmt
);
1234 if (TREE_CODE (lhs
) != SSA_NAME
)
1240 if (gimple_assign_rhs_code (stmt
) == ADDR_EXPR
1241 /* Handle pointer conversions on invariant addresses
1242 as well, as this is valid gimple. */
1243 || (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt
))
1244 && TREE_CODE (rhs
) == ADDR_EXPR
1245 && POINTER_TYPE_P (TREE_TYPE (lhs
))))
1248 if (!stmt_references_abnormal_ssa_name (stmt
)
1249 && forward_propagate_addr_expr (lhs
, rhs
))
1251 release_defs (stmt
);
1252 todoflags
|= TODO_remove_unused_locals
;
1253 gsi_remove (&gsi
, true);
1258 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
1259 && is_gimple_min_invariant (rhs
))
1261 /* Make sure to fold &a[0] + off_1 here. */
1262 fold_stmt_inplace (stmt
);
1264 if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
1267 else if ((gimple_assign_rhs_code (stmt
) == BIT_NOT_EXPR
1268 || gimple_assign_rhs_code (stmt
) == NEGATE_EXPR
)
1269 && TREE_CODE (rhs
) == SSA_NAME
)
1271 simplify_not_neg_expr (&gsi
);
1274 else if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
1276 /* In this case the entire COND_EXPR is in rhs1. */
1278 fold_defer_overflow_warnings ();
1279 did_something
= forward_propagate_into_cond (&gsi
);
1280 stmt
= gsi_stmt (gsi
);
1281 if (did_something
== 2)
1283 fold_undefer_overflow_warnings (!TREE_NO_WARNING (rhs
)
1284 && did_something
, stmt
, WARN_STRICT_OVERFLOW_CONDITIONAL
);
1287 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt
))
1290 if (forward_propagate_comparison (stmt
))
1292 release_defs (stmt
);
1293 todoflags
|= TODO_remove_unused_locals
;
1294 gsi_remove (&gsi
, true);
1299 else if (gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
)
1301 simplify_bitwise_and (&gsi
, stmt
);
1307 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
1309 simplify_gimple_switch (stmt
);
1312 else if (gimple_code (stmt
) == GIMPLE_COND
)
1315 fold_defer_overflow_warnings ();
1316 did_something
= forward_propagate_into_gimple_cond (stmt
);
1317 if (did_something
== 2)
1319 fold_undefer_overflow_warnings (did_something
, stmt
,
1320 WARN_STRICT_OVERFLOW_CONDITIONAL
);
1329 todoflags
|= TODO_cleanup_cfg
;
1335 gate_forwprop (void)
1340 struct gimple_opt_pass pass_forwprop
=
1344 "forwprop", /* name */
1345 gate_forwprop
, /* gate */
1346 tree_ssa_forward_propagate_single_use_vars
, /* execute */
1349 0, /* static_pass_number */
1350 TV_TREE_FORWPROP
, /* tv_id */
1351 PROP_cfg
| PROP_ssa
, /* properties_required */
1352 0, /* properties_provided */
1353 0, /* properties_destroyed */
1354 0, /* todo_flags_start */
1358 | TODO_verify_ssa
/* todo_flags_finish */