1 /* Forward propagation of expressions for single use variables.
2 Copyright (C) 2004, 2005 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 2, 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 COPYING. If not, write to
18 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
19 Boston, MA 02110-1301, USA. */
23 #include "coretypes.h"
29 #include "basic-block.h"
31 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-pass.h"
34 #include "tree-dump.h"
35 #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 Note carefully that after propagation the resulting statement
44 must still be a proper gimple statement. Right now we simply
45 only perform propagations we know will result in valid gimple
46 code. One day we'll want to generalize this code.
48 One class of common cases we handle is forward propagating a single use
49 variable into a COND_EXPR.
53 if (x) goto ... else goto ...
55 Will be transformed into:
58 if (a COND b) goto ... else goto ...
60 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
62 Or (assuming c1 and c2 are constants):
66 if (x EQ/NEQ c2) goto ... else goto ...
68 Will be transformed into:
71 if (a EQ/NEQ (c2 - c1)) goto ... else goto ...
73 Similarly for x = a - c1.
79 if (x) goto ... else goto ...
81 Will be transformed into:
84 if (a == 0) goto ... else goto ...
86 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
87 For these cases, we propagate A into all, possibly more than one,
88 COND_EXPRs that use X.
94 if (x) goto ... else goto ...
96 Will be transformed into:
99 if (a != 0) goto ... else goto ...
101 (Assuming a is an integral type and x is a boolean or x is an
102 integral and a is a boolean.)
104 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
105 For these cases, we propagate A into all, possibly more than one,
106 COND_EXPRs that use X.
108 In addition to eliminating the variable and the statement which assigns
109 a value to the variable, we may be able to later thread the jump without
110 adding insane complexity in the dominator optimizer.
112 Also note these transformations can cascade. We handle this by having
113 a worklist of COND_EXPR statements to examine. As we make a change to
114 a statement, we put it back on the worklist to examine on the next
115 iteration of the main loop.
117 A second class of propagation opportunities arises for ADDR_EXPR
130 ptr2 = ptr + <constant>;
134 ptr2 = &x[constant/elementsize];
139 offset = index * element_size;
140 offset_p = (pointer) offset;
141 ptr2 = ptr + offset_p
143 Will get turned into:
147 We also propagate casts into SWITCH_EXPR and COND_EXPR conditions to
148 allow us to remove the cast and {NOT_EXPR,NEG_EXPR} into a subsequent
151 This will (of course) be extended as other needs arise. */
153 static bool forward_propagate_addr_expr (tree name
, tree rhs
);
155 /* Set to true if we delete EH edges during the optimization. */
156 static bool cfg_changed
;
159 /* Get the next statement we can propagate NAME's value into skipping
160 trivial copies. Returns the statement that is suitable as a
161 propagation destination or NULL_TREE if there is no such one.
162 This only returns destinations in a single-use chain. FINAL_NAME_P
163 if non-NULL is written to the ssa name that represents the use. */
166 get_prop_dest_stmt (tree name
, tree
*final_name_p
)
172 /* If name has multiple uses, bail out. */
173 if (!single_imm_use (name
, &use
, &use_stmt
))
176 /* If this is not a trivial copy, we found it. */
177 if (TREE_CODE (use_stmt
) != GIMPLE_MODIFY_STMT
178 || TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt
, 0)) != SSA_NAME
179 || GIMPLE_STMT_OPERAND (use_stmt
, 1) != name
)
182 /* Continue searching uses of the copy destination. */
183 name
= GIMPLE_STMT_OPERAND (use_stmt
, 0);
187 *final_name_p
= name
;
192 /* Get the statement we can propagate from into NAME skipping
193 trivial copies. Returns the statement which defines the
194 propagation source or NULL_TREE if there is no such one.
195 If SINGLE_USE_ONLY is set considers only sources which have
196 a single use chain up to NAME. If SINGLE_USE_P is non-null,
197 it is set to whether the chain to NAME is a single use chain
198 or not. SINGLE_USE_P is not written to if SINGLE_USE_ONLY is set. */
201 get_prop_source_stmt (tree name
, bool single_use_only
, bool *single_use_p
)
203 bool single_use
= true;
206 tree def_stmt
= SSA_NAME_DEF_STMT (name
);
208 if (!has_single_use (name
))
215 /* If name is defined by a PHI node or is the default def, bail out. */
216 if (TREE_CODE (def_stmt
) != GIMPLE_MODIFY_STMT
)
219 /* If name is not a simple copy destination, we found it. */
220 if (TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt
, 1)) != SSA_NAME
)
222 if (!single_use_only
&& single_use_p
)
223 *single_use_p
= single_use
;
228 /* Continue searching the def of the copy source name. */
229 name
= GIMPLE_STMT_OPERAND (def_stmt
, 1);
233 /* Checks if the destination ssa name in DEF_STMT can be used as
234 propagation source. Returns true if so, otherwise false. */
237 can_propagate_from (tree def_stmt
)
239 tree rhs
= GIMPLE_STMT_OPERAND (def_stmt
, 1);
241 /* We cannot propagate ssa names that occur in abnormal phi nodes. */
242 switch (TREE_CODE_LENGTH (TREE_CODE (rhs
)))
245 if (TREE_OPERAND (rhs
, 2) != NULL_TREE
246 && TREE_CODE (TREE_OPERAND (rhs
, 2)) == SSA_NAME
247 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (rhs
, 2)))
250 if (TREE_OPERAND (rhs
, 1) != NULL_TREE
251 && TREE_CODE (TREE_OPERAND (rhs
, 1)) == SSA_NAME
252 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (rhs
, 1)))
255 if (TREE_OPERAND (rhs
, 0) != NULL_TREE
256 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
257 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (rhs
, 0)))
265 /* If the definition is a conversion of a pointer to a function type,
266 then we can not apply optimizations as some targets require function
267 pointers to be canonicalized and in this case this optimization could
268 eliminate a necessary canonicalization. */
269 if ((TREE_CODE (rhs
) == NOP_EXPR
270 || TREE_CODE (rhs
) == CONVERT_EXPR
)
271 && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs
, 0)))
272 && TREE_CODE (TREE_TYPE (TREE_TYPE
273 (TREE_OPERAND (rhs
, 0)))) == FUNCTION_TYPE
)
279 /* Remove a copy chain ending in NAME along the defs but not
280 further or including UP_TO_STMT. If NAME was replaced in
281 its only use then this function can be used to clean up
282 dead stmts. Returns true if UP_TO_STMT can be removed
283 as well, otherwise false. */
286 remove_prop_source_from_use (tree name
, tree up_to_stmt
)
288 block_stmt_iterator bsi
;
292 if (!has_zero_uses (name
))
295 stmt
= SSA_NAME_DEF_STMT (name
);
296 if (stmt
== up_to_stmt
)
299 bsi
= bsi_for_stmt (stmt
);
301 bsi_remove (&bsi
, true);
303 name
= GIMPLE_STMT_OPERAND (stmt
, 1);
304 } while (TREE_CODE (name
) == SSA_NAME
);
309 /* Combine OP0 CODE OP1 in the context of a COND_EXPR. Returns
310 the folded result in a form suitable for COND_EXPR_COND or
311 NULL_TREE, if there is no suitable simplified form. If
312 INVARIANT_ONLY is true only gimple_min_invariant results are
313 considered simplified. */
316 combine_cond_expr_cond (enum tree_code code
, tree type
,
317 tree op0
, tree op1
, bool invariant_only
)
321 gcc_assert (TREE_CODE_CLASS (code
) == tcc_comparison
);
323 t
= fold_binary (code
, type
, op0
, op1
);
327 /* Require that we got a boolean type out if we put one in. */
328 gcc_assert (TREE_CODE (TREE_TYPE (t
)) == TREE_CODE (type
));
330 /* For (bool)x use x != 0. */
331 if (TREE_CODE (t
) == NOP_EXPR
332 && TREE_TYPE (t
) == boolean_type_node
)
334 tree top0
= TREE_OPERAND (t
, 0);
335 t
= build2 (NE_EXPR
, type
,
336 top0
, build_int_cst (TREE_TYPE (top0
), 0));
338 /* For !x use x == 0. */
339 else if (TREE_CODE (t
) == TRUTH_NOT_EXPR
)
341 tree top0
= TREE_OPERAND (t
, 0);
342 t
= build2 (EQ_EXPR
, type
,
343 top0
, build_int_cst (TREE_TYPE (top0
), 0));
345 /* For cmp ? 1 : 0 use cmp. */
346 else if (TREE_CODE (t
) == COND_EXPR
347 && COMPARISON_CLASS_P (TREE_OPERAND (t
, 0))
348 && integer_onep (TREE_OPERAND (t
, 1))
349 && integer_zerop (TREE_OPERAND (t
, 2)))
351 tree top0
= TREE_OPERAND (t
, 0);
352 t
= build2 (TREE_CODE (top0
), type
,
353 TREE_OPERAND (top0
, 0), TREE_OPERAND (top0
, 1));
356 /* Bail out if we required an invariant but didn't get one. */
358 && !is_gimple_min_invariant (t
))
361 /* A valid conditional for a COND_EXPR is either a gimple value
362 or a comparison with two gimple value operands. */
363 if (is_gimple_val (t
)
364 || (COMPARISON_CLASS_P (t
)
365 && is_gimple_val (TREE_OPERAND (t
, 0))
366 && is_gimple_val (TREE_OPERAND (t
, 1))))
372 /* Propagate from the ssa name definition statements of COND_EXPR
373 in statement STMT into the conditional if that simplifies it. */
376 forward_propagate_into_cond (tree cond_expr
, tree stmt
)
378 bool did_something
= false;
381 tree tmp
= NULL_TREE
;
382 tree cond
= COND_EXPR_COND (cond_expr
);
383 tree name
, def_stmt
, rhs
;
386 /* We can do tree combining on SSA_NAME and comparison expressions. */
387 if (COMPARISON_CLASS_P (cond
)
388 && TREE_CODE (TREE_OPERAND (cond
, 0)) == SSA_NAME
)
390 /* For comparisons use the first operand, that is likely to
391 simplify comparisons against constants. */
392 name
= TREE_OPERAND (cond
, 0);
393 def_stmt
= get_prop_source_stmt (name
, false, &single_use_p
);
394 if (def_stmt
!= NULL_TREE
395 && can_propagate_from (def_stmt
))
397 tree op1
= TREE_OPERAND (cond
, 1);
398 rhs
= GIMPLE_STMT_OPERAND (def_stmt
, 1);
399 tmp
= combine_cond_expr_cond (TREE_CODE (cond
), boolean_type_node
,
400 fold_convert (TREE_TYPE (op1
), rhs
),
403 /* If that wasn't successful, try the second operand. */
405 && TREE_CODE (TREE_OPERAND (cond
, 1)) == SSA_NAME
)
407 tree op0
= TREE_OPERAND (cond
, 0);
408 name
= TREE_OPERAND (cond
, 1);
409 def_stmt
= get_prop_source_stmt (name
, false, &single_use_p
);
410 if (def_stmt
== NULL_TREE
411 || !can_propagate_from (def_stmt
))
412 return did_something
;
414 rhs
= GIMPLE_STMT_OPERAND (def_stmt
, 1);
415 tmp
= combine_cond_expr_cond (TREE_CODE (cond
), boolean_type_node
,
417 fold_convert (TREE_TYPE (op0
), rhs
),
421 else if (TREE_CODE (cond
) == SSA_NAME
)
424 def_stmt
= get_prop_source_stmt (name
, true, NULL
);
425 if (def_stmt
== NULL_TREE
426 || !can_propagate_from (def_stmt
))
427 return did_something
;
429 rhs
= GIMPLE_STMT_OPERAND (def_stmt
, 1);
430 tmp
= combine_cond_expr_cond (NE_EXPR
, boolean_type_node
, rhs
,
431 build_int_cst (TREE_TYPE (rhs
), 0),
437 if (dump_file
&& tmp
)
439 fprintf (dump_file
, " Replaced '");
440 print_generic_expr (dump_file
, cond
, 0);
441 fprintf (dump_file
, "' with '");
442 print_generic_expr (dump_file
, tmp
, 0);
443 fprintf (dump_file
, "'\n");
446 COND_EXPR_COND (cond_expr
) = unshare_expr (tmp
);
449 /* Remove defining statements. */
450 remove_prop_source_from_use (name
, NULL
);
452 did_something
= true;
454 /* Continue combining. */
461 return did_something
;
464 /* We've just substituted an ADDR_EXPR into stmt. Update all the
465 relevant data structures to match. */
468 tidy_after_forward_propagate_addr (tree stmt
)
470 /* We may have turned a trapping insn into a non-trapping insn. */
471 if (maybe_clean_or_replace_eh_stmt (stmt
, stmt
)
472 && tree_purge_dead_eh_edges (bb_for_stmt (stmt
)))
475 if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1)) == ADDR_EXPR
)
476 recompute_tree_invariant_for_addr_expr (GIMPLE_STMT_OPERAND (stmt
, 1));
478 mark_symbols_for_renaming (stmt
);
481 /* DEF_RHS contains the address of the 0th element in an array.
482 USE_STMT uses type of DEF_RHS to compute the address of an
483 arbitrary element within the array. The (variable) byte offset
484 of the element is contained in OFFSET.
486 We walk back through the use-def chains of OFFSET to verify that
487 it is indeed computing the offset of an element within the array
488 and extract the index corresponding to the given byte offset.
490 We then try to fold the entire address expression into a form
493 If we are successful, we replace the right hand side of USE_STMT
494 with the new address computation. */
497 forward_propagate_addr_into_variable_array_index (tree offset
,
498 tree def_rhs
, tree use_stmt
)
502 /* The offset must be defined by a simple GIMPLE_MODIFY_STMT statement. */
503 if (TREE_CODE (offset
) != GIMPLE_MODIFY_STMT
)
506 /* The RHS of the statement which defines OFFSET must be a gimple
507 cast of another SSA_NAME. */
508 offset
= GIMPLE_STMT_OPERAND (offset
, 1);
509 if (!is_gimple_cast (offset
))
512 offset
= TREE_OPERAND (offset
, 0);
513 if (TREE_CODE (offset
) != SSA_NAME
)
516 /* Try to find an expression for a proper index. This is either
517 a multiplication expression by the element size or just the
518 ssa name we came along in case the element size is one. */
519 if (integer_onep (TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (def_rhs
)))))
523 offset
= SSA_NAME_DEF_STMT (offset
);
525 /* The RHS of the statement which defines OFFSET must be a
526 multiplication of an object by the size of the array elements. */
527 if (TREE_CODE (offset
) != GIMPLE_MODIFY_STMT
)
530 offset
= GIMPLE_STMT_OPERAND (offset
, 1);
531 if (TREE_CODE (offset
) != MULT_EXPR
532 || TREE_CODE (TREE_OPERAND (offset
, 1)) != INTEGER_CST
533 || !simple_cst_equal (TREE_OPERAND (offset
, 1),
534 TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (def_rhs
)))))
537 /* The first operand to the MULT_EXPR is the desired index. */
538 index
= TREE_OPERAND (offset
, 0);
541 /* Replace the pointer addition with array indexing. */
542 GIMPLE_STMT_OPERAND (use_stmt
, 1) = unshare_expr (def_rhs
);
543 TREE_OPERAND (TREE_OPERAND (GIMPLE_STMT_OPERAND (use_stmt
, 1), 0), 1)
546 /* That should have created gimple, so there is no need to
547 record information to undo the propagation. */
548 fold_stmt_inplace (use_stmt
);
549 tidy_after_forward_propagate_addr (use_stmt
);
553 /* NAME is a SSA_NAME representing DEF_RHS which is of the form
554 ADDR_EXPR <whatever>.
556 Try to forward propagate the ADDR_EXPR into the use USE_STMT.
557 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
558 node or for recovery of array indexing from pointer arithmetic.
560 Return true if the propagation was successful (the propagation can
561 be not totally successful, yet things may have been changed). */
564 forward_propagate_addr_expr_1 (tree name
, tree def_rhs
, tree use_stmt
,
567 tree lhs
, rhs
, array_ref
;
569 /* Strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
570 ADDR_EXPR will not appear on the LHS. */
571 lhs
= GIMPLE_STMT_OPERAND (use_stmt
, 0);
572 while (handled_component_p (lhs
))
573 lhs
= TREE_OPERAND (lhs
, 0);
575 rhs
= GIMPLE_STMT_OPERAND (use_stmt
, 1);
577 /* Now see if the LHS node is an INDIRECT_REF using NAME. If so,
578 propagate the ADDR_EXPR into the use of NAME and fold the result. */
579 if (TREE_CODE (lhs
) == INDIRECT_REF
&& TREE_OPERAND (lhs
, 0) == name
)
581 /* This should always succeed in creating gimple, so there is
582 no need to save enough state to undo this propagation. */
583 TREE_OPERAND (lhs
, 0) = unshare_expr (def_rhs
);
584 fold_stmt_inplace (use_stmt
);
585 tidy_after_forward_propagate_addr (use_stmt
);
587 /* Continue propagating into the RHS. */
590 /* Trivial cases. The use statement could be a trivial copy or a
591 useless conversion. Recurse to the uses of the lhs as copyprop does
592 not copy through differen variant pointers and FRE does not catch
593 all useless conversions. Treat the case of a single-use name and
594 a conversion to def_rhs type separate, though. */
595 else if (TREE_CODE (lhs
) == SSA_NAME
596 && (TREE_CODE (rhs
) == NOP_EXPR
597 || TREE_CODE (rhs
) == CONVERT_EXPR
)
598 && TREE_TYPE (rhs
) == TREE_TYPE (def_rhs
)
601 GIMPLE_STMT_OPERAND (use_stmt
, 1) = unshare_expr (def_rhs
);
604 else if ((TREE_CODE (lhs
) == SSA_NAME
606 || ((TREE_CODE (rhs
) == NOP_EXPR
607 || TREE_CODE (rhs
) == CONVERT_EXPR
)
608 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (rhs
),
609 TREE_TYPE (def_rhs
))))
610 return forward_propagate_addr_expr (lhs
, def_rhs
);
612 /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
613 nodes from the RHS. */
614 while (handled_component_p (rhs
)
615 || TREE_CODE (rhs
) == ADDR_EXPR
)
616 rhs
= TREE_OPERAND (rhs
, 0);
618 /* Now see if the RHS node is an INDIRECT_REF using NAME. If so,
619 propagate the ADDR_EXPR into the use of NAME and fold the result. */
620 if (TREE_CODE (rhs
) == INDIRECT_REF
&& TREE_OPERAND (rhs
, 0) == name
)
622 /* This should always succeed in creating gimple, so there is
623 no need to save enough state to undo this propagation. */
624 TREE_OPERAND (rhs
, 0) = unshare_expr (def_rhs
);
625 fold_stmt_inplace (use_stmt
);
626 tidy_after_forward_propagate_addr (use_stmt
);
630 /* The remaining cases are all for turning pointer arithmetic into
631 array indexing. They only apply when we have the address of
632 element zero in an array. If that is not the case then there
634 array_ref
= TREE_OPERAND (def_rhs
, 0);
635 if (TREE_CODE (array_ref
) != ARRAY_REF
636 || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref
, 0))) != ARRAY_TYPE
637 || !integer_zerop (TREE_OPERAND (array_ref
, 1)))
640 /* If the use of the ADDR_EXPR must be a PLUS_EXPR, or else there
642 if (TREE_CODE (rhs
) != PLUS_EXPR
)
645 /* Try to optimize &x[0] + C where C is a multiple of the size
646 of the elements in X into &x[C/element size]. */
647 if (TREE_OPERAND (rhs
, 0) == name
648 && TREE_CODE (TREE_OPERAND (rhs
, 1)) == INTEGER_CST
)
650 tree orig
= unshare_expr (rhs
);
651 TREE_OPERAND (rhs
, 0) = unshare_expr (def_rhs
);
653 /* If folding succeeds, then we have just exposed new variables
654 in USE_STMT which will need to be renamed. If folding fails,
655 then we need to put everything back the way it was. */
656 if (fold_stmt_inplace (use_stmt
))
658 tidy_after_forward_propagate_addr (use_stmt
);
663 GIMPLE_STMT_OPERAND (use_stmt
, 1) = orig
;
664 update_stmt (use_stmt
);
669 /* Try to optimize &x[0] + OFFSET where OFFSET is defined by
670 converting a multiplication of an index by the size of the
671 array elements, then the result is converted into the proper
672 type for the arithmetic. */
673 if (TREE_OPERAND (rhs
, 0) == name
674 && TREE_CODE (TREE_OPERAND (rhs
, 1)) == SSA_NAME
675 /* Avoid problems with IVopts creating PLUS_EXPRs with a
676 different type than their operands. */
677 && lang_hooks
.types_compatible_p (TREE_TYPE (name
), TREE_TYPE (rhs
)))
680 tree offset_stmt
= SSA_NAME_DEF_STMT (TREE_OPERAND (rhs
, 1));
682 res
= forward_propagate_addr_into_variable_array_index (offset_stmt
,
687 /* Same as the previous case, except the operands of the PLUS_EXPR
689 if (TREE_OPERAND (rhs
, 1) == name
690 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
691 /* Avoid problems with IVopts creating PLUS_EXPRs with a
692 different type than their operands. */
693 && lang_hooks
.types_compatible_p (TREE_TYPE (name
), TREE_TYPE (rhs
)))
696 tree offset_stmt
= SSA_NAME_DEF_STMT (TREE_OPERAND (rhs
, 0));
697 res
= forward_propagate_addr_into_variable_array_index (offset_stmt
,
704 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
706 Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME.
707 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
708 node or for recovery of array indexing from pointer arithmetic.
709 Returns true, if all uses have been propagated into. */
712 forward_propagate_addr_expr (tree name
, tree rhs
)
714 int stmt_loop_depth
= bb_for_stmt (SSA_NAME_DEF_STMT (name
))->loop_depth
;
715 imm_use_iterator iter
;
718 bool single_use_p
= has_single_use (name
);
720 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, name
)
724 /* If the use is not in a simple assignment statement, then
725 there is nothing we can do. */
726 if (TREE_CODE (use_stmt
) != GIMPLE_MODIFY_STMT
)
732 /* If the use is in a deeper loop nest, then we do not want
733 to propagate the ADDR_EXPR into the loop as that is likely
734 adding expression evaluations into the loop. */
735 if (bb_for_stmt (use_stmt
)->loop_depth
> stmt_loop_depth
)
741 /* If the use_stmt has side-effects, don't propagate into it. */
742 if (stmt_ann (use_stmt
)->has_volatile_ops
)
748 push_stmt_changes (&use_stmt
);
750 result
= forward_propagate_addr_expr_1 (name
, rhs
, use_stmt
,
754 pop_stmt_changes (&use_stmt
);
756 /* Remove intermediate now unused copy and conversion chains. */
758 && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt
, 0)) == SSA_NAME
759 && (TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt
, 1)) == SSA_NAME
760 || TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt
, 1)) == NOP_EXPR
761 || TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt
, 1)) == CONVERT_EXPR
))
763 block_stmt_iterator bsi
= bsi_for_stmt (use_stmt
);
764 release_defs (use_stmt
);
765 bsi_remove (&bsi
, true);
772 /* Forward propagate the comparison COND defined in STMT like
773 cond_1 = x CMP y to uses of the form
777 Returns true if stmt is now unused. */
780 forward_propagate_comparison (tree cond
, tree stmt
)
782 tree name
= GIMPLE_STMT_OPERAND (stmt
, 0);
783 tree use_stmt
, tmp
= NULL_TREE
;
785 /* Don't propagate ssa names that occur in abnormal phis. */
786 if ((TREE_CODE (TREE_OPERAND (cond
, 0)) == SSA_NAME
787 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (cond
, 0)))
788 || (TREE_CODE (TREE_OPERAND (cond
, 1)) == SSA_NAME
789 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (cond
, 1))))
792 /* Do not un-cse comparisons. But propagate through copies. */
793 use_stmt
= get_prop_dest_stmt (name
, &name
);
794 if (use_stmt
== NULL_TREE
)
797 /* Conversion of the condition result to another integral type. */
798 if (TREE_CODE (use_stmt
) == GIMPLE_MODIFY_STMT
799 && (TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt
, 1)) == CONVERT_EXPR
800 || TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt
, 1)) == NOP_EXPR
801 || COMPARISON_CLASS_P (GIMPLE_STMT_OPERAND (use_stmt
, 1))
802 || TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt
, 1)) == TRUTH_NOT_EXPR
)
803 && INTEGRAL_TYPE_P (TREE_TYPE (GIMPLE_STMT_OPERAND (use_stmt
, 0))))
805 tree lhs
= GIMPLE_STMT_OPERAND (use_stmt
, 0);
806 tree rhs
= GIMPLE_STMT_OPERAND (use_stmt
, 1);
808 /* We can propagate the condition into a conversion. */
809 if (TREE_CODE (rhs
) == CONVERT_EXPR
810 || TREE_CODE (rhs
) == NOP_EXPR
)
812 /* Avoid using fold here as that may create a COND_EXPR with
813 non-boolean condition as canonical form. */
814 tmp
= build2 (TREE_CODE (cond
), TREE_TYPE (lhs
),
815 TREE_OPERAND (cond
, 0), TREE_OPERAND (cond
, 1));
817 /* We can propagate the condition into X op CST where op
818 is EQ_EXRP or NE_EXPR and CST is either one or zero. */
819 else if (COMPARISON_CLASS_P (rhs
)
820 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
821 && TREE_CODE (TREE_OPERAND (rhs
, 1)) == INTEGER_CST
)
823 enum tree_code code
= TREE_CODE (rhs
);
824 tree cst
= TREE_OPERAND (rhs
, 1);
826 tmp
= combine_cond_expr_cond (code
, TREE_TYPE (lhs
),
827 fold_convert (TREE_TYPE (cst
), cond
),
829 if (tmp
== NULL_TREE
)
832 /* We can propagate the condition into a statement that
833 computes the logical negation of the comparison result. */
834 else if (TREE_CODE (rhs
) == TRUTH_NOT_EXPR
)
836 tree type
= TREE_TYPE (TREE_OPERAND (cond
, 0));
837 bool nans
= HONOR_NANS (TYPE_MODE (type
));
839 code
= invert_tree_comparison (TREE_CODE (cond
), nans
);
840 if (code
== ERROR_MARK
)
843 tmp
= build2 (code
, TREE_TYPE (lhs
), TREE_OPERAND (cond
, 0),
844 TREE_OPERAND (cond
, 1));
849 GIMPLE_STMT_OPERAND (use_stmt
, 1) = unshare_expr (tmp
);
850 update_stmt (use_stmt
);
852 /* Remove defining statements. */
853 remove_prop_source_from_use (name
, stmt
);
855 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
857 fprintf (dump_file
, " Replaced '");
858 print_generic_expr (dump_file
, rhs
, dump_flags
);
859 fprintf (dump_file
, "' with '");
860 print_generic_expr (dump_file
, tmp
, dump_flags
);
861 fprintf (dump_file
, "'\n");
870 /* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y.
871 If so, we can change STMT into lhs = y which can later be copy
872 propagated. Similarly for negation.
874 This could trivially be formulated as a forward propagation
875 to immediate uses. However, we already had an implementation
876 from DOM which used backward propagation via the use-def links.
878 It turns out that backward propagation is actually faster as
879 there's less work to do for each NOT/NEG expression we find.
880 Backwards propagation needs to look at the statement in a single
881 backlink. Forward propagation needs to look at potentially more
882 than one forward link. */
885 simplify_not_neg_expr (tree stmt
)
887 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
888 tree rhs_def_stmt
= SSA_NAME_DEF_STMT (TREE_OPERAND (rhs
, 0));
890 /* See if the RHS_DEF_STMT has the same form as our statement. */
891 if (TREE_CODE (rhs_def_stmt
) == GIMPLE_MODIFY_STMT
892 && TREE_CODE (GIMPLE_STMT_OPERAND (rhs_def_stmt
, 1)) == TREE_CODE (rhs
))
894 tree rhs_def_operand
=
895 TREE_OPERAND (GIMPLE_STMT_OPERAND (rhs_def_stmt
, 1), 0);
897 /* Verify that RHS_DEF_OPERAND is a suitable SSA_NAME. */
898 if (TREE_CODE (rhs_def_operand
) == SSA_NAME
899 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand
))
901 GIMPLE_STMT_OPERAND (stmt
, 1) = rhs_def_operand
;
907 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
908 the condition which we may be able to optimize better. */
911 simplify_switch_expr (tree stmt
)
913 tree cond
= SWITCH_COND (stmt
);
916 /* The optimization that we really care about is removing unnecessary
917 casts. That will let us do much better in propagating the inferred
918 constant at the switch target. */
919 if (TREE_CODE (cond
) == SSA_NAME
)
921 def
= SSA_NAME_DEF_STMT (cond
);
922 if (TREE_CODE (def
) == GIMPLE_MODIFY_STMT
)
924 def
= GIMPLE_STMT_OPERAND (def
, 1);
925 if (TREE_CODE (def
) == NOP_EXPR
)
930 def
= TREE_OPERAND (def
, 0);
932 #ifdef ENABLE_CHECKING
933 /* ??? Why was Jeff testing this? We are gimple... */
934 gcc_assert (is_gimple_val (def
));
937 to
= TREE_TYPE (cond
);
938 ti
= TREE_TYPE (def
);
940 /* If we have an extension that preserves value, then we
941 can copy the source value into the switch. */
943 need_precision
= TYPE_PRECISION (ti
);
945 if (! INTEGRAL_TYPE_P (ti
))
947 else if (TYPE_UNSIGNED (to
) && !TYPE_UNSIGNED (ti
))
949 else if (!TYPE_UNSIGNED (to
) && TYPE_UNSIGNED (ti
))
951 if (TYPE_PRECISION (to
) < need_precision
)
956 SWITCH_COND (stmt
) = def
;
964 /* Main entry point for the forward propagation optimizer. */
967 tree_ssa_forward_propagate_single_use_vars (void)
970 unsigned int todoflags
= 0;
976 block_stmt_iterator bsi
;
978 /* Note we update BSI within the loop as necessary. */
979 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); )
981 tree stmt
= bsi_stmt (bsi
);
983 /* If this statement sets an SSA_NAME to an address,
984 try to propagate the address into the uses of the SSA_NAME. */
985 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
987 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
988 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
991 if (TREE_CODE (lhs
) != SSA_NAME
)
997 if (TREE_CODE (rhs
) == ADDR_EXPR
)
999 if (forward_propagate_addr_expr (lhs
, rhs
))
1001 release_defs (stmt
);
1002 todoflags
|= TODO_remove_unused_locals
;
1003 bsi_remove (&bsi
, true);
1008 else if ((TREE_CODE (rhs
) == BIT_NOT_EXPR
1009 || TREE_CODE (rhs
) == NEGATE_EXPR
)
1010 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
)
1012 simplify_not_neg_expr (stmt
);
1015 else if (TREE_CODE (rhs
) == COND_EXPR
)
1018 fold_defer_overflow_warnings ();
1019 did_something
= forward_propagate_into_cond (rhs
, stmt
);
1020 fold_undefer_overflow_warnings (!TREE_NO_WARNING (rhs
)
1021 && did_something
, stmt
, WARN_STRICT_OVERFLOW_CONDITIONAL
);
1024 else if (COMPARISON_CLASS_P (rhs
))
1026 if (forward_propagate_comparison (rhs
, stmt
))
1028 release_defs (stmt
);
1029 todoflags
|= TODO_remove_unused_locals
;
1030 bsi_remove (&bsi
, true);
1038 else if (TREE_CODE (stmt
) == SWITCH_EXPR
)
1040 simplify_switch_expr (stmt
);
1043 else if (TREE_CODE (stmt
) == COND_EXPR
)
1046 fold_defer_overflow_warnings ();
1047 did_something
= forward_propagate_into_cond (stmt
, stmt
);
1048 fold_undefer_overflow_warnings (!TREE_NO_WARNING (stmt
)
1049 && did_something
, stmt
,
1050 WARN_STRICT_OVERFLOW_CONDITIONAL
);
1059 todoflags
|= TODO_cleanup_cfg
;
1065 gate_forwprop (void)
1070 struct tree_opt_pass pass_forwprop
= {
1071 "forwprop", /* name */
1072 gate_forwprop
, /* gate */
1073 tree_ssa_forward_propagate_single_use_vars
, /* execute */
1076 0, /* static_pass_number */
1077 TV_TREE_FORWPROP
, /* tv_id */
1078 PROP_cfg
| PROP_ssa
, /* properties_required */
1079 0, /* properties_provided */
1080 0, /* properties_destroyed */
1081 0, /* todo_flags_start */
1085 | TODO_verify_ssa
, /* todo_flags_finish */
1090 /* Structure to keep track of the value of a dereferenced PHI result
1091 and the set of virtual operands used for that dereference. */
1099 /* Verify if the value recorded for NAME in PHIVN is still valid at
1100 the start of basic block BB. */
1103 phivn_valid_p (struct phiprop_d
*phivn
, tree name
, basic_block bb
)
1105 tree vop_stmt
= phivn
[SSA_NAME_VERSION (name
)].vop_stmt
;
1109 /* The def stmts of all virtual uses need to be post-dominated
1111 FOR_EACH_SSA_TREE_OPERAND (vuse
, vop_stmt
, ui
, SSA_OP_VUSE
)
1114 imm_use_iterator ui2
;
1117 FOR_EACH_IMM_USE_STMT (use_stmt
, ui2
, vuse
)
1119 /* If BB does not dominate a VDEF, the value is invalid. */
1120 if (((TREE_CODE (use_stmt
) == GIMPLE_MODIFY_STMT
1121 && !ZERO_SSA_OPERANDS (use_stmt
, SSA_OP_VDEF
))
1122 || TREE_CODE (use_stmt
) == PHI_NODE
)
1123 && !dominated_by_p (CDI_DOMINATORS
, bb_for_stmt (use_stmt
), bb
))
1126 BREAK_FROM_IMM_USE_STMT (ui2
);
1136 /* Insert a new phi node for the dereference of PHI at basic_block
1137 BB with the virtual operands from USE_STMT. */
1140 phiprop_insert_phi (basic_block bb
, tree phi
, tree use_stmt
,
1141 struct phiprop_d
*phivn
, size_t n
)
1147 /* Build a new PHI node to replace the definition of
1148 the indirect reference lhs. */
1149 res
= GIMPLE_STMT_OPERAND (use_stmt
, 0);
1150 SSA_NAME_DEF_STMT (res
) = new_phi
= create_phi_node (res
, bb
);
1152 /* Add PHI arguments for each edge inserting loads of the
1153 addressable operands. */
1154 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1156 tree old_arg
, new_var
, tmp
;
1158 old_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
1159 while (TREE_CODE (old_arg
) == SSA_NAME
1160 && (SSA_NAME_VERSION (old_arg
) >= n
1161 || phivn
[SSA_NAME_VERSION (old_arg
)].value
== NULL_TREE
))
1163 tree def_stmt
= SSA_NAME_DEF_STMT (old_arg
);
1164 old_arg
= GIMPLE_STMT_OPERAND (def_stmt
, 1);
1167 if (TREE_CODE (old_arg
) == SSA_NAME
)
1168 /* Reuse a formerly created dereference. */
1169 new_var
= phivn
[SSA_NAME_VERSION (old_arg
)].value
;
1172 old_arg
= TREE_OPERAND (old_arg
, 0);
1173 new_var
= create_tmp_var (TREE_TYPE (old_arg
), NULL
);
1174 tmp
= build2 (GIMPLE_MODIFY_STMT
, void_type_node
,
1175 NULL_TREE
, unshare_expr (old_arg
));
1176 if (TREE_CODE (TREE_TYPE (old_arg
)) == COMPLEX_TYPE
1177 || TREE_CODE (TREE_TYPE (old_arg
)) == VECTOR_TYPE
)
1178 DECL_GIMPLE_REG_P (new_var
) = 1;
1179 add_referenced_var (new_var
);
1180 new_var
= make_ssa_name (new_var
, tmp
);
1181 GIMPLE_STMT_OPERAND (tmp
, 0) = new_var
;
1183 bsi_insert_on_edge (e
, tmp
);
1186 mark_symbols_for_renaming (tmp
);
1189 add_phi_arg (new_phi
, new_var
, e
);
1192 update_stmt (new_phi
);
1197 /* Propagate between the phi node arguments of PHI in BB and phi result
1198 users. For now this matches
1199 # p_2 = PHI <&x, &y>
1206 Returns true if a transformation was done and edge insertions
1207 need to be committed. Global data PHIVN and N is used to track
1208 past transformation results. We need to be especially careful here
1209 with aliasing issues as we are moving memory reads. */
1212 propagate_with_phi (basic_block bb
, tree phi
, struct phiprop_d
*phivn
, size_t n
)
1214 tree ptr
= PHI_RESULT (phi
);
1215 tree use_stmt
, res
= NULL_TREE
;
1216 block_stmt_iterator bsi
;
1217 imm_use_iterator ui
;
1218 use_operand_p arg_p
, use
;
1222 if (MTAG_P (SSA_NAME_VAR (ptr
))
1223 || !POINTER_TYPE_P (TREE_TYPE (ptr
))
1224 || !is_gimple_reg_type (TREE_TYPE (TREE_TYPE (ptr
))))
1227 /* Check if we can "cheaply" dereference all phi arguments. */
1228 FOR_EACH_PHI_ARG (arg_p
, phi
, i
, SSA_OP_USE
)
1230 tree arg
= USE_FROM_PTR (arg_p
);
1231 /* Walk the ssa chain until we reach a ssa name we already
1232 created a value for or we reach a definition of the form
1233 ssa_name_n = &var; */
1234 while (TREE_CODE (arg
) == SSA_NAME
1235 && !SSA_NAME_IS_DEFAULT_DEF (arg
)
1236 && (SSA_NAME_VERSION (arg
) >= n
1237 || phivn
[SSA_NAME_VERSION (arg
)].value
== NULL_TREE
))
1239 tree def_stmt
= SSA_NAME_DEF_STMT (arg
);
1240 if (TREE_CODE (def_stmt
) != GIMPLE_MODIFY_STMT
)
1242 arg
= GIMPLE_STMT_OPERAND (def_stmt
, 1);
1244 if ((TREE_CODE (arg
) != ADDR_EXPR
1245 /* Avoid to have to decay *&a to a[0] later. */
1246 || !is_gimple_reg_type (TREE_TYPE (TREE_OPERAND (arg
, 0))))
1247 && !(TREE_CODE (arg
) == SSA_NAME
1248 && phivn
[SSA_NAME_VERSION (arg
)].value
!= NULL_TREE
1249 && phivn_valid_p (phivn
, arg
, bb
)))
1253 /* Find a dereferencing use. First follow (single use) ssa
1254 copy chains for ptr. */
1255 while (single_imm_use (ptr
, &use
, &use_stmt
)
1256 && TREE_CODE (use_stmt
) == GIMPLE_MODIFY_STMT
1257 && GIMPLE_STMT_OPERAND (use_stmt
, 1) == ptr
1258 && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt
, 0)) == SSA_NAME
)
1259 ptr
= GIMPLE_STMT_OPERAND (use_stmt
, 0);
1261 /* Replace the first dereference of *ptr if there is one and if we
1262 can move the loads to the place of the ptr phi node. */
1263 phi_inserted
= false;
1264 FOR_EACH_IMM_USE_STMT (use_stmt
, ui
, ptr
)
1269 /* Check whether this is a load of *ptr. */
1270 if (!(TREE_CODE (use_stmt
) == GIMPLE_MODIFY_STMT
1271 && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt
, 0)) == SSA_NAME
1272 && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt
, 1)) == INDIRECT_REF
1273 && TREE_OPERAND (GIMPLE_STMT_OPERAND (use_stmt
, 1), 0) == ptr
1274 /* We cannot replace a load that may throw or is volatile. */
1275 && !tree_can_throw_internal (use_stmt
)))
1278 /* Check if we can move the loads. The def stmts of all virtual uses
1279 need to be post-dominated by bb. */
1280 FOR_EACH_SSA_TREE_OPERAND (vuse
, use_stmt
, ui2
, SSA_OP_VUSE
)
1282 tree def_stmt
= SSA_NAME_DEF_STMT (vuse
);
1283 if (!SSA_NAME_IS_DEFAULT_DEF (vuse
)
1284 && (bb_for_stmt (def_stmt
) == bb
1285 || !dominated_by_p (CDI_DOMINATORS
,
1286 bb
, bb_for_stmt (def_stmt
))))
1290 /* Found a proper dereference. Insert a phi node if this
1291 is the first load transformation. */
1294 res
= phiprop_insert_phi (bb
, phi
, use_stmt
, phivn
, n
);
1296 /* Remember the value we created for *ptr. */
1297 phivn
[SSA_NAME_VERSION (ptr
)].value
= res
;
1298 phivn
[SSA_NAME_VERSION (ptr
)].vop_stmt
= use_stmt
;
1300 /* Remove old stmt. The phi is taken care of by DCE, if we
1301 want to delete it here we also have to delete all intermediate
1303 bsi
= bsi_for_stmt (use_stmt
);
1304 bsi_remove (&bsi
, 0);
1306 phi_inserted
= true;
1310 /* Further replacements are easy, just make a copy out of the
1312 GIMPLE_STMT_OPERAND (use_stmt
, 1) = res
;
1313 update_stmt (use_stmt
);
1317 /* Continue searching for a proper dereference. */
1320 return phi_inserted
;
1323 /* Helper walking the dominator tree starting from BB and processing
1324 phi nodes with global data PHIVN and N. */
1327 tree_ssa_phiprop_1 (basic_block bb
, struct phiprop_d
*phivn
, size_t n
)
1329 bool did_something
= false;
1333 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1334 did_something
|= propagate_with_phi (bb
, phi
, phivn
, n
);
1336 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
1338 son
= next_dom_son (CDI_DOMINATORS
, son
))
1339 did_something
|= tree_ssa_phiprop_1 (son
, phivn
, n
);
1341 return did_something
;
1344 /* Main entry for phiprop pass. */
1347 tree_ssa_phiprop (void)
1349 struct phiprop_d
*phivn
;
1351 calculate_dominance_info (CDI_DOMINATORS
);
1353 phivn
= XCNEWVEC (struct phiprop_d
, num_ssa_names
);
1355 if (tree_ssa_phiprop_1 (ENTRY_BLOCK_PTR
, phivn
, num_ssa_names
))
1356 bsi_commit_edge_inserts ();
1369 struct tree_opt_pass pass_phiprop
= {
1370 "phiprop", /* name */
1371 gate_phiprop
, /* gate */
1372 tree_ssa_phiprop
, /* execute */
1375 0, /* static_pass_number */
1376 TV_TREE_FORWPROP
, /* tv_id */
1377 PROP_cfg
| PROP_ssa
, /* properties_required */
1378 0, /* properties_provided */
1379 0, /* properties_destroyed */
1380 0, /* todo_flags_start */
1384 | TODO_verify_ssa
, /* todo_flags_finish */