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"
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.
41 Note carefully that after propagation the resulting statement
42 must still be a proper gimple statement. Right now we simply
43 only perform propagations we know will result in valid gimple
44 code. One day we'll want to generalize this code.
46 One class of common cases we handle is forward propagating a single use
47 variable into a COND_EXPR.
51 if (x) goto ... else goto ...
53 Will be transformed into:
56 if (a COND b) goto ... else goto ...
58 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
60 Or (assuming c1 and c2 are constants):
64 if (x EQ/NEQ c2) goto ... else goto ...
66 Will be transformed into:
69 if (a EQ/NEQ (c2 - c1)) goto ... else goto ...
71 Similarly for x = a - c1.
77 if (x) goto ... else goto ...
79 Will be transformed into:
82 if (a == 0) goto ... else goto ...
84 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
85 For these cases, we propagate A into all, possibly more than one,
86 COND_EXPRs that use X.
92 if (x) goto ... else goto ...
94 Will be transformed into:
97 if (a != 0) goto ... else goto ...
99 (Assuming a is an integral type and x is a boolean or x is an
100 integral and a is a boolean.)
102 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
103 For these cases, we propagate A into all, possibly more than one,
104 COND_EXPRs that use X.
106 In addition to eliminating the variable and the statement which assigns
107 a value to the variable, we may be able to later thread the jump without
108 adding insane complexity in the dominator optimizer.
110 Also note these transformations can cascade. We handle this by having
111 a worklist of COND_EXPR statements to examine. As we make a change to
112 a statement, we put it back on the worklist to examine on the next
113 iteration of the main loop.
115 A second class of propagation opportunities arises for ADDR_EXPR
128 ptr2 = ptr + <constant>;
132 ptr2 = &x[constant/elementsize];
137 offset = index * element_size;
138 offset_p = (pointer) offset;
139 ptr2 = ptr + offset_p
141 Will get turned into:
146 This will (of course) be extended as other needs arise. */
149 /* Set to true if we delete EH edges during the optimization. */
150 static bool cfg_changed
;
153 /* Given an SSA_NAME VAR, return true if and only if VAR is defined by
157 ssa_name_defined_by_comparison_p (tree var
)
159 tree def
= SSA_NAME_DEF_STMT (var
);
161 if (TREE_CODE (def
) == MODIFY_EXPR
)
163 tree rhs
= TREE_OPERAND (def
, 1);
164 return COMPARISON_CLASS_P (rhs
);
170 /* Forward propagate a single-use variable into COND once. Return a
171 new condition if successful. Return NULL_TREE otherwise. */
174 forward_propagate_into_cond_1 (tree cond
, tree
*test_var_p
)
176 tree new_cond
= NULL_TREE
;
177 enum tree_code cond_code
= TREE_CODE (cond
);
178 tree test_var
= NULL_TREE
;
182 /* If the condition is not a lone variable or an equality test of an
183 SSA_NAME against an integral constant, then we do not have an
186 Note these conditions also ensure the COND_EXPR has no
187 virtual operands or other side effects. */
188 if (cond_code
!= SSA_NAME
189 && !((cond_code
== EQ_EXPR
|| cond_code
== NE_EXPR
)
190 && TREE_CODE (TREE_OPERAND (cond
, 0)) == SSA_NAME
191 && CONSTANT_CLASS_P (TREE_OPERAND (cond
, 1))
192 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond
, 1)))))
195 /* Extract the single variable used in the test into TEST_VAR. */
196 if (cond_code
== SSA_NAME
)
199 test_var
= TREE_OPERAND (cond
, 0);
201 /* Now get the defining statement for TEST_VAR. Skip this case if
202 it's not defined by some MODIFY_EXPR. */
203 def
= SSA_NAME_DEF_STMT (test_var
);
204 if (TREE_CODE (def
) != MODIFY_EXPR
)
207 def_rhs
= TREE_OPERAND (def
, 1);
209 /* If TEST_VAR is set by adding or subtracting a constant
210 from an SSA_NAME, then it is interesting to us as we
211 can adjust the constant in the conditional and thus
212 eliminate the arithmetic operation. */
213 if (TREE_CODE (def_rhs
) == PLUS_EXPR
214 || TREE_CODE (def_rhs
) == MINUS_EXPR
)
216 tree op0
= TREE_OPERAND (def_rhs
, 0);
217 tree op1
= TREE_OPERAND (def_rhs
, 1);
219 /* The first operand must be an SSA_NAME and the second
220 operand must be a constant. */
221 if (TREE_CODE (op0
) != SSA_NAME
222 || !CONSTANT_CLASS_P (op1
)
223 || !INTEGRAL_TYPE_P (TREE_TYPE (op1
)))
226 /* Don't propagate if the first operand occurs in
228 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0
))
231 if (has_single_use (test_var
))
233 enum tree_code new_code
;
236 /* If the variable was defined via X + C, then we must
237 subtract C from the constant in the conditional.
238 Otherwise we add C to the constant in the
239 conditional. The result must fold into a valid
240 gimple operand to be optimizable. */
241 new_code
= (TREE_CODE (def_rhs
) == PLUS_EXPR
242 ? MINUS_EXPR
: PLUS_EXPR
);
243 t
= int_const_binop (new_code
, TREE_OPERAND (cond
, 1), op1
, 0);
244 if (!is_gimple_val (t
))
247 new_cond
= build2 (cond_code
, boolean_type_node
, op0
, t
);
251 /* These cases require comparisons of a naked SSA_NAME or
252 comparison of an SSA_NAME against zero or one. */
253 else if (TREE_CODE (cond
) == SSA_NAME
254 || integer_zerop (TREE_OPERAND (cond
, 1))
255 || integer_onep (TREE_OPERAND (cond
, 1)))
257 /* If TEST_VAR is set from a relational operation
258 between two SSA_NAMEs or a combination of an SSA_NAME
259 and a constant, then it is interesting. */
260 if (COMPARISON_CLASS_P (def_rhs
))
262 tree op0
= TREE_OPERAND (def_rhs
, 0);
263 tree op1
= TREE_OPERAND (def_rhs
, 1);
265 /* Both operands of DEF_RHS must be SSA_NAMEs or
267 if ((TREE_CODE (op0
) != SSA_NAME
268 && !is_gimple_min_invariant (op0
))
269 || (TREE_CODE (op1
) != SSA_NAME
270 && !is_gimple_min_invariant (op1
)))
273 /* Don't propagate if the first operand occurs in
275 if (TREE_CODE (op0
) == SSA_NAME
276 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0
))
279 /* Don't propagate if the second operand occurs in
281 if (TREE_CODE (op1
) == SSA_NAME
282 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1
))
285 if (has_single_use (test_var
))
287 /* TEST_VAR was set from a relational operator. */
288 new_cond
= build2 (TREE_CODE (def_rhs
),
289 boolean_type_node
, op0
, op1
);
291 /* Invert the conditional if necessary. */
292 if ((cond_code
== EQ_EXPR
293 && integer_zerop (TREE_OPERAND (cond
, 1)))
294 || (cond_code
== NE_EXPR
295 && integer_onep (TREE_OPERAND (cond
, 1))))
297 new_cond
= invert_truthvalue (new_cond
);
299 /* If we did not get a simple relational
300 expression or bare SSA_NAME, then we can
301 not optimize this case. */
302 if (!COMPARISON_CLASS_P (new_cond
)
303 && TREE_CODE (new_cond
) != SSA_NAME
)
304 new_cond
= NULL_TREE
;
309 /* If TEST_VAR is set from a TRUTH_NOT_EXPR, then it
311 else if (TREE_CODE (def_rhs
) == TRUTH_NOT_EXPR
)
313 enum tree_code new_code
;
315 def_rhs
= TREE_OPERAND (def_rhs
, 0);
317 /* DEF_RHS must be an SSA_NAME or constant. */
318 if (TREE_CODE (def_rhs
) != SSA_NAME
319 && !is_gimple_min_invariant (def_rhs
))
322 /* Don't propagate if the operand occurs in
324 if (TREE_CODE (def_rhs
) == SSA_NAME
325 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_rhs
))
328 if (cond_code
== SSA_NAME
329 || (cond_code
== NE_EXPR
330 && integer_zerop (TREE_OPERAND (cond
, 1)))
331 || (cond_code
== EQ_EXPR
332 && integer_onep (TREE_OPERAND (cond
, 1))))
337 new_cond
= build2 (new_code
, boolean_type_node
, def_rhs
,
338 fold_convert (TREE_TYPE (def_rhs
),
342 /* If TEST_VAR was set from a cast of an integer type
343 to a boolean type or a cast of a boolean to an
344 integral, then it is interesting. */
345 else if (TREE_CODE (def_rhs
) == NOP_EXPR
346 || TREE_CODE (def_rhs
) == CONVERT_EXPR
)
351 outer_type
= TREE_TYPE (def_rhs
);
352 inner_type
= TREE_TYPE (TREE_OPERAND (def_rhs
, 0));
354 if ((TREE_CODE (outer_type
) == BOOLEAN_TYPE
355 && INTEGRAL_TYPE_P (inner_type
))
356 || (TREE_CODE (inner_type
) == BOOLEAN_TYPE
357 && INTEGRAL_TYPE_P (outer_type
)))
359 else if (INTEGRAL_TYPE_P (outer_type
)
360 && INTEGRAL_TYPE_P (inner_type
)
361 && TREE_CODE (TREE_OPERAND (def_rhs
, 0)) == SSA_NAME
362 && ssa_name_defined_by_comparison_p (TREE_OPERAND (def_rhs
,
368 /* Don't propagate if the operand occurs in
370 if (TREE_CODE (TREE_OPERAND (def_rhs
, 0)) == SSA_NAME
371 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND
375 if (has_single_use (test_var
))
377 enum tree_code new_code
;
380 if (cond_code
== SSA_NAME
381 || (cond_code
== NE_EXPR
382 && integer_zerop (TREE_OPERAND (cond
, 1)))
383 || (cond_code
== EQ_EXPR
384 && integer_onep (TREE_OPERAND (cond
, 1))))
389 new_arg
= TREE_OPERAND (def_rhs
, 0);
390 new_cond
= build2 (new_code
, boolean_type_node
, new_arg
,
391 fold_convert (TREE_TYPE (new_arg
),
397 *test_var_p
= test_var
;
401 /* Forward propagate a single-use variable into COND_EXPR as many
402 times as possible. */
405 forward_propagate_into_cond (tree cond_expr
)
407 gcc_assert (TREE_CODE (cond_expr
) == COND_EXPR
);
411 tree test_var
= NULL_TREE
;
412 tree cond
= COND_EXPR_COND (cond_expr
);
413 tree new_cond
= forward_propagate_into_cond_1 (cond
, &test_var
);
415 /* Return if unsuccessful. */
416 if (new_cond
== NULL_TREE
)
420 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
422 fprintf (dump_file
, " Replaced '");
423 print_generic_expr (dump_file
, cond
, dump_flags
);
424 fprintf (dump_file
, "' with '");
425 print_generic_expr (dump_file
, new_cond
, dump_flags
);
426 fprintf (dump_file
, "'\n");
429 COND_EXPR_COND (cond_expr
) = new_cond
;
430 update_stmt (cond_expr
);
432 if (has_zero_uses (test_var
))
434 tree def
= SSA_NAME_DEF_STMT (test_var
);
435 block_stmt_iterator bsi
= bsi_for_stmt (def
);
441 /* We've just substituted an ADDR_EXPR into stmt. Update all the
442 relevant data structures to match. */
445 tidy_after_forward_propagate_addr (tree stmt
)
447 mark_new_vars_to_rename (stmt
);
449 /* We may have turned a trapping insn into a non-trapping insn. */
450 if (maybe_clean_or_replace_eh_stmt (stmt
, stmt
)
451 && tree_purge_dead_eh_edges (bb_for_stmt (stmt
)))
454 if (TREE_CODE (TREE_OPERAND (stmt
, 1)) == ADDR_EXPR
)
455 recompute_tree_invariant_for_addr_expr (TREE_OPERAND (stmt
, 1));
460 /* STMT defines LHS which is contains the address of the 0th element
461 in an array. USE_STMT uses LHS to compute the address of an
462 arbitrary element within the array. The (variable) byte offset
463 of the element is contained in OFFSET.
465 We walk back through the use-def chains of OFFSET to verify that
466 it is indeed computing the offset of an element within the array
467 and extract the index corresponding to the given byte offset.
469 We then try to fold the entire address expression into a form
472 If we are successful, we replace the right hand side of USE_STMT
473 with the new address computation. */
476 forward_propagate_addr_into_variable_array_index (tree offset
, tree lhs
,
477 tree stmt
, tree use_stmt
)
481 /* The offset must be defined by a simple MODIFY_EXPR statement. */
482 if (TREE_CODE (offset
) != MODIFY_EXPR
)
485 /* The RHS of the statement which defines OFFSET must be a gimple
486 cast of another SSA_NAME. */
487 offset
= TREE_OPERAND (offset
, 1);
488 if (!is_gimple_cast (offset
))
491 offset
= TREE_OPERAND (offset
, 0);
492 if (TREE_CODE (offset
) != SSA_NAME
)
495 /* Get the defining statement of the offset before type
497 offset
= SSA_NAME_DEF_STMT (offset
);
499 /* The statement which defines OFFSET before type conversion
500 must be a simple MODIFY_EXPR. */
501 if (TREE_CODE (offset
) != MODIFY_EXPR
)
504 /* The RHS of the statement which defines OFFSET must be a
505 multiplication of an object by the size of the array elements.
506 This implicitly verifies that the size of the array elements
508 offset
= TREE_OPERAND (offset
, 1);
509 if (TREE_CODE (offset
) != MULT_EXPR
510 || TREE_CODE (TREE_OPERAND (offset
, 1)) != INTEGER_CST
511 || !simple_cst_equal (TREE_OPERAND (offset
, 1),
512 TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (lhs
)))))
515 /* The first operand to the MULT_EXPR is the desired index. */
516 index
= TREE_OPERAND (offset
, 0);
518 /* Replace the pointer addition with array indexing. */
519 TREE_OPERAND (use_stmt
, 1) = unshare_expr (TREE_OPERAND (stmt
, 1));
520 TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (use_stmt
, 1), 0), 1) = index
;
522 /* That should have created gimple, so there is no need to
523 record information to undo the propagation. */
524 fold_stmt_inplace (use_stmt
);
525 tidy_after_forward_propagate_addr (use_stmt
);
529 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
531 Try to forward propagate the ADDR_EXPR into the use USE_STMT.
532 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
533 node or for recovery of array indexing from pointer arithmetic.
534 Return true, if the propagation was successful. */
537 forward_propagate_addr_expr_1 (tree stmt
, tree use_stmt
)
539 tree name
= TREE_OPERAND (stmt
, 0);
540 tree lhs
, rhs
, array_ref
;
542 /* Strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
543 ADDR_EXPR will not appear on the LHS. */
544 lhs
= TREE_OPERAND (use_stmt
, 0);
545 while (TREE_CODE (lhs
) == COMPONENT_REF
|| TREE_CODE (lhs
) == ARRAY_REF
)
546 lhs
= TREE_OPERAND (lhs
, 0);
548 /* Now see if the LHS node is an INDIRECT_REF using NAME. If so,
549 propagate the ADDR_EXPR into the use of NAME and fold the result. */
550 if (TREE_CODE (lhs
) == INDIRECT_REF
&& TREE_OPERAND (lhs
, 0) == name
)
552 /* This should always succeed in creating gimple, so there is
553 no need to save enough state to undo this propagation. */
554 TREE_OPERAND (lhs
, 0) = unshare_expr (TREE_OPERAND (stmt
, 1));
555 fold_stmt_inplace (use_stmt
);
556 tidy_after_forward_propagate_addr (use_stmt
);
560 /* Trivial case. The use statement could be a trivial copy. We
561 go ahead and handle that case here since it's trivial and
562 removes the need to run copy-prop before this pass to get
563 the best results. Also note that by handling this case here
564 we can catch some cascading effects, ie the single use is
565 in a copy, and the copy is used later by a single INDIRECT_REF
567 if (TREE_CODE (lhs
) == SSA_NAME
&& TREE_OPERAND (use_stmt
, 1) == name
)
569 TREE_OPERAND (use_stmt
, 1) = unshare_expr (TREE_OPERAND (stmt
, 1));
570 tidy_after_forward_propagate_addr (use_stmt
);
574 /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
575 nodes from the RHS. */
576 rhs
= TREE_OPERAND (use_stmt
, 1);
577 while (TREE_CODE (rhs
) == COMPONENT_REF
578 || TREE_CODE (rhs
) == ARRAY_REF
579 || TREE_CODE (rhs
) == ADDR_EXPR
)
580 rhs
= TREE_OPERAND (rhs
, 0);
582 /* Now see if the RHS node is an INDIRECT_REF using NAME. If so,
583 propagate the ADDR_EXPR into the use of NAME and fold the result. */
584 if (TREE_CODE (rhs
) == INDIRECT_REF
&& TREE_OPERAND (rhs
, 0) == name
)
586 /* This should always succeed in creating gimple, so there is
587 no need to save enough state to undo this propagation. */
588 TREE_OPERAND (rhs
, 0) = unshare_expr (TREE_OPERAND (stmt
, 1));
589 fold_stmt_inplace (use_stmt
);
590 tidy_after_forward_propagate_addr (use_stmt
);
594 /* The remaining cases are all for turning pointer arithmetic into
595 array indexing. They only apply when we have the address of
596 element zero in an array. If that is not the case then there
598 array_ref
= TREE_OPERAND (TREE_OPERAND (stmt
, 1), 0);
599 if (TREE_CODE (array_ref
) != ARRAY_REF
600 || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref
, 0))) != ARRAY_TYPE
601 || !integer_zerop (TREE_OPERAND (array_ref
, 1)))
604 /* If the use of the ADDR_EXPR must be a PLUS_EXPR, or else there
606 if (TREE_CODE (rhs
) != PLUS_EXPR
)
609 /* Try to optimize &x[0] + C where C is a multiple of the size
610 of the elements in X into &x[C/element size]. */
611 if (TREE_OPERAND (rhs
, 0) == name
612 && TREE_CODE (TREE_OPERAND (rhs
, 1)) == INTEGER_CST
)
614 tree orig
= unshare_expr (rhs
);
615 TREE_OPERAND (rhs
, 0) = unshare_expr (TREE_OPERAND (stmt
, 1));
617 /* If folding succeeds, then we have just exposed new variables
618 in USE_STMT which will need to be renamed. If folding fails,
619 then we need to put everything back the way it was. */
620 if (fold_stmt_inplace (use_stmt
))
622 tidy_after_forward_propagate_addr (use_stmt
);
627 TREE_OPERAND (use_stmt
, 1) = orig
;
628 update_stmt (use_stmt
);
633 /* Try to optimize &x[0] + OFFSET where OFFSET is defined by
634 converting a multiplication of an index by the size of the
635 array elements, then the result is converted into the proper
636 type for the arithmetic. */
637 if (TREE_OPERAND (rhs
, 0) == name
638 && TREE_CODE (TREE_OPERAND (rhs
, 1)) == SSA_NAME
639 /* Avoid problems with IVopts creating PLUS_EXPRs with a
640 different type than their operands. */
641 && lang_hooks
.types_compatible_p (TREE_TYPE (name
), TREE_TYPE (rhs
)))
643 tree offset_stmt
= SSA_NAME_DEF_STMT (TREE_OPERAND (rhs
, 1));
644 return forward_propagate_addr_into_variable_array_index (offset_stmt
, lhs
,
648 /* Same as the previous case, except the operands of the PLUS_EXPR
650 if (TREE_OPERAND (rhs
, 1) == name
651 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
652 /* Avoid problems with IVopts creating PLUS_EXPRs with a
653 different type than their operands. */
654 && lang_hooks
.types_compatible_p (TREE_TYPE (name
), TREE_TYPE (rhs
)))
656 tree offset_stmt
= SSA_NAME_DEF_STMT (TREE_OPERAND (rhs
, 0));
657 return forward_propagate_addr_into_variable_array_index (offset_stmt
, lhs
,
663 /* Return TRUE iff STMT is a MODIFY_EXPR of the form
666 static bool cast_conversion_assignment_p (tree stmt
)
672 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
675 lhs
= TREE_OPERAND (stmt
, 0);
676 rhs
= TREE_OPERAND (stmt
, 1);
677 if ((TREE_CODE (rhs
) == NOP_EXPR
678 || TREE_CODE (rhs
) == CONVERT_EXPR
)
679 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
680 && TREE_CODE (lhs
) == SSA_NAME
)
686 /* STMT is a comparision and it uses DEF_STMT.
687 DEF_STMT is a modify expression that applys cast.
688 Return TRUE iff, it is OK to replace use of DEF_STMT by LHS's
689 inner type. If NEW_STMT is not NULL then */
691 replacable_use_in_cond_expr (tree stmt
, tree def_stmt
, tree
*new_stmt
)
693 tree op0
, op1
, candidate_op
, other_op
, temp
, def_rhs
, def_rhs_inner_type
;
696 gcc_assert (def_stmt
);
697 gcc_assert (COMPARISON_CLASS_P (stmt
));
698 gcc_assert (TREE_CODE (def_stmt
) == MODIFY_EXPR
);
700 candidate_op
= NULL_TREE
;
701 other_op
= NULL_TREE
;
703 op0
= TREE_OPERAND (stmt
, 0);
704 op1
= TREE_OPERAND (stmt
, 1);
706 if (TREE_CODE (op0
) == SSA_NAME
707 && SSA_NAME_DEF_STMT (op0
) == def_stmt
708 && is_gimple_min_invariant (op1
))
713 else if (TREE_CODE (op1
) == SSA_NAME
714 && SSA_NAME_DEF_STMT (op1
) == def_stmt
715 && is_gimple_min_invariant (op0
))
723 /* If either operand to the comparison is a pointer to
724 a function, then we can not apply this optimization
725 as some targets require function pointers to be
726 canonicalized and in this case this optimization would
727 eliminate a necessary canonicalization. */
728 if ((POINTER_TYPE_P (TREE_TYPE (op0
))
729 && TREE_CODE (TREE_TYPE (TREE_TYPE (op0
))) == FUNCTION_TYPE
)
730 || (POINTER_TYPE_P (TREE_TYPE (op1
))
731 && TREE_CODE (TREE_TYPE (TREE_TYPE (op1
))) == FUNCTION_TYPE
))
734 if (!cast_conversion_assignment_p (def_stmt
))
737 /* What we want to prove is that if we convert CANDIDATE_OP to
738 the type of the object inside the NOP_EXPR that the
739 result is still equivalent to SRC. */
740 def_rhs
= TREE_OPERAND (def_stmt
, 1);
741 def_rhs_inner_type
= TREE_TYPE (TREE_OPERAND (def_rhs
, 0));
743 /* If the inner type of the conversion is a pointer to
744 a function, then we can not apply this optimization
745 as some targets require function pointers to be
746 canonicalized. This optimization would result in
747 canonicalization of the pointer when it was not originally
749 if (POINTER_TYPE_P (def_rhs_inner_type
)
750 && TREE_CODE (TREE_TYPE (def_rhs_inner_type
)) == FUNCTION_TYPE
)
753 temp
= build1 (TREE_CODE (def_rhs
), def_rhs_inner_type
, other_op
);
755 if (is_gimple_val (temp
) && tree_int_cst_equal (temp
, other_op
))
758 *new_stmt
= build2 (TREE_CODE (stmt
), TREE_TYPE (stmt
),
759 TREE_OPERAND (def_rhs
, 0), temp
);
767 /* Return TRUE iff all uses of STMT are candidate for replacement. */
769 all_uses_are_replacable (tree stmt
, bool replace
)
771 bool replacable
= true;
772 imm_use_iterator imm_iter
;
776 if (NUM_SSA_OPERANDS (stmt
, SSA_OP_DEF
) != 1)
779 def
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_DEF
);
781 FOR_EACH_IMM_USE_SAFE (use_p
, imm_iter
, def
)
783 tree use
= USE_STMT (use_p
);
785 BREAK_FROM_SAFE_IMM_USE (imm_iter
);
787 if (replace
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
789 fprintf (dump_file
, " Removing casts");
790 print_generic_expr (dump_file
, use
, dump_flags
);
791 fprintf (dump_file
, "\n");
794 if (TREE_CODE (use
) == MODIFY_EXPR
)
796 replacable
= cast_conversion_assignment_p (use
);
802 USE: c = (undo_cast) a;
808 tree def_rhs
= TREE_OPERAND (stmt
, 1);
809 tree def_rhs_inner
= TREE_OPERAND (def_rhs
, 0);
810 tree use_lhs
= TREE_OPERAND (use
, 0);
812 tree def_rhs_inner_type
= TREE_TYPE (def_rhs_inner
);
813 tree use_lhs_type
= TREE_TYPE (use_lhs
);
815 if ((TYPE_PRECISION (def_rhs_inner_type
)
816 == TYPE_PRECISION (use_lhs_type
))
817 && (TYPE_MAIN_VARIANT (def_rhs_inner_type
)
818 == TYPE_MAIN_VARIANT (use_lhs_type
)))
820 TREE_OPERAND (use
, 1) = TREE_OPERAND (def_rhs
, 0);
825 else if (TREE_CODE (use
) == COND_EXPR
826 && COMPARISON_CLASS_P (COND_EXPR_COND (use
)))
830 tree new_cond
= NULL_TREE
;
831 replacable
= replacable_use_in_cond_expr (COND_EXPR_COND (use
),
835 COND_EXPR_COND (use
) = new_cond
;
842 replacable
= replacable_use_in_cond_expr (COND_EXPR_COND (use
),
852 /* Return TRUE if STMT is part of a pttern that can be simplified.
853 (STMT is a cast operation). */
855 replacable_cast_pattern (tree stmt
)
857 /* (2) Look for the following pattern:
858 S1: X = (widening_cast) x;
859 S2: Y = lshift (X, z);
860 S3: y = (narrowing_cast) Y;
866 S1: X = (widening_cast) x;
867 S2: Y = lshift (X, z);
868 S3: y = (narrowing_cast) Y;
869 S4: y_new = lshift (x, z);
873 DCE will remove S1,S2,S3 if possible.
875 tree def_stmt
, oprnd0
, oprnd1
;
876 tree var
, var_name
, new_stmt
;
877 block_stmt_iterator si
;
878 tree rhs
= TREE_OPERAND (stmt
, 1);
879 tree rhs_inner
= TREE_OPERAND (rhs
, 0);
880 tree type
= TREE_TYPE (rhs
);
881 tree inner_type
= TREE_TYPE (rhs_inner
);
882 imm_use_iterator imm_iter
;
885 if (TREE_CODE (rhs_inner
) != SSA_NAME
)
887 def_stmt
= SSA_NAME_DEF_STMT (rhs_inner
);
888 if (TREE_CODE (def_stmt
) != MODIFY_EXPR
)
890 rhs
= TREE_OPERAND (def_stmt
, 1);
891 if (TREE_CODE (rhs
) != LSHIFT_EXPR
)
893 oprnd0
= TREE_OPERAND (rhs
, 0);
894 oprnd1
= TREE_OPERAND (rhs
, 1);
895 if (TREE_CODE (oprnd0
) != SSA_NAME
)
897 def_stmt
= SSA_NAME_DEF_STMT (oprnd0
);
898 if (!cast_conversion_assignment_p (def_stmt
))
900 rhs
= TREE_OPERAND (def_stmt
, 1);
901 rhs_inner
= TREE_OPERAND (rhs
, 0);
902 if (TYPE_MAIN_VARIANT (TREE_TYPE (rhs
)) != TYPE_MAIN_VARIANT (inner_type
))
904 if (TYPE_MAIN_VARIANT (TREE_TYPE (rhs_inner
)) != TYPE_MAIN_VARIANT (type
))
907 /* Pattern detected. Replace. */
908 rhs
= build2 (LSHIFT_EXPR
, type
, rhs_inner
, oprnd1
);
909 var
= create_tmp_var (type
, "tmp");
910 add_referenced_tmp_var (var
);
911 var_name
= make_ssa_name (var
, NULL_TREE
);
912 new_stmt
= build2 (MODIFY_EXPR
, type
, var_name
, rhs
);
913 SSA_NAME_DEF_STMT (var_name
) = new_stmt
;
914 si
= bsi_for_stmt (stmt
);
915 bsi_insert_before (&si
, new_stmt
, BSI_SAME_STMT
);
916 FOR_EACH_IMM_USE_SAFE (use_p
, imm_iter
, TREE_OPERAND (stmt
, 0))
917 SET_USE (use_p
, var_name
);
922 eliminate_unnecessary_casts (void)
925 block_stmt_iterator bsi
;
926 varray_type worklist1
, worklist2
;
929 /* Memory allocation. */
930 vars1
= BITMAP_ALLOC (NULL
);
931 vars2
= BITMAP_ALLOC (NULL
);
932 VARRAY_TREE_INIT (worklist1
, 10, "worklist");
933 VARRAY_TREE_INIT (worklist2
, 10, "worklist");
936 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
938 tree stmt
= bsi_stmt (bsi
);
940 /* If stmt is of the form
942 then make x candidate. */
943 if (cast_conversion_assignment_p (stmt
))
945 tree lhs
= TREE_OPERAND (stmt
, 0);
946 tree rhs
= TREE_OPERAND (stmt
, 1);
947 tree rhs_inner
= TREE_OPERAND (rhs
, 0);
948 tree rhs_type
= TREE_TYPE (rhs
);
949 tree rhs_inner_type
= TREE_TYPE (rhs_inner
);
951 if ((TYPE_PRECISION (rhs_inner_type
) > TYPE_PRECISION (rhs_type
))
952 && (TYPE_UNSIGNED (rhs_inner_type
) ==
953 TYPE_UNSIGNED (rhs_type
)))
955 bitmap_set_bit (vars1
, SSA_NAME_VERSION (lhs
));
956 VARRAY_PUSH_TREE (worklist1
, stmt
);
959 if ((TYPE_PRECISION (rhs_inner_type
) <=
960 TYPE_PRECISION (rhs_type
))
961 && (TYPE_UNSIGNED (rhs_inner_type
) ==
962 TYPE_UNSIGNED (rhs_type
)))
964 bitmap_set_bit (vars2
, SSA_NAME_VERSION (lhs
));
965 VARRAY_PUSH_TREE (worklist2
, stmt
);
971 /* Try to eliminate casts for first set of candidates. */
972 while (VARRAY_ACTIVE_SIZE (worklist1
) > 0)
974 tree stmt
= VARRAY_TOP_TREE (worklist1
);
975 VARRAY_POP (worklist1
);
977 if (replacable_cast_pattern (stmt
))
979 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
981 fprintf (dump_file
,"File name = %s\n", __FILE__
);
982 fprintf (dump_file
,"Input name = %s\n", main_input_filename
);
987 /* Now compute immidiate uses for second set of candidates. */
988 while (VARRAY_ACTIVE_SIZE (worklist2
) > 0)
990 tree stmt
= VARRAY_TOP_TREE (worklist2
);
991 VARRAY_POP (worklist2
);
993 if (all_uses_are_replacable (stmt
, false /* Do not replace */))
995 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
997 fprintf (dump_file
,"File name = %s\n", __FILE__
);
998 fprintf (dump_file
,"Input name = %s\n", main_input_filename
);
1000 all_uses_are_replacable (stmt
, true /* Replace */);
1004 BITMAP_FREE (vars1
);
1005 BITMAP_FREE (vars2
);
1008 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
1010 Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME.
1011 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
1012 node or for recovery of array indexing from pointer arithmetic.
1013 Returns true, if all uses have been propagated into. */
1016 forward_propagate_addr_expr (tree stmt
)
1018 int stmt_loop_depth
= bb_for_stmt (stmt
)->loop_depth
;
1019 tree name
= TREE_OPERAND (stmt
, 0);
1020 use_operand_p imm_use
;
1021 imm_use_iterator iter
;
1024 FOR_EACH_IMM_USE_SAFE (imm_use
, iter
, name
)
1026 tree use_stmt
= USE_STMT (imm_use
);
1028 /* If the use is not in a simple assignment statement, then
1029 there is nothing we can do. */
1030 if (TREE_CODE (use_stmt
) != MODIFY_EXPR
)
1036 /* If the use is in a deeper loop nest, then we do not want
1037 to propagate the ADDR_EXPR into the loop as that is likely
1038 adding expression evaluations into the loop. */
1039 if (bb_for_stmt (use_stmt
)->loop_depth
> stmt_loop_depth
)
1045 all
= forward_propagate_addr_expr_1 (stmt
, use_stmt
) && all
;
1051 /* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y.
1052 If so, we can change STMT into lhs = y which can later be copy
1053 propagated. Similarly for negation.
1055 This could trivially be formulated as a forward propagation
1056 to immediate uses. However, we already had an implementation
1057 from DOM which used backward propagation via the use-def links.
1059 It turns out that backward propagation is actually faster as
1060 there's less work to do for each NOT/NEG expression we find.
1061 Backwards propagation needs to look at the statement in a single
1062 backlink. Forward propagation needs to look at potentially more
1063 than one forward link. */
1066 simplify_not_neg_expr (tree stmt
)
1068 tree rhs
= TREE_OPERAND (stmt
, 1);
1069 tree rhs_def_stmt
= SSA_NAME_DEF_STMT (TREE_OPERAND (rhs
, 0));
1071 /* See if the RHS_DEF_STMT has the same form as our statement. */
1072 if (TREE_CODE (rhs_def_stmt
) == MODIFY_EXPR
1073 && TREE_CODE (TREE_OPERAND (rhs_def_stmt
, 1)) == TREE_CODE (rhs
))
1075 tree rhs_def_operand
= TREE_OPERAND (TREE_OPERAND (rhs_def_stmt
, 1), 0);
1077 /* Verify that RHS_DEF_OPERAND is a suitable SSA_NAME. */
1078 if (TREE_CODE (rhs_def_operand
) == SSA_NAME
1079 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand
))
1081 TREE_OPERAND (stmt
, 1) = rhs_def_operand
;
1087 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
1088 the condition which we may be able to optimize better. */
1091 simplify_switch_expr (tree stmt
)
1093 tree cond
= SWITCH_COND (stmt
);
1096 /* The optimization that we really care about is removing unnecessary
1097 casts. That will let us do much better in propagating the inferred
1098 constant at the switch target. */
1099 if (TREE_CODE (cond
) == SSA_NAME
)
1101 def
= SSA_NAME_DEF_STMT (cond
);
1102 if (TREE_CODE (def
) == MODIFY_EXPR
)
1104 def
= TREE_OPERAND (def
, 1);
1105 if (TREE_CODE (def
) == NOP_EXPR
)
1110 def
= TREE_OPERAND (def
, 0);
1112 #ifdef ENABLE_CHECKING
1113 /* ??? Why was Jeff testing this? We are gimple... */
1114 gcc_assert (is_gimple_val (def
));
1117 to
= TREE_TYPE (cond
);
1118 ti
= TREE_TYPE (def
);
1120 /* If we have an extension that preserves value, then we
1121 can copy the source value into the switch. */
1123 need_precision
= TYPE_PRECISION (ti
);
1125 if (TYPE_UNSIGNED (to
) && !TYPE_UNSIGNED (ti
))
1127 else if (!TYPE_UNSIGNED (to
) && TYPE_UNSIGNED (ti
))
1128 need_precision
+= 1;
1129 if (TYPE_PRECISION (to
) < need_precision
)
1134 SWITCH_COND (stmt
) = def
;
1142 /* Main entry point for the forward propagation optimizer. */
1145 tree_ssa_forward_propagate_single_use_vars (void)
1149 cfg_changed
= false;
1151 eliminate_unnecessary_casts ();
1155 block_stmt_iterator bsi
;
1157 /* Note we update BSI within the loop as necessary. */
1158 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); )
1160 tree stmt
= bsi_stmt (bsi
);
1162 /* If this statement sets an SSA_NAME to an address,
1163 try to propagate the address into the uses of the SSA_NAME. */
1164 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
1166 tree lhs
= TREE_OPERAND (stmt
, 0);
1167 tree rhs
= TREE_OPERAND (stmt
, 1);
1169 if (TREE_CODE (lhs
) != SSA_NAME
)
1174 /* Try to transform &A + offs into &A[offset]. */
1175 if (TREE_CODE (rhs
) == PLUS_EXPR
&& (
1176 (TREE_CODE (TREE_OPERAND (rhs
, 0)) == ADDR_EXPR
||
1177 TREE_CODE (TREE_OPERAND (rhs
, 1)) == ADDR_EXPR
)))
1180 rhs
= TREE_OPERAND (stmt
, 1);
1181 if (TREE_CODE (rhs
) == ADDR_EXPR
){
1182 recompute_tree_invariant_for_addr_expr (rhs
);
1187 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1189 if (forward_propagate_addr_expr (stmt
))
1194 else if ((TREE_CODE (rhs
) == BIT_NOT_EXPR
1195 || TREE_CODE (rhs
) == NEGATE_EXPR
)
1196 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
)
1198 simplify_not_neg_expr (stmt
);
1204 else if (TREE_CODE (stmt
) == SWITCH_EXPR
)
1206 simplify_switch_expr (stmt
);
1209 else if (TREE_CODE (stmt
) == COND_EXPR
)
1211 forward_propagate_into_cond (stmt
);
1220 cleanup_tree_cfg ();
1225 gate_forwprop (void)
1230 struct tree_opt_pass pass_forwprop
= {
1231 "forwprop", /* name */
1232 gate_forwprop
, /* gate */
1233 tree_ssa_forward_propagate_single_use_vars
, /* execute */
1236 0, /* static_pass_number */
1237 TV_TREE_FORWPROP
, /* tv_id */
1239 | PROP_alias
, /* properties_required */
1240 0, /* properties_provided */
1241 0, /* properties_destroyed */
1242 0, /* todo_flags_start */
1243 TODO_dump_func
| TODO_ggc_collect
/* todo_flags_finish */
1244 | TODO_update_ssa
| TODO_verify_ssa
,