1 /* Forward propagation of 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"
37 /* This pass performs simple forward propagation of single use variables
38 from their definition site into their single use site.
40 Right now we only bother forward propagating into COND_EXPRs since those
41 are relatively common cases where forward propagation creates valid
42 gimple code without the expression needing to fold. i.e.
46 if (x) goto ... else goto ...
48 Will be transformed into:
51 if (a COND b) goto ... else goto ...
53 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
55 Or (assuming c1 and c2 are constants):
59 if (x EQ/NEQ c2) goto ... else goto ...
61 Will be transformed into:
64 if (a EQ/NEQ (c2 - c1)) goto ... else goto ...
66 Similarly for x = a - c1.
72 if (x) goto ... else goto ...
74 Will be transformed into:
77 if (a == 0) goto ... else goto ...
79 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
80 For these cases, we propagate A into all, possibly more than one,
81 COND_EXPRs that use X.
87 if (x) goto ... else goto ...
89 Will be transformed into:
92 if (a != 0) goto ... else goto ...
94 (Assuming a is an integral type and x is a boolean or x is an
95 integral and a is a boolean.)
97 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
98 For these cases, we propagate A into all, possibly more than one,
99 COND_EXPRs that use X.
101 In addition to eliminating the variable and the statement which assigns
102 a value to the variable, we may be able to later thread the jump without
103 adding insane complexity in the dominator optimizer.
105 Also note these transformations can cascade. We handle this by having
106 a worklist of COND_EXPR statements to examine. As we make a change to
107 a statement, we put it back on the worklist to examine on the next
108 iteration of the main loop.
110 This will (of course) be extended as other needs arise. */
112 /* Given an SSA_NAME VAR, return true if and only if VAR is defined by
116 ssa_name_defined_by_comparison_p (tree var)
118 tree def = SSA_NAME_DEF_STMT (var);
120 if (TREE_CODE (def) == MODIFY_EXPR)
122 tree rhs = TREE_OPERAND (def, 1);
123 return COMPARISON_CLASS_P (rhs);
129 /* Forward propagate a single-use variable into COND once. Return a
130 new condition if successful. Return NULL_TREE otherwise. */
133 forward_propagate_into_cond_1 (tree cond, tree *test_var_p)
135 tree new_cond = NULL_TREE;
136 enum tree_code cond_code = TREE_CODE (cond);
137 tree test_var = NULL_TREE;
141 /* If the condition is not a lone variable or an equality test of an
142 SSA_NAME against an integral constant, then we do not have an
145 Note these conditions also ensure the COND_EXPR has no
146 virtual operands or other side effects. */
147 if (cond_code != SSA_NAME
148 && !((cond_code == EQ_EXPR || cond_code == NE_EXPR)
149 && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
150 && CONSTANT_CLASS_P (TREE_OPERAND (cond, 1))
151 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))))
154 /* Extract the single variable used in the test into TEST_VAR. */
155 if (cond_code == SSA_NAME)
158 test_var = TREE_OPERAND (cond, 0);
160 /* Now get the defining statement for TEST_VAR. Skip this case if
161 it's not defined by some MODIFY_EXPR. */
162 def = SSA_NAME_DEF_STMT (test_var);
163 if (TREE_CODE (def) != MODIFY_EXPR)
166 def_rhs = TREE_OPERAND (def, 1);
168 /* If TEST_VAR is set by adding or subtracting a constant
169 from an SSA_NAME, then it is interesting to us as we
170 can adjust the constant in the conditional and thus
171 eliminate the arithmetic operation. */
172 if (TREE_CODE (def_rhs) == PLUS_EXPR
173 || TREE_CODE (def_rhs) == MINUS_EXPR)
175 tree op0 = TREE_OPERAND (def_rhs, 0);
176 tree op1 = TREE_OPERAND (def_rhs, 1);
178 /* The first operand must be an SSA_NAME and the second
179 operand must be a constant. */
180 if (TREE_CODE (op0) != SSA_NAME
181 || !CONSTANT_CLASS_P (op1)
182 || !INTEGRAL_TYPE_P (TREE_TYPE (op1)))
185 /* Don't propagate if the first operand occurs in
187 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
190 if (has_single_use (test_var))
192 tree op0 = TREE_OPERAND (def_rhs, 0);
193 tree op1 = TREE_OPERAND (def_rhs, 1);
194 enum tree_code new_code;
197 /* If the variable was defined via X + C, then we must
198 subtract C from the constant in the conditional.
199 Otherwise we add C to the constant in the
200 conditional. The result must fold into a valid
201 gimple operand to be optimizable. */
202 new_code = (TREE_CODE (def_rhs) == PLUS_EXPR
203 ? MINUS_EXPR : PLUS_EXPR);
204 t = int_const_binop (new_code, TREE_OPERAND (cond, 1), op1, 0);
205 if (!is_gimple_val (t))
208 new_cond = build (cond_code, boolean_type_node, op0, t);
212 /* These cases require comparisons of a naked SSA_NAME or
213 comparison of an SSA_NAME against zero or one. */
214 else if (TREE_CODE (cond) == SSA_NAME
215 || integer_zerop (TREE_OPERAND (cond, 1))
216 || integer_onep (TREE_OPERAND (cond, 1)))
218 /* If TEST_VAR is set from a relational operation
219 between two SSA_NAMEs or a combination of an SSA_NAME
220 and a constant, then it is interesting. */
221 if (COMPARISON_CLASS_P (def_rhs))
223 tree op0 = TREE_OPERAND (def_rhs, 0);
224 tree op1 = TREE_OPERAND (def_rhs, 1);
226 /* Both operands of DEF_RHS must be SSA_NAMEs or
228 if ((TREE_CODE (op0) != SSA_NAME
229 && !is_gimple_min_invariant (op0))
230 || (TREE_CODE (op1) != SSA_NAME
231 && !is_gimple_min_invariant (op1)))
234 /* Don't propagate if the first operand occurs in
236 if (TREE_CODE (op0) == SSA_NAME
237 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
240 /* Don't propagate if the second operand occurs in
242 if (TREE_CODE (op1) == SSA_NAME
243 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1))
246 if (has_single_use (test_var))
248 /* TEST_VAR was set from a relational operator. */
249 tree op0 = TREE_OPERAND (def_rhs, 0);
250 tree op1 = TREE_OPERAND (def_rhs, 1);
252 new_cond = build (TREE_CODE (def_rhs),
253 boolean_type_node, op0, op1);
255 /* Invert the conditional if necessary. */
256 if ((cond_code == EQ_EXPR
257 && integer_zerop (TREE_OPERAND (cond, 1)))
258 || (cond_code == NE_EXPR
259 && integer_onep (TREE_OPERAND (cond, 1))))
261 new_cond = invert_truthvalue (new_cond);
263 /* If we did not get a simple relational
264 expression or bare SSA_NAME, then we can
265 not optimize this case. */
266 if (!COMPARISON_CLASS_P (new_cond)
267 && TREE_CODE (new_cond) != SSA_NAME)
268 new_cond = NULL_TREE;
273 /* If TEST_VAR is set from a TRUTH_NOT_EXPR, then it
275 else if (TREE_CODE (def_rhs) == TRUTH_NOT_EXPR)
277 enum tree_code new_code;
279 def_rhs = TREE_OPERAND (def_rhs, 0);
281 /* DEF_RHS must be an SSA_NAME or constant. */
282 if (TREE_CODE (def_rhs) != SSA_NAME
283 && !is_gimple_min_invariant (def_rhs))
286 /* Don't propagate if the operand occurs in
288 if (TREE_CODE (def_rhs) == SSA_NAME
289 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_rhs))
292 if (cond_code == SSA_NAME
293 || (cond_code == NE_EXPR
294 && integer_zerop (TREE_OPERAND (cond, 1)))
295 || (cond_code == EQ_EXPR
296 && integer_onep (TREE_OPERAND (cond, 1))))
301 new_cond = build2 (new_code, boolean_type_node, def_rhs,
302 fold_convert (TREE_TYPE (def_rhs),
306 /* If TEST_VAR was set from a cast of an integer type
307 to a boolean type or a cast of a boolean to an
308 integral, then it is interesting. */
309 else if (TREE_CODE (def_rhs) == NOP_EXPR
310 || TREE_CODE (def_rhs) == CONVERT_EXPR)
315 outer_type = TREE_TYPE (def_rhs);
316 inner_type = TREE_TYPE (TREE_OPERAND (def_rhs, 0));
318 if ((TREE_CODE (outer_type) == BOOLEAN_TYPE
319 && INTEGRAL_TYPE_P (inner_type))
320 || (TREE_CODE (inner_type) == BOOLEAN_TYPE
321 && INTEGRAL_TYPE_P (outer_type)))
323 else if (INTEGRAL_TYPE_P (outer_type)
324 && INTEGRAL_TYPE_P (inner_type)
325 && TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME
326 && ssa_name_defined_by_comparison_p (TREE_OPERAND (def_rhs,
332 /* Don't propagate if the operand occurs in
334 if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME
335 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND
339 if (has_single_use (test_var))
341 enum tree_code new_code;
344 if (cond_code == SSA_NAME
345 || (cond_code == NE_EXPR
346 && integer_zerop (TREE_OPERAND (cond, 1)))
347 || (cond_code == EQ_EXPR
348 && integer_onep (TREE_OPERAND (cond, 1))))
353 new_arg = TREE_OPERAND (def_rhs, 0);
354 new_cond = build2 (new_code, boolean_type_node, new_arg,
355 fold_convert (TREE_TYPE (new_arg),
361 *test_var_p = test_var;
365 /* Forward propagate a single-use variable into COND_EXPR as many
366 times as possible. */
369 forward_propagate_into_cond (tree cond_expr)
371 gcc_assert (TREE_CODE (cond_expr) == COND_EXPR);
375 tree test_var = NULL_TREE;
376 tree cond = COND_EXPR_COND (cond_expr);
377 tree new_cond = forward_propagate_into_cond_1 (cond, &test_var);
379 /* Return if unsuccessful. */
380 if (new_cond == NULL_TREE)
384 if (dump_file && (dump_flags & TDF_DETAILS))
386 fprintf (dump_file, " Replaced '");
387 print_generic_expr (dump_file, cond, dump_flags);
388 fprintf (dump_file, "' with '");
389 print_generic_expr (dump_file, new_cond, dump_flags);
390 fprintf (dump_file, "'\n");
393 COND_EXPR_COND (cond_expr) = new_cond;
394 update_stmt (cond_expr);
396 if (has_zero_uses (test_var))
398 tree def = SSA_NAME_DEF_STMT (test_var);
399 block_stmt_iterator bsi = bsi_for_stmt (def);
405 /* Main entry point for the forward propagation optimizer. */
408 tree_ssa_forward_propagate_single_use_vars (void)
414 tree last = last_stmt (bb);
415 if (last && TREE_CODE (last) == COND_EXPR)
416 forward_propagate_into_cond (last);
427 struct tree_opt_pass pass_forwprop = {
428 "forwprop", /* name */
429 gate_forwprop, /* gate */
430 tree_ssa_forward_propagate_single_use_vars, /* execute */
433 0, /* static_pass_number */
434 TV_TREE_FORWPROP, /* tv_id */
436 | PROP_alias, /* properties_required */
437 0, /* properties_provided */
438 0, /* properties_destroyed */
439 0, /* todo_flags_start */
440 TODO_dump_func | TODO_ggc_collect /* todo_flags_finish */