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 /* Bitmap of variables for which we want immediate uses. This is set
113 by record_single_argument_cond_exprs and tested in need_imm_uses_for. */
116 static void tree_ssa_forward_propagate_single_use_vars (void);
117 static void record_single_argument_cond_exprs (varray_type
,
120 static void substitute_single_use_vars (varray_type
*, varray_type
);
122 /* Find all COND_EXPRs with a condition that is a naked SSA_NAME or
123 an equality comparison against a constant.
125 Record the identified COND_EXPRs and the SSA_NAME used in the COND_EXPR
126 into a virtual array, which is returned to the caller. Also record
127 into VARS that we will need immediate uses for the identified SSA_NAME.
129 The more uninteresting COND_EXPRs and associated SSA_NAMEs we can
130 filter out here, the faster this pass will run since its runtime is
131 dominated by the time to build immediate uses. */
134 record_single_argument_cond_exprs (varray_type cond_worklist
,
135 varray_type
*vars_worklist
,
139 /* The first pass over the blocks gathers the set of variables we need
140 immediate uses for as well as the set of interesting COND_EXPRs.
142 A simpler implementation may be appropriate if/when we have a lower
143 overhead means of getting immediate use information. */
144 while (VARRAY_ACTIVE_SIZE (cond_worklist
) > 0)
146 tree last
= VARRAY_TOP_TREE (cond_worklist
);
148 VARRAY_POP (cond_worklist
);
150 /* See if this block ends in a COND_EXPR. */
151 if (last
&& TREE_CODE (last
) == COND_EXPR
)
153 tree cond
= COND_EXPR_COND (last
);
154 enum tree_code cond_code
= TREE_CODE (cond
);
156 /* If the condition is a lone variable or an equality test of
157 an SSA_NAME against an integral constant, then we may have an
160 Note these conditions also ensure the COND_EXPR has no
161 virtual operands or other side effects. */
162 if (cond_code
== SSA_NAME
163 || ((cond_code
== EQ_EXPR
|| cond_code
== NE_EXPR
)
164 && TREE_CODE (TREE_OPERAND (cond
, 0)) == SSA_NAME
165 && CONSTANT_CLASS_P (TREE_OPERAND (cond
, 1))
166 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond
, 1)))))
171 /* Extract the single variable used in the test into TEST_VAR. */
172 if (cond_code
== SSA_NAME
)
175 test_var
= TREE_OPERAND (cond
, 0);
177 /* If we have already recorded this SSA_NAME as interesting,
178 do not do so again. */
179 if (bitmap_bit_p (vars
, SSA_NAME_VERSION (test_var
)))
182 /* Now get the defining statement for TEST_VAR and see if it
183 something we are interested in. */
184 def
= SSA_NAME_DEF_STMT (test_var
);
185 if (TREE_CODE (def
) == MODIFY_EXPR
)
187 tree def_rhs
= TREE_OPERAND (def
, 1);
189 /* If TEST_VAR is set by adding or subtracting a constant
190 from an SSA_NAME, then it is interesting to us as we
191 can adjust the constant in the conditional and thus
192 eliminate the arithmetic operation. */
193 if (TREE_CODE (def_rhs
) == PLUS_EXPR
194 || TREE_CODE (def_rhs
) == MINUS_EXPR
)
196 tree op0
= TREE_OPERAND (def_rhs
, 0);
197 tree op1
= TREE_OPERAND (def_rhs
, 1);
199 /* The first operand must be an SSA_NAME and the second
200 operand must be a constant. */
201 if (TREE_CODE (op0
) != SSA_NAME
202 || !CONSTANT_CLASS_P (op1
)
203 || !INTEGRAL_TYPE_P (TREE_TYPE (op1
)))
206 /* Don't propagate if the first operand occurs in
208 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0
))
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
))
247 /* If TEST_VAR is set from a TRUTH_NOT_EXPR, then it
249 else if (TREE_CODE (def_rhs
) == TRUTH_NOT_EXPR
)
251 def_rhs
= TREE_OPERAND (def_rhs
, 0);
253 /* DEF_RHS must be an SSA_NAME or constant. */
254 if (TREE_CODE (def_rhs
) != SSA_NAME
255 && !is_gimple_min_invariant (def_rhs
))
258 /* Don't propagate if the operand occurs in
260 if (TREE_CODE (def_rhs
) == SSA_NAME
261 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_rhs
))
265 /* If TEST_VAR was set from a cast of an integer type
266 to a boolean type or a cast of a boolean to an
267 integral, then it is interesting. */
268 else if (TREE_CODE (def_rhs
) == NOP_EXPR
269 || TREE_CODE (def_rhs
) == CONVERT_EXPR
)
274 outer_type
= TREE_TYPE (def_rhs
);
275 inner_type
= TREE_TYPE (TREE_OPERAND (def_rhs
, 0));
277 if ((TREE_CODE (outer_type
) == BOOLEAN_TYPE
278 && INTEGRAL_TYPE_P (inner_type
))
279 || (TREE_CODE (inner_type
) == BOOLEAN_TYPE
280 && INTEGRAL_TYPE_P (outer_type
)))
285 /* Don't propagate if the operand occurs in
287 if (TREE_CODE (TREE_OPERAND (def_rhs
, 0)) == SSA_NAME
288 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND
298 /* All the tests passed, record TEST_VAR as interesting. */
299 VARRAY_PUSH_TREE (*vars_worklist
, test_var
);
300 bitmap_set_bit (vars
, SSA_NAME_VERSION (test_var
));
307 /* Given FORWPROP_DATA containing SSA_NAMEs which are used in COND_EXPRs
308 that we may be able to optimize, attempt to rewrite the condition
309 in each COND_EXPR to use the RHS of the statement which defines the
310 SSA_NAME used in the COND_EXPR. */
313 substitute_single_use_vars (varray_type
*cond_worklist
,
314 varray_type vars_worklist
)
317 while (VARRAY_ACTIVE_SIZE (vars_worklist
) > 0)
319 tree test_var
= VARRAY_TOP_TREE (vars_worklist
);
320 tree def_stmt
= SSA_NAME_DEF_STMT (test_var
);
322 int num_uses
, propagated_uses
;
323 imm_use_iterator imm_iter
;
325 VARRAY_POP (vars_worklist
);
330 if (NUM_DEFS (STMT_DEF_OPS (def_stmt
)) != 1)
333 def
= DEF_OP (STMT_DEF_OPS (def_stmt
), 0);
335 /* If TEST_VAR is used more than once and is not a boolean set
336 via TRUTH_NOT_EXPR with another SSA_NAME as its argument, then
337 we can not optimize. */
338 if (has_single_use (def
)
339 || (TREE_CODE (TREE_TYPE (test_var
)) == BOOLEAN_TYPE
340 && TREE_CODE (TREE_OPERAND (def_stmt
, 1)) == TRUTH_NOT_EXPR
341 && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (def_stmt
, 1), 0))
347 /* Walk over each use and try to forward propagate the RHS of
349 FOR_EACH_IMM_USE_SAFE (use_p
, imm_iter
, def
)
353 enum tree_code cond_code
;
355 enum tree_code def_rhs_code
;
358 cond_stmt
= USE_STMT (use_p
);
361 /* For now we can only propagate into COND_EXPRs. */
362 if (TREE_CODE (cond_stmt
) != COND_EXPR
)
365 cond
= COND_EXPR_COND (cond_stmt
);
366 cond_code
= TREE_CODE (cond
);
367 def_rhs
= TREE_OPERAND (def_stmt
, 1);
368 def_rhs_code
= TREE_CODE (def_rhs
);
370 /* If the definition of the single use variable was from an
371 arithmetic operation, then we just need to adjust the
372 constant in the COND_EXPR_COND and update the variable tested. */
373 if (def_rhs_code
== PLUS_EXPR
|| def_rhs_code
== MINUS_EXPR
)
375 tree op0
= TREE_OPERAND (def_rhs
, 0);
376 tree op1
= TREE_OPERAND (def_rhs
, 1);
377 enum tree_code new_code
;
380 /* If the variable was defined via X + C, then we must subtract
381 C from the constant in the conditional. Otherwise we add
382 C to the constant in the conditional. The result must fold
383 into a valid gimple operand to be optimizable. */
384 new_code
= def_rhs_code
== PLUS_EXPR
? MINUS_EXPR
: PLUS_EXPR
;
385 t
= int_const_binop (new_code
, TREE_OPERAND (cond
, 1), op1
, 0);
386 if (!is_gimple_val (t
))
389 new_cond
= build (cond_code
, boolean_type_node
, op0
, t
);
391 /* If the variable is defined by a conditional expression... */
392 else if (TREE_CODE_CLASS (def_rhs_code
) == tcc_comparison
)
394 /* TEST_VAR was set from a relational operator. */
395 tree op0
= TREE_OPERAND (def_rhs
, 0);
396 tree op1
= TREE_OPERAND (def_rhs
, 1);
398 new_cond
= build (def_rhs_code
, boolean_type_node
, op0
, op1
);
400 /* Invert the conditional if necessary. */
401 if ((cond_code
== EQ_EXPR
402 && integer_zerop (TREE_OPERAND (cond
, 1)))
403 || (cond_code
== NE_EXPR
404 && integer_onep (TREE_OPERAND (cond
, 1))))
406 new_cond
= invert_truthvalue (new_cond
);
408 /* If we did not get a simple relational expression or
409 bare SSA_NAME, then we can not optimize this case. */
410 if (!COMPARISON_CLASS_P (new_cond
)
411 && TREE_CODE (new_cond
) != SSA_NAME
)
418 enum tree_code new_code
;
421 /* TEST_VAR was set from a TRUTH_NOT_EXPR or a NOP_EXPR. */
422 if (def_rhs_code
== TRUTH_NOT_EXPR
)
425 if (cond_code
== SSA_NAME
426 || (cond_code
== NE_EXPR
427 && integer_zerop (TREE_OPERAND (cond
, 1)))
428 || (cond_code
== EQ_EXPR
429 && integer_onep (TREE_OPERAND (cond
, 1))))
435 new_code
= (new_code
== EQ_EXPR
? NE_EXPR
: EQ_EXPR
);
437 new_arg
= TREE_OPERAND (def_rhs
, 0);
438 new_cond
= build2 (new_code
, boolean_type_node
, new_arg
,
439 fold_convert (TREE_TYPE (new_arg
),
444 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
446 fprintf (dump_file
, " Replaced '");
447 print_generic_expr (dump_file
, cond
, dump_flags
);
448 fprintf (dump_file
, "' with '");
449 print_generic_expr (dump_file
, new_cond
, dump_flags
);
450 fprintf (dump_file
, "'\n");
453 /* Replace the condition. */
454 COND_EXPR_COND (cond_stmt
) = new_cond
;
455 update_stmt (cond_stmt
);
457 VARRAY_PUSH_TREE (*cond_worklist
, cond_stmt
);
460 /* If we propagated into all the uses, then we can delete DEF.
461 Unfortunately, we have to find the defining statement in
462 whatever block it might be in. */
463 if (num_uses
&& num_uses
== propagated_uses
)
465 block_stmt_iterator bsi
= bsi_for_stmt (def_stmt
);
471 /* Main entry point for the forward propagation optimizer. */
474 tree_ssa_forward_propagate_single_use_vars (void)
477 varray_type vars_worklist
, cond_worklist
;
479 vars
= BITMAP_ALLOC (NULL
);
480 VARRAY_TREE_INIT (vars_worklist
, 10, "VARS worklist");
481 VARRAY_TREE_INIT (cond_worklist
, 10, "COND worklist");
483 /* Prime the COND_EXPR worklist by placing all the COND_EXPRs on the
487 tree last
= last_stmt (bb
);
488 if (last
&& TREE_CODE (last
) == COND_EXPR
)
489 VARRAY_PUSH_TREE (cond_worklist
, last
);
492 while (VARRAY_ACTIVE_SIZE (cond_worklist
) > 0)
494 /* First get a list of all the interesting COND_EXPRs and potential
495 single use variables which feed those COND_EXPRs. This will drain
496 COND_WORKLIST and initialize VARS_WORKLIST. */
497 record_single_argument_cond_exprs (cond_worklist
, &vars_worklist
, vars
);
499 if (VARRAY_ACTIVE_SIZE (vars_worklist
) > 0)
501 /* We've computed immediate uses, so we can/must clear the VARS
502 bitmap for the next iteration. */
505 /* And optimize. This will drain VARS_WORKLIST and initialize
506 COND_WORKLIST for the next iteration. */
507 substitute_single_use_vars (&cond_worklist
, vars_worklist
);
511 /* All done. Clean up. */
522 struct tree_opt_pass pass_forwprop
= {
523 "forwprop", /* name */
524 gate_forwprop
, /* gate */
525 tree_ssa_forward_propagate_single_use_vars
, /* execute */
528 0, /* static_pass_number */
529 TV_TREE_FORWPROP
, /* tv_id */
531 | PROP_alias
, /* properties_required */
532 0, /* properties_provided */
533 0, /* properties_destroyed */
534 0, /* todo_flags_start */
535 TODO_dump_func
| TODO_ggc_collect
/* todo_flags_finish */