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 variale 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. */
149 /* Given an SSA_NAME VAR, return true if and only if VAR is defined by
153 ssa_name_defined_by_comparison_p (tree var)
155 tree def = SSA_NAME_DEF_STMT (var);
157 if (TREE_CODE (def) == MODIFY_EXPR)
159 tree rhs = TREE_OPERAND (def, 1);
160 return COMPARISON_CLASS_P (rhs);
166 /* Forward propagate a single-use variable into COND once. Return a
167 new condition if successful. Return NULL_TREE otherwise. */
170 forward_propagate_into_cond_1 (tree cond, tree *test_var_p)
172 tree new_cond = NULL_TREE;
173 enum tree_code cond_code = TREE_CODE (cond);
174 tree test_var = NULL_TREE;
178 /* If the condition is not a lone variable or an equality test of an
179 SSA_NAME against an integral constant, then we do not have an
182 Note these conditions also ensure the COND_EXPR has no
183 virtual operands or other side effects. */
184 if (cond_code != SSA_NAME
185 && !((cond_code == EQ_EXPR || cond_code == NE_EXPR)
186 && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
187 && CONSTANT_CLASS_P (TREE_OPERAND (cond, 1))
188 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))))
191 /* Extract the single variable used in the test into TEST_VAR. */
192 if (cond_code == SSA_NAME)
195 test_var = TREE_OPERAND (cond, 0);
197 /* Now get the defining statement for TEST_VAR. Skip this case if
198 it's not defined by some MODIFY_EXPR. */
199 def = SSA_NAME_DEF_STMT (test_var);
200 if (TREE_CODE (def) != MODIFY_EXPR)
203 def_rhs = TREE_OPERAND (def, 1);
205 /* If TEST_VAR is set by adding or subtracting a constant
206 from an SSA_NAME, then it is interesting to us as we
207 can adjust the constant in the conditional and thus
208 eliminate the arithmetic operation. */
209 if (TREE_CODE (def_rhs) == PLUS_EXPR
210 || TREE_CODE (def_rhs) == MINUS_EXPR)
212 tree op0 = TREE_OPERAND (def_rhs, 0);
213 tree op1 = TREE_OPERAND (def_rhs, 1);
215 /* The first operand must be an SSA_NAME and the second
216 operand must be a constant. */
217 if (TREE_CODE (op0) != SSA_NAME
218 || !CONSTANT_CLASS_P (op1)
219 || !INTEGRAL_TYPE_P (TREE_TYPE (op1)))
222 /* Don't propagate if the first operand occurs in
224 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
227 if (has_single_use (test_var))
229 enum tree_code new_code;
232 /* If the variable was defined via X + C, then we must
233 subtract C from the constant in the conditional.
234 Otherwise we add C to the constant in the
235 conditional. The result must fold into a valid
236 gimple operand to be optimizable. */
237 new_code = (TREE_CODE (def_rhs) == PLUS_EXPR
238 ? MINUS_EXPR : PLUS_EXPR);
239 t = int_const_binop (new_code, TREE_OPERAND (cond, 1), op1, 0);
240 if (!is_gimple_val (t))
243 new_cond = build (cond_code, boolean_type_node, op0, t);
247 /* These cases require comparisons of a naked SSA_NAME or
248 comparison of an SSA_NAME against zero or one. */
249 else if (TREE_CODE (cond) == SSA_NAME
250 || integer_zerop (TREE_OPERAND (cond, 1))
251 || integer_onep (TREE_OPERAND (cond, 1)))
253 /* If TEST_VAR is set from a relational operation
254 between two SSA_NAMEs or a combination of an SSA_NAME
255 and a constant, then it is interesting. */
256 if (COMPARISON_CLASS_P (def_rhs))
258 tree op0 = TREE_OPERAND (def_rhs, 0);
259 tree op1 = TREE_OPERAND (def_rhs, 1);
261 /* Both operands of DEF_RHS must be SSA_NAMEs or
263 if ((TREE_CODE (op0) != SSA_NAME
264 && !is_gimple_min_invariant (op0))
265 || (TREE_CODE (op1) != SSA_NAME
266 && !is_gimple_min_invariant (op1)))
269 /* Don't propagate if the first operand occurs in
271 if (TREE_CODE (op0) == SSA_NAME
272 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
275 /* Don't propagate if the second operand occurs in
277 if (TREE_CODE (op1) == SSA_NAME
278 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1))
281 if (has_single_use (test_var))
283 /* TEST_VAR was set from a relational operator. */
284 new_cond = build (TREE_CODE (def_rhs),
285 boolean_type_node, op0, op1);
287 /* Invert the conditional if necessary. */
288 if ((cond_code == EQ_EXPR
289 && integer_zerop (TREE_OPERAND (cond, 1)))
290 || (cond_code == NE_EXPR
291 && integer_onep (TREE_OPERAND (cond, 1))))
293 new_cond = invert_truthvalue (new_cond);
295 /* If we did not get a simple relational
296 expression or bare SSA_NAME, then we can
297 not optimize this case. */
298 if (!COMPARISON_CLASS_P (new_cond)
299 && TREE_CODE (new_cond) != SSA_NAME)
300 new_cond = NULL_TREE;
305 /* If TEST_VAR is set from a TRUTH_NOT_EXPR, then it
307 else if (TREE_CODE (def_rhs) == TRUTH_NOT_EXPR)
309 enum tree_code new_code;
311 def_rhs = TREE_OPERAND (def_rhs, 0);
313 /* DEF_RHS must be an SSA_NAME or constant. */
314 if (TREE_CODE (def_rhs) != SSA_NAME
315 && !is_gimple_min_invariant (def_rhs))
318 /* Don't propagate if the operand occurs in
320 if (TREE_CODE (def_rhs) == SSA_NAME
321 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_rhs))
324 if (cond_code == SSA_NAME
325 || (cond_code == NE_EXPR
326 && integer_zerop (TREE_OPERAND (cond, 1)))
327 || (cond_code == EQ_EXPR
328 && integer_onep (TREE_OPERAND (cond, 1))))
333 new_cond = build2 (new_code, boolean_type_node, def_rhs,
334 fold_convert (TREE_TYPE (def_rhs),
338 /* If TEST_VAR was set from a cast of an integer type
339 to a boolean type or a cast of a boolean to an
340 integral, then it is interesting. */
341 else if (TREE_CODE (def_rhs) == NOP_EXPR
342 || TREE_CODE (def_rhs) == CONVERT_EXPR)
347 outer_type = TREE_TYPE (def_rhs);
348 inner_type = TREE_TYPE (TREE_OPERAND (def_rhs, 0));
350 if ((TREE_CODE (outer_type) == BOOLEAN_TYPE
351 && INTEGRAL_TYPE_P (inner_type))
352 || (TREE_CODE (inner_type) == BOOLEAN_TYPE
353 && INTEGRAL_TYPE_P (outer_type)))
355 else if (INTEGRAL_TYPE_P (outer_type)
356 && INTEGRAL_TYPE_P (inner_type)
357 && TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME
358 && ssa_name_defined_by_comparison_p (TREE_OPERAND (def_rhs,
364 /* Don't propagate if the operand occurs in
366 if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME
367 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND
371 if (has_single_use (test_var))
373 enum tree_code new_code;
376 if (cond_code == SSA_NAME
377 || (cond_code == NE_EXPR
378 && integer_zerop (TREE_OPERAND (cond, 1)))
379 || (cond_code == EQ_EXPR
380 && integer_onep (TREE_OPERAND (cond, 1))))
385 new_arg = TREE_OPERAND (def_rhs, 0);
386 new_cond = build2 (new_code, boolean_type_node, new_arg,
387 fold_convert (TREE_TYPE (new_arg),
393 *test_var_p = test_var;
397 /* Forward propagate a single-use variable into COND_EXPR as many
398 times as possible. */
401 forward_propagate_into_cond (tree cond_expr)
403 gcc_assert (TREE_CODE (cond_expr) == COND_EXPR);
407 tree test_var = NULL_TREE;
408 tree cond = COND_EXPR_COND (cond_expr);
409 tree new_cond = forward_propagate_into_cond_1 (cond, &test_var);
411 /* Return if unsuccessful. */
412 if (new_cond == NULL_TREE)
416 if (dump_file && (dump_flags & TDF_DETAILS))
418 fprintf (dump_file, " Replaced '");
419 print_generic_expr (dump_file, cond, dump_flags);
420 fprintf (dump_file, "' with '");
421 print_generic_expr (dump_file, new_cond, dump_flags);
422 fprintf (dump_file, "'\n");
425 COND_EXPR_COND (cond_expr) = new_cond;
426 update_stmt (cond_expr);
428 if (has_zero_uses (test_var))
430 tree def = SSA_NAME_DEF_STMT (test_var);
431 block_stmt_iterator bsi = bsi_for_stmt (def);
437 /* STMT defines LHS which is contains the address of the 0th element
438 in an array. USE_STMT uses LHS to compute the address of an
439 arbitrary element within the array. The (variable) byte offset
440 of the element is contained in OFFSET.
442 We walk back through the use-def chains of OFFSET to verify that
443 it is indeed computing the offset of an element within the array
444 and extract the index corresponding to the given byte offset.
446 We then try to fold the entire address expression into a form
449 If we are successful, we replace the right hand side of USE_STMT
450 with the new address computation. */
453 forward_propagate_addr_into_variable_array_index (tree offset, tree lhs,
454 tree stmt, tree use_stmt)
458 /* The offset must be defined by a simple MODIFY_EXPR statement. */
459 if (TREE_CODE (offset) != MODIFY_EXPR)
462 /* The RHS of the statement which defines OFFSET must be a gimple
463 cast of another SSA_NAME. */
464 offset = TREE_OPERAND (offset, 1);
465 if (!is_gimple_cast (offset))
468 offset = TREE_OPERAND (offset, 0);
469 if (TREE_CODE (offset) != SSA_NAME)
472 /* Get the defining statement of the offset before type
474 offset = SSA_NAME_DEF_STMT (offset);
476 /* The statement which defines OFFSET before type conversion
477 must be a simple MODIFY_EXPR. */
478 if (TREE_CODE (offset) != MODIFY_EXPR)
481 /* The RHS of the statement which defines OFFSET must be a
482 multiplication of an object by the size of the array elements.
483 This implicitly verifies that the size of the array elements
485 offset = TREE_OPERAND (offset, 1);
486 if (TREE_CODE (offset) != MULT_EXPR
487 || TREE_CODE (TREE_OPERAND (offset, 1)) != INTEGER_CST
488 || !simple_cst_equal (TREE_OPERAND (offset, 1),
489 TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (lhs)))))
492 /* The first operand to the MULT_EXPR is the desired index. */
493 index = TREE_OPERAND (offset, 0);
495 /* Replace the pointer addition with array indexing. */
496 TREE_OPERAND (use_stmt, 1) = unshare_expr (TREE_OPERAND (stmt, 1));
497 TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (use_stmt, 1), 0), 1) = index;
499 /* That should have created gimple, so there is no need to
500 record information to undo the propagation. */
501 fold_stmt (bsi_stmt_ptr (bsi_for_stmt (use_stmt)));
502 mark_new_vars_to_rename (use_stmt);
503 update_stmt (use_stmt);
507 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
509 Try to forward propagate the ADDR_EXPR into the uses of the SSA_NAME.
510 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
511 node or for recovery of array indexing from pointer arithmetic. */
514 forward_propagate_addr_expr (tree stmt)
516 int stmt_loop_depth = bb_for_stmt (stmt)->loop_depth;
517 tree name = TREE_OPERAND (stmt, 0);
518 use_operand_p imm_use;
519 tree use_stmt, lhs, rhs, array_ref;
521 /* We require that the SSA_NAME holding the result of the ADDR_EXPR
522 be used only once. That may be overly conservative in that we
523 could propagate into multiple uses. However, that would effectively
524 be un-cseing the ADDR_EXPR, which is probably not what we want. */
525 single_imm_use (name, &imm_use, &use_stmt);
529 /* If the use is not in a simple assignment statement, then
530 there is nothing we can do. */
531 if (TREE_CODE (use_stmt) != MODIFY_EXPR)
534 /* If the use is in a deeper loop nest, then we do not want
535 to propagate the ADDR_EXPR into the loop as that is likely
536 adding expression evaluations into the loop. */
537 if (bb_for_stmt (use_stmt)->loop_depth > stmt_loop_depth)
540 /* Strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS. */
541 lhs = TREE_OPERAND (use_stmt, 0);
542 while (TREE_CODE (lhs) == COMPONENT_REF || TREE_CODE (lhs) == ARRAY_REF)
543 lhs = TREE_OPERAND (lhs, 0);
545 /* Now see if the LHS node is an INDIRECT_REF using NAME. If so,
546 propagate the ADDR_EXPR into the use of NAME and fold the result. */
547 if (TREE_CODE (lhs) == INDIRECT_REF && TREE_OPERAND (lhs, 0) == name)
549 /* This should always succeed in creating gimple, so there is
550 no need to save enough state to undo this propagation. */
551 TREE_OPERAND (lhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1));
552 fold_stmt (bsi_stmt_ptr (bsi_for_stmt (use_stmt)));
553 mark_new_vars_to_rename (use_stmt);
554 update_stmt (use_stmt);
558 /* Trivial case. The use statement could be a trivial copy. We
559 go ahead and handle that case here since it's trivial and
560 removes the need to run copy-prop before this pass to get
561 the best results. Also note that by handling this case here
562 we can catch some cascading effects, ie the single use is
563 in a copy, and the copy is used later by a single INDIRECT_REF
565 if (TREE_CODE (lhs) == SSA_NAME && TREE_OPERAND (use_stmt, 1) == name)
567 TREE_OPERAND (use_stmt, 1) = unshare_expr (TREE_OPERAND (stmt, 1));
568 mark_new_vars_to_rename (use_stmt);
569 update_stmt (use_stmt);
573 /* Strip away any outer COMPONENT_REF/ARRAY_REF nodes from the RHS. */
574 rhs = TREE_OPERAND (use_stmt, 1);
575 while (TREE_CODE (rhs) == COMPONENT_REF || TREE_CODE (rhs) == ARRAY_REF)
576 rhs = TREE_OPERAND (rhs, 0);
578 /* Now see if the RHS node is an INDIRECT_REF using NAME. If so,
579 propagate the ADDR_EXPR into the use of NAME and fold the result. */
580 if (TREE_CODE (rhs) == INDIRECT_REF && TREE_OPERAND (rhs, 0) == name)
582 /* This should always succeed in creating gimple, so there is
583 no need to save enough state to undo this propagation. */
584 TREE_OPERAND (rhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1));
585 fold_stmt (bsi_stmt_ptr (bsi_for_stmt (use_stmt)));
586 mark_new_vars_to_rename (use_stmt);
587 update_stmt (use_stmt);
591 /* The remaining cases are all for turning pointer arithmetic into
592 array indexing. They only apply when we have the address of
593 element zero in an array. If that is not the case then there
595 array_ref = TREE_OPERAND (TREE_OPERAND (stmt, 1), 0);
596 if (TREE_CODE (array_ref) != ARRAY_REF
597 || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE
598 || !integer_zerop (TREE_OPERAND (array_ref, 1)))
601 /* If the use of the ADDR_EXPR must be a PLUS_EXPR, or else there
603 if (TREE_CODE (rhs) != PLUS_EXPR)
606 /* Try to optimize &x[0] + C where C is a multiple of the size
607 of the elements in X into &x[C/element size]. */
608 if (TREE_OPERAND (rhs, 0) == name
609 && TREE_CODE (TREE_OPERAND (rhs, 1)) == INTEGER_CST)
611 tree orig = unshare_expr (rhs);
612 TREE_OPERAND (rhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1));
614 /* If folding succeeds, then we have just exposed new variables
615 in USE_STMT which will need to be renamed. If folding fails,
616 then we need to put everything back the way it was. */
617 if (fold_stmt (bsi_stmt_ptr (bsi_for_stmt (use_stmt))))
619 mark_new_vars_to_rename (use_stmt);
620 update_stmt (use_stmt);
625 TREE_OPERAND (use_stmt, 1) = orig;
626 update_stmt (use_stmt);
631 /* Try to optimize &x[0] + OFFSET where OFFSET is defined by
632 converting a multiplication of an index by the size of the
633 array elements, then the result is converted into the proper
634 type for the arithmetic. */
635 if (TREE_OPERAND (rhs, 0) == name
636 && TREE_CODE (TREE_OPERAND (rhs, 1)) == SSA_NAME
637 /* Avoid problems with IVopts creating PLUS_EXPRs with a
638 different type than their operands. */
639 && lang_hooks.types_compatible_p (TREE_TYPE (name), TREE_TYPE (rhs)))
641 tree offset_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 1));
642 return forward_propagate_addr_into_variable_array_index (offset_stmt, lhs,
646 /* Same as the previous case, except the operands of the PLUS_EXPR
648 if (TREE_OPERAND (rhs, 1) == name
649 && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
650 /* Avoid problems with IVopts creating PLUS_EXPRs with a
651 different type than their operands. */
652 && lang_hooks.types_compatible_p (TREE_TYPE (name), TREE_TYPE (rhs)))
654 tree offset_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
655 return forward_propagate_addr_into_variable_array_index (offset_stmt, lhs,
661 /* Main entry point for the forward propagation optimizer. */
664 tree_ssa_forward_propagate_single_use_vars (void)
670 block_stmt_iterator bsi;
672 /* Note we update BSI within the loop as necessary. */
673 for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
675 tree stmt = bsi_stmt (bsi);
677 /* If this statement sets an SSA_NAME to an address,
678 try to propagate the address into the uses of the SSA_NAME. */
679 if (TREE_CODE (stmt) == MODIFY_EXPR
680 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ADDR_EXPR
681 && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME)
683 if (forward_propagate_addr_expr (stmt))
688 else if (TREE_CODE (stmt) == COND_EXPR)
690 forward_propagate_into_cond (stmt);
706 struct tree_opt_pass pass_forwprop = {
707 "forwprop", /* name */
708 gate_forwprop, /* gate */
709 tree_ssa_forward_propagate_single_use_vars, /* execute */
712 0, /* static_pass_number */
713 TV_TREE_FORWPROP, /* tv_id */
715 | PROP_alias, /* properties_required */
716 0, /* properties_provided */
717 0, /* properties_destroyed */
718 0, /* todo_flags_start */
719 TODO_dump_func | TODO_ggc_collect /* todo_flags_finish */
720 | TODO_update_ssa | TODO_verify_ssa,