1 /* Forward propagation of expressions for single use variables.
2 Copyright (C) 2004, 2005, 2007, 2008 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"
37 /* This pass propagates the RHS of assignment statements into use
38 sites of the LHS of the assignment. It's basically a specialized
39 form of tree combination. It is hoped all of this can disappear
40 when we have a generalized tree combiner.
42 Note carefully that after propagation the resulting statement
43 must still be a proper gimple statement. Right now we simply
44 only perform propagations we know will result in valid gimple
45 code. One day we'll want to generalize this code.
47 One class of common cases we handle is forward propagating a single use
48 variable into a COND_EXPR.
52 if (x) goto ... else goto ...
54 Will be transformed into:
57 if (a COND b) goto ... else goto ...
59 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
61 Or (assuming c1 and c2 are constants):
65 if (x EQ/NEQ c2) goto ... else goto ...
67 Will be transformed into:
70 if (a EQ/NEQ (c2 - c1)) goto ... else goto ...
72 Similarly for x = a - c1.
78 if (x) goto ... else goto ...
80 Will be transformed into:
83 if (a == 0) goto ... else goto ...
85 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
86 For these cases, we propagate A into all, possibly more than one,
87 COND_EXPRs that use X.
93 if (x) goto ... else goto ...
95 Will be transformed into:
98 if (a != 0) goto ... else goto ...
100 (Assuming a is an integral type and x is a boolean or x is an
101 integral and a is a boolean.)
103 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
104 For these cases, we propagate A into all, possibly more than one,
105 COND_EXPRs that use X.
107 In addition to eliminating the variable and the statement which assigns
108 a value to the variable, we may be able to later thread the jump without
109 adding insane complexity in the dominator optimizer.
111 Also note these transformations can cascade. We handle this by having
112 a worklist of COND_EXPR statements to examine. As we make a change to
113 a statement, we put it back on the worklist to examine on the next
114 iteration of the main loop.
116 A second class of propagation opportunities arises for ADDR_EXPR
127 ptr = (type1*)&type2var;
130 Will get turned into (if type1 and type2 are the same size
131 and neither have volatile on them):
132 res = VIEW_CONVERT_EXPR<type1>(type2var)
137 ptr2 = ptr + <constant>;
141 ptr2 = &x[constant/elementsize];
146 offset = index * element_size;
147 offset_p = (pointer) offset;
148 ptr2 = ptr + offset_p
150 Will get turned into:
154 We also propagate casts into SWITCH_EXPR and COND_EXPR conditions to
155 allow us to remove the cast and {NOT_EXPR,NEG_EXPR} into a subsequent
158 This will (of course) be extended as other needs arise. */
160 static bool forward_propagate_addr_expr (tree name
, tree rhs
);
162 /* Set to true if we delete EH edges during the optimization. */
163 static bool cfg_changed
;
166 /* Get the next statement we can propagate NAME's value into skipping
167 trivial copies. Returns the statement that is suitable as a
168 propagation destination or NULL_TREE if there is no such one.
169 This only returns destinations in a single-use chain. FINAL_NAME_P
170 if non-NULL is written to the ssa name that represents the use. */
173 get_prop_dest_stmt (tree name
, tree
*final_name_p
)
179 /* If name has multiple uses, bail out. */
180 if (!single_imm_use (name
, &use
, &use_stmt
))
183 /* If this is not a trivial copy, we found it. */
184 if (TREE_CODE (use_stmt
) != GIMPLE_MODIFY_STMT
185 || TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt
, 0)) != SSA_NAME
186 || GIMPLE_STMT_OPERAND (use_stmt
, 1) != name
)
189 /* Continue searching uses of the copy destination. */
190 name
= GIMPLE_STMT_OPERAND (use_stmt
, 0);
194 *final_name_p
= name
;
199 /* Get the statement we can propagate from into NAME skipping
200 trivial copies. Returns the statement which defines the
201 propagation source or NULL_TREE if there is no such one.
202 If SINGLE_USE_ONLY is set considers only sources which have
203 a single use chain up to NAME. If SINGLE_USE_P is non-null,
204 it is set to whether the chain to NAME is a single use chain
205 or not. SINGLE_USE_P is not written to if SINGLE_USE_ONLY is set. */
208 get_prop_source_stmt (tree name
, bool single_use_only
, bool *single_use_p
)
210 bool single_use
= true;
213 tree def_stmt
= SSA_NAME_DEF_STMT (name
);
215 if (!has_single_use (name
))
222 /* If name is defined by a PHI node or is the default def, bail out. */
223 if (TREE_CODE (def_stmt
) != GIMPLE_MODIFY_STMT
)
226 /* If name is not a simple copy destination, we found it. */
227 if (TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt
, 1)) != SSA_NAME
)
231 if (!single_use_only
&& single_use_p
)
232 *single_use_p
= single_use
;
234 /* We can look through pointer conversions in the search
235 for a useful stmt for the comparison folding. */
236 rhs
= GIMPLE_STMT_OPERAND (def_stmt
, 1);
237 if (CONVERT_EXPR_P (rhs
)
238 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
239 && POINTER_TYPE_P (TREE_TYPE (rhs
))
240 && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs
, 0))))
241 name
= TREE_OPERAND (rhs
, 0);
247 /* Continue searching the def of the copy source name. */
248 name
= GIMPLE_STMT_OPERAND (def_stmt
, 1);
253 /* Checks if the destination ssa name in DEF_STMT can be used as
254 propagation source. Returns true if so, otherwise false. */
257 can_propagate_from (tree def_stmt
)
259 tree rhs
= GIMPLE_STMT_OPERAND (def_stmt
, 1);
261 /* If the rhs has side-effects we cannot propagate from it. */
262 if (TREE_SIDE_EFFECTS (rhs
))
265 /* If the rhs is a load we cannot propagate from it. */
266 if (REFERENCE_CLASS_P (rhs
))
269 /* Constants can be always propagated. */
270 if (is_gimple_min_invariant (rhs
))
273 /* We cannot propagate ssa names that occur in abnormal phi nodes. */
274 switch (TREE_CODE_LENGTH (TREE_CODE (rhs
)))
277 if (TREE_OPERAND (rhs
, 2) != NULL_TREE
278 && TREE_CODE (TREE_OPERAND (rhs
, 2)) == SSA_NAME
279 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (rhs
, 2)))
282 if (TREE_OPERAND (rhs
, 1) != NULL_TREE
283 && TREE_CODE (TREE_OPERAND (rhs
, 1)) == SSA_NAME
284 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (rhs
, 1)))
287 if (TREE_OPERAND (rhs
, 0) != NULL_TREE
288 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
289 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (rhs
, 0)))
297 /* If the definition is a conversion of a pointer to a function type,
298 then we can not apply optimizations as some targets require function
299 pointers to be canonicalized and in this case this optimization could
300 eliminate a necessary canonicalization. */
301 if (CONVERT_EXPR_P (rhs
)
302 && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs
, 0)))
303 && TREE_CODE (TREE_TYPE (TREE_TYPE
304 (TREE_OPERAND (rhs
, 0)))) == FUNCTION_TYPE
)
310 /* Remove a copy chain ending in NAME along the defs but not
311 further or including UP_TO_STMT. If NAME was replaced in
312 its only use then this function can be used to clean up
313 dead stmts. Returns true if UP_TO_STMT can be removed
314 as well, otherwise false. */
317 remove_prop_source_from_use (tree name
, tree up_to_stmt
)
319 block_stmt_iterator bsi
;
323 if (!has_zero_uses (name
))
326 stmt
= SSA_NAME_DEF_STMT (name
);
327 if (stmt
== up_to_stmt
)
330 bsi
= bsi_for_stmt (stmt
);
332 bsi_remove (&bsi
, true);
334 name
= GIMPLE_STMT_OPERAND (stmt
, 1);
335 } while (TREE_CODE (name
) == SSA_NAME
);
340 /* Combine OP0 CODE OP1 in the context of a COND_EXPR. Returns
341 the folded result in a form suitable for COND_EXPR_COND or
342 NULL_TREE, if there is no suitable simplified form. If
343 INVARIANT_ONLY is true only gimple_min_invariant results are
344 considered simplified. */
347 combine_cond_expr_cond (enum tree_code code
, tree type
,
348 tree op0
, tree op1
, bool invariant_only
)
352 gcc_assert (TREE_CODE_CLASS (code
) == tcc_comparison
);
354 t
= fold_binary (code
, type
, op0
, op1
);
358 /* Require that we got a boolean type out if we put one in. */
359 gcc_assert (TREE_CODE (TREE_TYPE (t
)) == TREE_CODE (type
));
361 /* Canonicalize the combined condition for use in a COND_EXPR. */
362 t
= canonicalize_cond_expr_cond (t
);
364 /* Bail out if we required an invariant but didn't get one. */
367 && !is_gimple_min_invariant (t
)))
373 /* Propagate from the ssa name definition statements of COND_EXPR
374 in statement STMT into the conditional if that simplifies it.
375 Returns zero if no statement was changed, one if there were
376 changes and two if cfg_cleanup needs to run. */
379 forward_propagate_into_cond (tree cond_expr
, tree stmt
)
381 int did_something
= 0;
384 tree tmp
= NULL_TREE
;
385 tree cond
= COND_EXPR_COND (cond_expr
);
386 tree name
, def_stmt
, rhs0
= NULL_TREE
, rhs1
= NULL_TREE
;
387 bool single_use0_p
= false, single_use1_p
= false;
389 /* We can do tree combining on SSA_NAME and comparison expressions. */
390 if (COMPARISON_CLASS_P (cond
)
391 && TREE_CODE (TREE_OPERAND (cond
, 0)) == SSA_NAME
)
393 /* For comparisons use the first operand, that is likely to
394 simplify comparisons against constants. */
395 name
= TREE_OPERAND (cond
, 0);
396 def_stmt
= get_prop_source_stmt (name
, false, &single_use0_p
);
397 if (def_stmt
!= NULL_TREE
398 && can_propagate_from (def_stmt
))
400 tree op1
= TREE_OPERAND (cond
, 1);
401 rhs0
= GIMPLE_STMT_OPERAND (def_stmt
, 1);
402 tmp
= combine_cond_expr_cond (TREE_CODE (cond
), boolean_type_node
,
403 fold_convert (TREE_TYPE (op1
), rhs0
),
404 op1
, !single_use0_p
);
406 /* If that wasn't successful, try the second operand. */
408 && TREE_CODE (TREE_OPERAND (cond
, 1)) == SSA_NAME
)
410 tree op0
= TREE_OPERAND (cond
, 0);
411 name
= TREE_OPERAND (cond
, 1);
412 def_stmt
= get_prop_source_stmt (name
, false, &single_use1_p
);
413 if (def_stmt
== NULL_TREE
414 || !can_propagate_from (def_stmt
))
415 return did_something
;
417 rhs1
= GIMPLE_STMT_OPERAND (def_stmt
, 1);
418 tmp
= combine_cond_expr_cond (TREE_CODE (cond
), boolean_type_node
,
420 fold_convert (TREE_TYPE (op0
), rhs1
),
423 /* If that wasn't successful either, try both operands. */
426 && rhs1
!= NULL_TREE
)
427 tmp
= combine_cond_expr_cond (TREE_CODE (cond
), boolean_type_node
,
429 fold_convert (TREE_TYPE (rhs0
), rhs1
),
430 !(single_use0_p
&& single_use1_p
));
432 else if (TREE_CODE (cond
) == SSA_NAME
)
435 def_stmt
= get_prop_source_stmt (name
, true, NULL
);
436 if (def_stmt
== NULL_TREE
437 || !can_propagate_from (def_stmt
))
438 return did_something
;
440 rhs0
= GIMPLE_STMT_OPERAND (def_stmt
, 1);
441 tmp
= combine_cond_expr_cond (NE_EXPR
, boolean_type_node
, rhs0
,
442 build_int_cst (TREE_TYPE (rhs0
), 0),
448 if (dump_file
&& tmp
)
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 COND_EXPR_COND (cond_expr
) = 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
;
478 /* We've just substituted an ADDR_EXPR into stmt. Update all the
479 relevant data structures to match. */
482 tidy_after_forward_propagate_addr (tree stmt
)
484 /* We may have turned a trapping insn into a non-trapping insn. */
485 if (maybe_clean_or_replace_eh_stmt (stmt
, stmt
)
486 && tree_purge_dead_eh_edges (bb_for_stmt (stmt
)))
489 if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1)) == ADDR_EXPR
)
490 recompute_tree_invariant_for_addr_expr (GIMPLE_STMT_OPERAND (stmt
, 1));
492 mark_symbols_for_renaming (stmt
);
495 /* DEF_RHS contains the address of the 0th element in an array.
496 USE_STMT uses type of DEF_RHS to compute the address of an
497 arbitrary element within the array. The (variable) byte offset
498 of the element is contained in OFFSET.
500 We walk back through the use-def chains of OFFSET to verify that
501 it is indeed computing the offset of an element within the array
502 and extract the index corresponding to the given byte offset.
504 We then try to fold the entire address expression into a form
507 If we are successful, we replace the right hand side of USE_STMT
508 with the new address computation. */
511 forward_propagate_addr_into_variable_array_index (tree offset
,
512 tree def_rhs
, tree use_stmt
)
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 /* Get the offset's defining statement. */
524 offset
= SSA_NAME_DEF_STMT (offset
);
526 /* The statement which defines OFFSET before type conversion
527 must be a simple GIMPLE_MODIFY_STMT. */
528 if (TREE_CODE (offset
) != GIMPLE_MODIFY_STMT
)
531 /* The RHS of the statement which defines OFFSET must be a
532 multiplication of an object by the size of the array elements.
533 This implicitly verifies that the size of the array elements
535 offset
= GIMPLE_STMT_OPERAND (offset
, 1);
536 if (TREE_CODE (offset
) != MULT_EXPR
537 || TREE_CODE (TREE_OPERAND (offset
, 1)) != INTEGER_CST
538 || !simple_cst_equal (TREE_OPERAND (offset
, 1),
539 TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (def_rhs
)))))
542 /* The first operand to the MULT_EXPR is the desired index. */
543 index
= TREE_OPERAND (offset
, 0);
546 /* Replace the pointer addition with array indexing. */
547 GIMPLE_STMT_OPERAND (use_stmt
, 1) = unshare_expr (def_rhs
);
548 TREE_OPERAND (TREE_OPERAND (GIMPLE_STMT_OPERAND (use_stmt
, 1), 0), 1)
551 /* That should have created gimple, so there is no need to
552 record information to undo the propagation. */
553 fold_stmt_inplace (use_stmt
);
554 tidy_after_forward_propagate_addr (use_stmt
);
558 /* NAME is a SSA_NAME representing DEF_RHS which is of the form
559 ADDR_EXPR <whatever>.
561 Try to forward propagate the ADDR_EXPR into the use USE_STMT.
562 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
563 node or for recovery of array indexing from pointer arithmetic.
565 Return true if the propagation was successful (the propagation can
566 be not totally successful, yet things may have been changed). */
569 forward_propagate_addr_expr_1 (tree name
, tree def_rhs
, tree use_stmt
,
572 tree lhs
, rhs
, array_ref
;
575 gcc_assert (TREE_CODE (def_rhs
) == ADDR_EXPR
);
577 lhs
= GIMPLE_STMT_OPERAND (use_stmt
, 0);
578 rhs
= GIMPLE_STMT_OPERAND (use_stmt
, 1);
580 /* Trivial cases. The use statement could be a trivial copy or a
581 useless conversion. Recurse to the uses of the lhs as copyprop does
582 not copy through different variant pointers and FRE does not catch
583 all useless conversions. Treat the case of a single-use name and
584 a conversion to def_rhs type separate, though. */
585 if (TREE_CODE (lhs
) == SSA_NAME
587 || CONVERT_EXPR_P (rhs
))
588 && useless_type_conversion_p (TREE_TYPE (rhs
), TREE_TYPE (def_rhs
)))
590 /* Only recurse if we don't deal with a single use. */
592 return forward_propagate_addr_expr (lhs
, def_rhs
);
594 GIMPLE_STMT_OPERAND (use_stmt
, 1) = unshare_expr (def_rhs
);
598 /* Now strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
599 ADDR_EXPR will not appear on the LHS. */
600 lhsp
= &GIMPLE_STMT_OPERAND (use_stmt
, 0);
601 while (handled_component_p (*lhsp
))
602 lhsp
= &TREE_OPERAND (*lhsp
, 0);
605 /* Now see if the LHS node is an INDIRECT_REF using NAME. If so,
606 propagate the ADDR_EXPR into the use of NAME and fold the result. */
607 if (TREE_CODE (lhs
) == INDIRECT_REF
608 && TREE_OPERAND (lhs
, 0) == name
609 && useless_type_conversion_p (TREE_TYPE (TREE_OPERAND (lhs
, 0)),
611 /* ??? This looks redundant, but is required for bogus types
612 that can sometimes occur. */
613 && useless_type_conversion_p (TREE_TYPE (lhs
),
614 TREE_TYPE (TREE_OPERAND (def_rhs
, 0))))
616 *lhsp
= unshare_expr (TREE_OPERAND (def_rhs
, 0));
617 fold_stmt_inplace (use_stmt
);
618 tidy_after_forward_propagate_addr (use_stmt
);
620 /* Continue propagating into the RHS if this was not the only use. */
625 /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
626 nodes from the RHS. */
627 rhsp
= &GIMPLE_STMT_OPERAND (use_stmt
, 1);
628 while (handled_component_p (*rhsp
)
629 || TREE_CODE (*rhsp
) == ADDR_EXPR
)
630 rhsp
= &TREE_OPERAND (*rhsp
, 0);
633 /* Now see if the RHS node is an INDIRECT_REF using NAME. If so,
634 propagate the ADDR_EXPR into the use of NAME and fold the result. */
635 if (TREE_CODE (rhs
) == INDIRECT_REF
636 && TREE_OPERAND (rhs
, 0) == name
637 && useless_type_conversion_p (TREE_TYPE (TREE_OPERAND (rhs
, 0)),
639 /* ??? This looks redundant, but is required for bogus types
640 that can sometimes occur. */
641 && useless_type_conversion_p (TREE_TYPE (rhs
),
642 TREE_TYPE (TREE_OPERAND (def_rhs
, 0))))
644 *rhsp
= unshare_expr (TREE_OPERAND (def_rhs
, 0));
645 fold_stmt_inplace (use_stmt
);
646 tidy_after_forward_propagate_addr (use_stmt
);
650 /* Now see if the RHS node is an INDIRECT_REF using NAME. If so,
651 propagate the ADDR_EXPR into the use of NAME and try to
652 create a VCE and fold the result. */
653 if (TREE_CODE (rhs
) == INDIRECT_REF
654 && TREE_OPERAND (rhs
, 0) == name
655 && TYPE_SIZE (TREE_TYPE (rhs
))
656 && TYPE_SIZE (TREE_TYPE (TREE_OPERAND (def_rhs
, 0)))
657 /* Function decls should not be used for VCE either as it could be
658 a function descriptor that we want and not the actual function code. */
659 && TREE_CODE (TREE_OPERAND (def_rhs
, 0)) != FUNCTION_DECL
660 /* We should not convert volatile loads to non volatile loads. */
661 && !TYPE_VOLATILE (TREE_TYPE (rhs
))
662 && !TYPE_VOLATILE (TREE_TYPE (TREE_OPERAND (def_rhs
, 0)))
663 && operand_equal_p (TYPE_SIZE (TREE_TYPE (rhs
)),
664 TYPE_SIZE (TREE_TYPE (TREE_OPERAND (def_rhs
, 0))), 0))
667 tree new_rhs
= unshare_expr (TREE_OPERAND (def_rhs
, 0));
668 new_rhs
= fold_build1 (VIEW_CONVERT_EXPR
, TREE_TYPE (rhs
), new_rhs
);
669 /* If we have folded the VCE, then we have to create a new statement. */
670 if (TREE_CODE (new_rhs
) != VIEW_CONVERT_EXPR
)
672 block_stmt_iterator bsi
= bsi_for_stmt (use_stmt
);
673 new_rhs
= force_gimple_operand_bsi (&bsi
, new_rhs
, true, NULL
, true, BSI_SAME_STMT
);
674 /* As we change the deference to a SSA_NAME, we need to return false to make sure that
675 the statement does not get removed. */
679 fold_stmt_inplace (use_stmt
);
680 tidy_after_forward_propagate_addr (use_stmt
);
684 /* If the use of the ADDR_EXPR is not a POINTER_PLUS_EXPR, there
686 if (TREE_CODE (rhs
) != POINTER_PLUS_EXPR
687 || TREE_OPERAND (rhs
, 0) != name
)
690 /* The remaining cases are all for turning pointer arithmetic into
691 array indexing. They only apply when we have the address of
692 element zero in an array. If that is not the case then there
694 array_ref
= TREE_OPERAND (def_rhs
, 0);
695 if (TREE_CODE (array_ref
) != ARRAY_REF
696 || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref
, 0))) != ARRAY_TYPE
697 || !integer_zerop (TREE_OPERAND (array_ref
, 1)))
700 /* Try to optimize &x[0] p+ C where C is a multiple of the size
701 of the elements in X into &x[C/element size]. */
702 if (TREE_CODE (TREE_OPERAND (rhs
, 1)) == INTEGER_CST
)
704 tree orig
= unshare_expr (rhs
);
705 TREE_OPERAND (rhs
, 0) = unshare_expr (def_rhs
);
707 /* If folding succeeds, then we have just exposed new variables
708 in USE_STMT which will need to be renamed. If folding fails,
709 then we need to put everything back the way it was. */
710 if (fold_stmt_inplace (use_stmt
))
712 tidy_after_forward_propagate_addr (use_stmt
);
717 GIMPLE_STMT_OPERAND (use_stmt
, 1) = orig
;
718 update_stmt (use_stmt
);
723 /* Try to optimize &x[0] p+ OFFSET where OFFSET is defined by
724 converting a multiplication of an index by the size of the
725 array elements, then the result is converted into the proper
726 type for the arithmetic. */
727 if (TREE_CODE (TREE_OPERAND (rhs
, 1)) == SSA_NAME
728 /* Avoid problems with IVopts creating PLUS_EXPRs with a
729 different type than their operands. */
730 && useless_type_conversion_p (TREE_TYPE (rhs
), TREE_TYPE (name
)))
734 res
= forward_propagate_addr_into_variable_array_index (TREE_OPERAND (rhs
, 1),
741 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
743 Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME.
744 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
745 node or for recovery of array indexing from pointer arithmetic.
746 Returns true, if all uses have been propagated into. */
749 forward_propagate_addr_expr (tree name
, tree rhs
)
751 int stmt_loop_depth
= bb_for_stmt (SSA_NAME_DEF_STMT (name
))->loop_depth
;
752 imm_use_iterator iter
;
755 bool single_use_p
= has_single_use (name
);
757 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, name
)
762 /* If the use is not in a simple assignment statement, then
763 there is nothing we can do. */
764 if (TREE_CODE (use_stmt
) != GIMPLE_MODIFY_STMT
)
770 /* If the use is in a deeper loop nest, then we do not want
771 to propagate the ADDR_EXPR into the loop as that is likely
772 adding expression evaluations into the loop. */
773 if (bb_for_stmt (use_stmt
)->loop_depth
> stmt_loop_depth
)
779 push_stmt_changes (&use_stmt
);
781 result
= forward_propagate_addr_expr_1 (name
, rhs
, use_stmt
,
785 pop_stmt_changes (&use_stmt
);
787 /* Remove intermediate now unused copy and conversion chains. */
788 use_rhs
= GIMPLE_STMT_OPERAND (use_stmt
, 1);
790 && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt
, 0)) == SSA_NAME
791 && (TREE_CODE (use_rhs
) == SSA_NAME
792 || (CONVERT_EXPR_P (use_rhs
)
793 && TREE_CODE (TREE_OPERAND (use_rhs
, 0)) == SSA_NAME
)))
795 block_stmt_iterator bsi
= bsi_for_stmt (use_stmt
);
796 release_defs (use_stmt
);
797 bsi_remove (&bsi
, true);
804 /* Forward propagate the comparison COND defined in STMT like
805 cond_1 = x CMP y to uses of the form
809 Returns true if stmt is now unused. */
812 forward_propagate_comparison (tree cond
, tree stmt
)
814 tree name
= GIMPLE_STMT_OPERAND (stmt
, 0);
815 tree use_stmt
, tmp
= NULL_TREE
;
817 /* Don't propagate ssa names that occur in abnormal phis. */
818 if ((TREE_CODE (TREE_OPERAND (cond
, 0)) == SSA_NAME
819 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (cond
, 0)))
820 || (TREE_CODE (TREE_OPERAND (cond
, 1)) == SSA_NAME
821 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (cond
, 1))))
824 /* Do not un-cse comparisons. But propagate through copies. */
825 use_stmt
= get_prop_dest_stmt (name
, &name
);
826 if (use_stmt
== NULL_TREE
)
829 /* Conversion of the condition result to another integral type. */
830 if (TREE_CODE (use_stmt
) == GIMPLE_MODIFY_STMT
831 && (CONVERT_EXPR_P (GIMPLE_STMT_OPERAND (use_stmt
, 1))
832 || COMPARISON_CLASS_P (GIMPLE_STMT_OPERAND (use_stmt
, 1))
833 || TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt
, 1)) == TRUTH_NOT_EXPR
)
834 && INTEGRAL_TYPE_P (TREE_TYPE (GIMPLE_STMT_OPERAND (use_stmt
, 0))))
836 tree lhs
= GIMPLE_STMT_OPERAND (use_stmt
, 0);
837 tree rhs
= GIMPLE_STMT_OPERAND (use_stmt
, 1);
839 /* We can propagate the condition into a conversion. */
840 if (CONVERT_EXPR_P (rhs
))
842 /* Avoid using fold here as that may create a COND_EXPR with
843 non-boolean condition as canonical form. */
844 tmp
= build2 (TREE_CODE (cond
), TREE_TYPE (lhs
),
845 TREE_OPERAND (cond
, 0), TREE_OPERAND (cond
, 1));
847 /* We can propagate the condition into X op CST where op
848 is EQ_EXPR or NE_EXPR and CST is either one or zero. */
849 else if (COMPARISON_CLASS_P (rhs
)
850 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
851 && TREE_CODE (TREE_OPERAND (rhs
, 1)) == INTEGER_CST
)
853 enum tree_code code
= TREE_CODE (rhs
);
854 tree cst
= TREE_OPERAND (rhs
, 1);
856 tmp
= combine_cond_expr_cond (code
, TREE_TYPE (lhs
),
857 fold_convert (TREE_TYPE (cst
), cond
),
859 if (tmp
== NULL_TREE
)
862 /* We can propagate the condition into a statement that
863 computes the logical negation of the comparison result. */
864 else if (TREE_CODE (rhs
) == TRUTH_NOT_EXPR
)
866 tree type
= TREE_TYPE (TREE_OPERAND (cond
, 0));
867 bool nans
= HONOR_NANS (TYPE_MODE (type
));
869 code
= invert_tree_comparison (TREE_CODE (cond
), nans
);
870 if (code
== ERROR_MARK
)
873 tmp
= build2 (code
, TREE_TYPE (lhs
), TREE_OPERAND (cond
, 0),
874 TREE_OPERAND (cond
, 1));
879 GIMPLE_STMT_OPERAND (use_stmt
, 1) = unshare_expr (tmp
);
880 update_stmt (use_stmt
);
882 /* Remove defining statements. */
883 remove_prop_source_from_use (name
, stmt
);
885 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
887 fprintf (dump_file
, " Replaced '");
888 print_generic_expr (dump_file
, rhs
, dump_flags
);
889 fprintf (dump_file
, "' with '");
890 print_generic_expr (dump_file
, tmp
, dump_flags
);
891 fprintf (dump_file
, "'\n");
900 /* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y.
901 If so, we can change STMT into lhs = y which can later be copy
902 propagated. Similarly for negation.
904 This could trivially be formulated as a forward propagation
905 to immediate uses. However, we already had an implementation
906 from DOM which used backward propagation via the use-def links.
908 It turns out that backward propagation is actually faster as
909 there's less work to do for each NOT/NEG expression we find.
910 Backwards propagation needs to look at the statement in a single
911 backlink. Forward propagation needs to look at potentially more
912 than one forward link. */
915 simplify_not_neg_expr (tree stmt
)
917 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
918 tree rhs_def_stmt
= SSA_NAME_DEF_STMT (TREE_OPERAND (rhs
, 0));
920 /* See if the RHS_DEF_STMT has the same form as our statement. */
921 if (TREE_CODE (rhs_def_stmt
) == GIMPLE_MODIFY_STMT
922 && TREE_CODE (GIMPLE_STMT_OPERAND (rhs_def_stmt
, 1)) == TREE_CODE (rhs
))
924 tree rhs_def_operand
=
925 TREE_OPERAND (GIMPLE_STMT_OPERAND (rhs_def_stmt
, 1), 0);
927 /* Verify that RHS_DEF_OPERAND is a suitable SSA_NAME. */
928 if (TREE_CODE (rhs_def_operand
) == SSA_NAME
929 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand
))
931 GIMPLE_STMT_OPERAND (stmt
, 1) = rhs_def_operand
;
937 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
938 the condition which we may be able to optimize better. */
941 simplify_switch_expr (tree stmt
)
943 tree cond
= SWITCH_COND (stmt
);
946 /* The optimization that we really care about is removing unnecessary
947 casts. That will let us do much better in propagating the inferred
948 constant at the switch target. */
949 if (TREE_CODE (cond
) == SSA_NAME
)
951 def
= SSA_NAME_DEF_STMT (cond
);
952 if (TREE_CODE (def
) == GIMPLE_MODIFY_STMT
)
954 def
= GIMPLE_STMT_OPERAND (def
, 1);
955 if (TREE_CODE (def
) == NOP_EXPR
)
960 def
= TREE_OPERAND (def
, 0);
962 #ifdef ENABLE_CHECKING
963 /* ??? Why was Jeff testing this? We are gimple... */
964 gcc_assert (is_gimple_val (def
));
967 to
= TREE_TYPE (cond
);
968 ti
= TREE_TYPE (def
);
970 /* If we have an extension that preserves value, then we
971 can copy the source value into the switch. */
973 need_precision
= TYPE_PRECISION (ti
);
975 if (! INTEGRAL_TYPE_P (ti
))
977 else if (TYPE_UNSIGNED (to
) && !TYPE_UNSIGNED (ti
))
979 else if (!TYPE_UNSIGNED (to
) && TYPE_UNSIGNED (ti
))
981 if (TYPE_PRECISION (to
) < need_precision
)
986 SWITCH_COND (stmt
) = def
;
994 /* Main entry point for the forward propagation optimizer. */
997 tree_ssa_forward_propagate_single_use_vars (void)
1000 unsigned int todoflags
= 0;
1002 cfg_changed
= false;
1006 block_stmt_iterator bsi
;
1008 /* Note we update BSI within the loop as necessary. */
1009 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); )
1011 tree stmt
= bsi_stmt (bsi
);
1013 /* If this statement sets an SSA_NAME to an address,
1014 try to propagate the address into the uses of the SSA_NAME. */
1015 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
1017 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
1018 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
1021 if (TREE_CODE (lhs
) != SSA_NAME
)
1027 if (TREE_CODE (rhs
) == ADDR_EXPR
1028 /* Handle pointer conversions on invariant addresses
1029 as well, as this is valid gimple. */
1030 || (CONVERT_EXPR_P (rhs
)
1031 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == ADDR_EXPR
1032 && POINTER_TYPE_P (TREE_TYPE (rhs
))))
1035 if (!stmt_references_abnormal_ssa_name (stmt
)
1036 && forward_propagate_addr_expr (lhs
, rhs
))
1038 release_defs (stmt
);
1039 todoflags
|= TODO_remove_unused_locals
;
1040 bsi_remove (&bsi
, true);
1045 else if ((TREE_CODE (rhs
) == BIT_NOT_EXPR
1046 || TREE_CODE (rhs
) == NEGATE_EXPR
)
1047 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
)
1049 simplify_not_neg_expr (stmt
);
1052 else if (TREE_CODE (rhs
) == COND_EXPR
)
1055 fold_defer_overflow_warnings ();
1056 did_something
= forward_propagate_into_cond (rhs
, stmt
);
1057 if (did_something
== 2)
1059 fold_undefer_overflow_warnings (!TREE_NO_WARNING (rhs
)
1060 && did_something
, stmt
, WARN_STRICT_OVERFLOW_CONDITIONAL
);
1063 else if (COMPARISON_CLASS_P (rhs
))
1065 if (forward_propagate_comparison (rhs
, stmt
))
1067 release_defs (stmt
);
1068 todoflags
|= TODO_remove_unused_locals
;
1069 bsi_remove (&bsi
, true);
1077 else if (TREE_CODE (stmt
) == SWITCH_EXPR
)
1079 simplify_switch_expr (stmt
);
1082 else if (TREE_CODE (stmt
) == COND_EXPR
)
1085 fold_defer_overflow_warnings ();
1086 did_something
= forward_propagate_into_cond (stmt
, stmt
);
1087 if (did_something
== 2)
1089 fold_undefer_overflow_warnings (did_something
, stmt
,
1090 WARN_STRICT_OVERFLOW_CONDITIONAL
);
1099 todoflags
|= TODO_cleanup_cfg
;
1105 gate_forwprop (void)
1110 struct gimple_opt_pass pass_forwprop
=
1114 "forwprop", /* name */
1115 gate_forwprop
, /* gate */
1116 tree_ssa_forward_propagate_single_use_vars
, /* execute */
1119 0, /* static_pass_number */
1120 TV_TREE_FORWPROP
, /* tv_id */
1121 PROP_cfg
| PROP_ssa
, /* properties_required */
1122 0, /* properties_provided */
1123 0, /* properties_destroyed */
1124 0, /* todo_flags_start */
1128 | TODO_verify_ssa
/* todo_flags_finish */