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, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
23 #include "coretypes.h"
30 #include "basic-block.h"
32 #include "diagnostic.h"
33 #include "tree-flow.h"
34 #include "tree-pass.h"
35 #include "tree-dump.h"
36 #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.
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
129 ptr2 = ptr + <constant>;
133 ptr2 = &x[constant/elementsize];
138 offset = index * element_size;
139 offset_p = (pointer) offset;
140 ptr2 = ptr + offset_p
142 Will get turned into:
147 This will (of course) be extended as other needs arise. */
150 /* Set to true if we delete EH edges during the optimization. */
151 static bool cfg_changed;
154 /* Given an SSA_NAME VAR, return true if and only if VAR is defined by
158 ssa_name_defined_by_comparison_p (tree var)
160 tree def = SSA_NAME_DEF_STMT (var);
162 if (TREE_CODE (def) == MODIFY_EXPR)
164 tree rhs = TREE_OPERAND (def, 1);
165 return COMPARISON_CLASS_P (rhs);
171 /* Forward propagate a single-use variable into COND once. Return a
172 new condition if successful. Return NULL_TREE otherwise. */
175 forward_propagate_into_cond_1 (tree cond, tree *test_var_p)
177 tree new_cond = NULL_TREE;
178 enum tree_code cond_code = TREE_CODE (cond);
179 tree test_var = NULL_TREE;
183 /* If the condition is not a lone variable or an equality test of an
184 SSA_NAME against an integral constant, then we do not have an
187 Note these conditions also ensure the COND_EXPR has no
188 virtual operands or other side effects. */
189 if (cond_code != SSA_NAME
190 && !((cond_code == EQ_EXPR || cond_code == NE_EXPR)
191 && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
192 && CONSTANT_CLASS_P (TREE_OPERAND (cond, 1))
193 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))))
196 /* Extract the single variable used in the test into TEST_VAR. */
197 if (cond_code == SSA_NAME)
200 test_var = TREE_OPERAND (cond, 0);
202 /* Now get the defining statement for TEST_VAR. Skip this case if
203 it's not defined by some MODIFY_EXPR. */
204 def = SSA_NAME_DEF_STMT (test_var);
205 if (TREE_CODE (def) != MODIFY_EXPR)
208 def_rhs = TREE_OPERAND (def, 1);
210 /* If TEST_VAR is set by adding or subtracting a constant
211 from an SSA_NAME, then it is interesting to us as we
212 can adjust the constant in the conditional and thus
213 eliminate the arithmetic operation. */
214 if (TREE_CODE (def_rhs) == PLUS_EXPR
215 || TREE_CODE (def_rhs) == MINUS_EXPR)
217 tree op0 = TREE_OPERAND (def_rhs, 0);
218 tree op1 = TREE_OPERAND (def_rhs, 1);
220 /* The first operand must be an SSA_NAME and the second
221 operand must be a constant. */
222 if (TREE_CODE (op0) != SSA_NAME
223 || !CONSTANT_CLASS_P (op1)
224 || !INTEGRAL_TYPE_P (TREE_TYPE (op1)))
227 /* Don't propagate if the first operand occurs in
229 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
232 if (has_single_use (test_var))
234 enum tree_code new_code;
237 /* If the variable was defined via X + C, then we must
238 subtract C from the constant in the conditional.
239 Otherwise we add C to the constant in the
240 conditional. The result must fold into a valid
241 gimple operand to be optimizable. */
242 new_code = (TREE_CODE (def_rhs) == PLUS_EXPR
243 ? MINUS_EXPR : PLUS_EXPR);
244 t = int_const_binop (new_code, TREE_OPERAND (cond, 1), op1, 0);
245 if (!is_gimple_val (t))
248 new_cond = build (cond_code, boolean_type_node, op0, t);
252 /* These cases require comparisons of a naked SSA_NAME or
253 comparison of an SSA_NAME against zero or one. */
254 else if (TREE_CODE (cond) == SSA_NAME
255 || integer_zerop (TREE_OPERAND (cond, 1))
256 || integer_onep (TREE_OPERAND (cond, 1)))
258 /* If TEST_VAR is set from a relational operation
259 between two SSA_NAMEs or a combination of an SSA_NAME
260 and a constant, then it is interesting. */
261 if (COMPARISON_CLASS_P (def_rhs))
263 tree op0 = TREE_OPERAND (def_rhs, 0);
264 tree op1 = TREE_OPERAND (def_rhs, 1);
266 /* Both operands of DEF_RHS must be SSA_NAMEs or
268 if ((TREE_CODE (op0) != SSA_NAME
269 && !is_gimple_min_invariant (op0))
270 || (TREE_CODE (op1) != SSA_NAME
271 && !is_gimple_min_invariant (op1)))
274 /* Don't propagate if the first operand occurs in
276 if (TREE_CODE (op0) == SSA_NAME
277 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
280 /* Don't propagate if the second operand occurs in
282 if (TREE_CODE (op1) == SSA_NAME
283 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1))
286 if (has_single_use (test_var))
288 /* TEST_VAR was set from a relational operator. */
289 new_cond = build (TREE_CODE (def_rhs),
290 boolean_type_node, op0, op1);
292 /* Invert the conditional if necessary. */
293 if ((cond_code == EQ_EXPR
294 && integer_zerop (TREE_OPERAND (cond, 1)))
295 || (cond_code == NE_EXPR
296 && integer_onep (TREE_OPERAND (cond, 1))))
298 new_cond = invert_truthvalue (new_cond);
300 /* If we did not get a simple relational
301 expression or bare SSA_NAME, then we can
302 not optimize this case. */
303 if (!COMPARISON_CLASS_P (new_cond)
304 && TREE_CODE (new_cond) != SSA_NAME)
305 new_cond = NULL_TREE;
310 /* If TEST_VAR is set from a TRUTH_NOT_EXPR, then it
312 else if (TREE_CODE (def_rhs) == TRUTH_NOT_EXPR)
314 enum tree_code new_code;
316 def_rhs = TREE_OPERAND (def_rhs, 0);
318 /* DEF_RHS must be an SSA_NAME or constant. */
319 if (TREE_CODE (def_rhs) != SSA_NAME
320 && !is_gimple_min_invariant (def_rhs))
323 /* Don't propagate if the operand occurs in
325 if (TREE_CODE (def_rhs) == SSA_NAME
326 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_rhs))
329 if (cond_code == SSA_NAME
330 || (cond_code == NE_EXPR
331 && integer_zerop (TREE_OPERAND (cond, 1)))
332 || (cond_code == EQ_EXPR
333 && integer_onep (TREE_OPERAND (cond, 1))))
338 new_cond = build2 (new_code, boolean_type_node, def_rhs,
339 fold_convert (TREE_TYPE (def_rhs),
343 /* If TEST_VAR was set from a cast of an integer type
344 to a boolean type or a cast of a boolean to an
345 integral, then it is interesting. */
346 else if (TREE_CODE (def_rhs) == NOP_EXPR
347 || TREE_CODE (def_rhs) == CONVERT_EXPR)
352 outer_type = TREE_TYPE (def_rhs);
353 inner_type = TREE_TYPE (TREE_OPERAND (def_rhs, 0));
355 if ((TREE_CODE (outer_type) == BOOLEAN_TYPE
356 && INTEGRAL_TYPE_P (inner_type))
357 || (TREE_CODE (inner_type) == BOOLEAN_TYPE
358 && INTEGRAL_TYPE_P (outer_type)))
360 else if (INTEGRAL_TYPE_P (outer_type)
361 && INTEGRAL_TYPE_P (inner_type)
362 && TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME
363 && ssa_name_defined_by_comparison_p (TREE_OPERAND (def_rhs,
369 /* Don't propagate if the operand occurs in
371 if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME
372 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND
376 if (has_single_use (test_var))
378 enum tree_code new_code;
381 if (cond_code == SSA_NAME
382 || (cond_code == NE_EXPR
383 && integer_zerop (TREE_OPERAND (cond, 1)))
384 || (cond_code == EQ_EXPR
385 && integer_onep (TREE_OPERAND (cond, 1))))
390 new_arg = TREE_OPERAND (def_rhs, 0);
391 new_cond = build2 (new_code, boolean_type_node, new_arg,
392 fold_convert (TREE_TYPE (new_arg),
398 *test_var_p = test_var;
402 /* Forward propagate a single-use variable into COND_EXPR as many
403 times as possible. */
406 forward_propagate_into_cond (tree cond_expr)
408 gcc_assert (TREE_CODE (cond_expr) == COND_EXPR);
412 tree test_var = NULL_TREE;
413 tree cond = COND_EXPR_COND (cond_expr);
414 tree new_cond = forward_propagate_into_cond_1 (cond, &test_var);
416 /* Return if unsuccessful. */
417 if (new_cond == NULL_TREE)
421 if (dump_file && (dump_flags & TDF_DETAILS))
423 fprintf (dump_file, " Replaced '");
424 print_generic_expr (dump_file, cond, dump_flags);
425 fprintf (dump_file, "' with '");
426 print_generic_expr (dump_file, new_cond, dump_flags);
427 fprintf (dump_file, "'\n");
430 COND_EXPR_COND (cond_expr) = new_cond;
431 update_stmt (cond_expr);
433 if (has_zero_uses (test_var))
435 tree def = SSA_NAME_DEF_STMT (test_var);
436 block_stmt_iterator bsi = bsi_for_stmt (def);
442 /* We've just substituted an ADDR_EXPR into stmt. Update all the
443 relevant data structures to match. */
446 tidy_after_forward_propagate_addr (tree stmt)
448 mark_new_vars_to_rename (stmt);
451 /* We may have turned a trapping insn into a non-trapping insn. */
452 if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
453 && tree_purge_dead_eh_edges (bb_for_stmt (stmt)))
457 /* STMT defines LHS which is contains the address of the 0th element
458 in an array. USE_STMT uses LHS to compute the address of an
459 arbitrary element within the array. The (variable) byte offset
460 of the element is contained in OFFSET.
462 We walk back through the use-def chains of OFFSET to verify that
463 it is indeed computing the offset of an element within the array
464 and extract the index corresponding to the given byte offset.
466 We then try to fold the entire address expression into a form
469 If we are successful, we replace the right hand side of USE_STMT
470 with the new address computation. */
473 forward_propagate_addr_into_variable_array_index (tree offset, tree lhs,
474 tree stmt, tree use_stmt)
478 /* The offset must be defined by a simple MODIFY_EXPR statement. */
479 if (TREE_CODE (offset) != MODIFY_EXPR)
482 /* The RHS of the statement which defines OFFSET must be a gimple
483 cast of another SSA_NAME. */
484 offset = TREE_OPERAND (offset, 1);
485 if (!is_gimple_cast (offset))
488 offset = TREE_OPERAND (offset, 0);
489 if (TREE_CODE (offset) != SSA_NAME)
492 /* Get the defining statement of the offset before type
494 offset = SSA_NAME_DEF_STMT (offset);
496 /* The statement which defines OFFSET before type conversion
497 must be a simple MODIFY_EXPR. */
498 if (TREE_CODE (offset) != MODIFY_EXPR)
501 /* The RHS of the statement which defines OFFSET must be a
502 multiplication of an object by the size of the array elements.
503 This implicitly verifies that the size of the array elements
505 offset = TREE_OPERAND (offset, 1);
506 if (TREE_CODE (offset) != MULT_EXPR
507 || TREE_CODE (TREE_OPERAND (offset, 1)) != INTEGER_CST
508 || !simple_cst_equal (TREE_OPERAND (offset, 1),
509 TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (lhs)))))
512 /* The first operand to the MULT_EXPR is the desired index. */
513 index = TREE_OPERAND (offset, 0);
515 /* Replace the pointer addition with array indexing. */
516 TREE_OPERAND (use_stmt, 1) = unshare_expr (TREE_OPERAND (stmt, 1));
517 TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (use_stmt, 1), 0), 1) = index;
519 /* That should have created gimple, so there is no need to
520 record information to undo the propagation. */
521 fold_stmt_inplace (use_stmt);
522 tidy_after_forward_propagate_addr (use_stmt);
526 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
528 Try to forward propagate the ADDR_EXPR into the uses of the SSA_NAME.
529 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
530 node or for recovery of array indexing from pointer arithmetic. */
533 forward_propagate_addr_expr (tree stmt)
535 int stmt_loop_depth = bb_for_stmt (stmt)->loop_depth;
536 tree name = TREE_OPERAND (stmt, 0);
537 use_operand_p imm_use;
538 tree use_stmt, lhs, rhs, array_ref;
540 /* We require that the SSA_NAME holding the result of the ADDR_EXPR
541 be used only once. That may be overly conservative in that we
542 could propagate into multiple uses. However, that would effectively
543 be un-cseing the ADDR_EXPR, which is probably not what we want. */
544 single_imm_use (name, &imm_use, &use_stmt);
548 /* If the use is not in a simple assignment statement, then
549 there is nothing we can do. */
550 if (TREE_CODE (use_stmt) != MODIFY_EXPR)
553 /* If the use is in a deeper loop nest, then we do not want
554 to propagate the ADDR_EXPR into the loop as that is likely
555 adding expression evaluations into the loop. */
556 if (bb_for_stmt (use_stmt)->loop_depth > stmt_loop_depth)
559 /* Strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS. */
560 lhs = TREE_OPERAND (use_stmt, 0);
561 while (TREE_CODE (lhs) == COMPONENT_REF || TREE_CODE (lhs) == ARRAY_REF)
562 lhs = TREE_OPERAND (lhs, 0);
564 /* Now see if the LHS node is an INDIRECT_REF using NAME. If so,
565 propagate the ADDR_EXPR into the use of NAME and fold the result. */
566 if (TREE_CODE (lhs) == INDIRECT_REF && TREE_OPERAND (lhs, 0) == name)
568 /* This should always succeed in creating gimple, so there is
569 no need to save enough state to undo this propagation. */
570 TREE_OPERAND (lhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1));
571 fold_stmt_inplace (use_stmt);
572 tidy_after_forward_propagate_addr (use_stmt);
576 /* Trivial case. The use statement could be a trivial copy. We
577 go ahead and handle that case here since it's trivial and
578 removes the need to run copy-prop before this pass to get
579 the best results. Also note that by handling this case here
580 we can catch some cascading effects, ie the single use is
581 in a copy, and the copy is used later by a single INDIRECT_REF
583 if (TREE_CODE (lhs) == SSA_NAME && TREE_OPERAND (use_stmt, 1) == name)
585 TREE_OPERAND (use_stmt, 1) = unshare_expr (TREE_OPERAND (stmt, 1));
586 tidy_after_forward_propagate_addr (use_stmt);
590 /* Strip away any outer COMPONENT_REF/ARRAY_REF nodes from the RHS. */
591 rhs = TREE_OPERAND (use_stmt, 1);
592 while (TREE_CODE (rhs) == COMPONENT_REF || TREE_CODE (rhs) == ARRAY_REF)
593 rhs = TREE_OPERAND (rhs, 0);
595 /* Now see if the RHS node is an INDIRECT_REF using NAME. If so,
596 propagate the ADDR_EXPR into the use of NAME and fold the result. */
597 if (TREE_CODE (rhs) == INDIRECT_REF && TREE_OPERAND (rhs, 0) == name)
599 /* This should always succeed in creating gimple, so there is
600 no need to save enough state to undo this propagation. */
601 TREE_OPERAND (rhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1));
602 fold_stmt_inplace (use_stmt);
603 tidy_after_forward_propagate_addr (use_stmt);
607 /* The remaining cases are all for turning pointer arithmetic into
608 array indexing. They only apply when we have the address of
609 element zero in an array. If that is not the case then there
611 array_ref = TREE_OPERAND (TREE_OPERAND (stmt, 1), 0);
612 if (TREE_CODE (array_ref) != ARRAY_REF
613 || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE
614 || !integer_zerop (TREE_OPERAND (array_ref, 1)))
617 /* If the use of the ADDR_EXPR must be a PLUS_EXPR, or else there
619 if (TREE_CODE (rhs) != PLUS_EXPR)
622 /* Try to optimize &x[0] + C where C is a multiple of the size
623 of the elements in X into &x[C/element size]. */
624 if (TREE_OPERAND (rhs, 0) == name
625 && TREE_CODE (TREE_OPERAND (rhs, 1)) == INTEGER_CST)
627 tree orig = unshare_expr (rhs);
628 TREE_OPERAND (rhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1));
630 /* If folding succeeds, then we have just exposed new variables
631 in USE_STMT which will need to be renamed. If folding fails,
632 then we need to put everything back the way it was. */
633 if (fold_stmt_inplace (use_stmt))
635 tidy_after_forward_propagate_addr (use_stmt);
640 TREE_OPERAND (use_stmt, 1) = orig;
641 update_stmt (use_stmt);
646 /* Try to optimize &x[0] + OFFSET where OFFSET is defined by
647 converting a multiplication of an index by the size of the
648 array elements, then the result is converted into the proper
649 type for the arithmetic. */
650 if (TREE_OPERAND (rhs, 0) == name
651 && TREE_CODE (TREE_OPERAND (rhs, 1)) == 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, 1));
657 return forward_propagate_addr_into_variable_array_index (offset_stmt, lhs,
661 /* Same as the previous case, except the operands of the PLUS_EXPR
663 if (TREE_OPERAND (rhs, 1) == name
664 && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
665 /* Avoid problems with IVopts creating PLUS_EXPRs with a
666 different type than their operands. */
667 && lang_hooks.types_compatible_p (TREE_TYPE (name), TREE_TYPE (rhs)))
669 tree offset_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
670 return forward_propagate_addr_into_variable_array_index (offset_stmt, lhs,
676 /* Main entry point for the forward propagation optimizer. */
679 tree_ssa_forward_propagate_single_use_vars (void)
687 block_stmt_iterator bsi;
689 /* Note we update BSI within the loop as necessary. */
690 for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
692 tree stmt = bsi_stmt (bsi);
694 /* If this statement sets an SSA_NAME to an address,
695 try to propagate the address into the uses of the SSA_NAME. */
696 if (TREE_CODE (stmt) == MODIFY_EXPR
697 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ADDR_EXPR
698 && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME)
700 if (forward_propagate_addr_expr (stmt))
705 else if (TREE_CODE (stmt) == COND_EXPR)
707 forward_propagate_into_cond (stmt);
726 struct tree_opt_pass pass_forwprop = {
727 "forwprop", /* name */
728 gate_forwprop, /* gate */
729 tree_ssa_forward_propagate_single_use_vars, /* execute */
732 0, /* static_pass_number */
733 TV_TREE_FORWPROP, /* tv_id */
735 | PROP_alias, /* properties_required */
736 0, /* properties_provided */
737 0, /* properties_destroyed */
738 0, /* todo_flags_start */
739 TODO_dump_func | TODO_ggc_collect /* todo_flags_finish */
740 | TODO_update_ssa | TODO_verify_ssa,