]>
Commit | Line | Data |
---|---|---|
291d763b | 1 | /* Forward propagation of expressions for single use variables. |
3bb6785a | 2 | Copyright (C) 2004, 2005 Free Software Foundation, Inc. |
4ee9c684 | 3 | |
4 | This file is part of GCC. | |
5 | ||
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) | |
9 | any later version. | |
10 | ||
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. | |
15 | ||
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. */ | |
20 | ||
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "tm.h" | |
25 | #include "errors.h" | |
26 | #include "ggc.h" | |
27 | #include "tree.h" | |
28 | #include "rtl.h" | |
29 | #include "tm_p.h" | |
30 | #include "basic-block.h" | |
31 | #include "timevar.h" | |
32 | #include "diagnostic.h" | |
33 | #include "tree-flow.h" | |
34 | #include "tree-pass.h" | |
35 | #include "tree-dump.h" | |
291d763b | 36 | #include "langhooks.h" |
4ee9c684 | 37 | |
291d763b | 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. | |
4ee9c684 | 41 | |
291d763b | 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. | |
46 | ||
47 | One class of common cases we handle is forward propagating a single use | |
c78cbec8 | 48 | variable into a COND_EXPR. |
4ee9c684 | 49 | |
50 | bb0: | |
51 | x = a COND b; | |
52 | if (x) goto ... else goto ... | |
53 | ||
54 | Will be transformed into: | |
55 | ||
56 | bb0: | |
57 | if (a COND b) goto ... else goto ... | |
58 | ||
59 | Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1). | |
60 | ||
61 | Or (assuming c1 and c2 are constants): | |
62 | ||
63 | bb0: | |
64 | x = a + c1; | |
65 | if (x EQ/NEQ c2) goto ... else goto ... | |
66 | ||
67 | Will be transformed into: | |
68 | ||
69 | bb0: | |
70 | if (a EQ/NEQ (c2 - c1)) goto ... else goto ... | |
71 | ||
72 | Similarly for x = a - c1. | |
73 | ||
74 | Or | |
75 | ||
76 | bb0: | |
77 | x = !a | |
78 | if (x) goto ... else goto ... | |
79 | ||
80 | Will be transformed into: | |
81 | ||
82 | bb0: | |
83 | if (a == 0) goto ... else goto ... | |
84 | ||
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. | |
88 | ||
f5c8cff5 | 89 | Or |
90 | ||
91 | bb0: | |
92 | x = (typecast) a | |
93 | if (x) goto ... else goto ... | |
94 | ||
95 | Will be transformed into: | |
96 | ||
97 | bb0: | |
98 | if (a != 0) goto ... else goto ... | |
99 | ||
100 | (Assuming a is an integral type and x is a boolean or x is an | |
101 | integral and a is a boolean.) | |
102 | ||
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. | |
106 | ||
4ee9c684 | 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 | |
e6dfde59 | 109 | adding insane complexity in the dominator optimizer. |
4ee9c684 | 110 | |
f5c8cff5 | 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. | |
115 | ||
291d763b | 116 | A second class of propagation opportunities arises for ADDR_EXPR |
117 | nodes. | |
118 | ||
119 | ptr = &x->y->z; | |
120 | res = *ptr; | |
121 | ||
122 | Will get turned into | |
123 | ||
124 | res = x->y->z; | |
125 | ||
126 | Or | |
127 | ||
128 | ptr = &x[0]; | |
129 | ptr2 = ptr + <constant>; | |
130 | ||
131 | Will get turned into | |
132 | ||
133 | ptr2 = &x[constant/elementsize]; | |
134 | ||
135 | Or | |
136 | ||
137 | ptr = &x[0]; | |
138 | offset = index * element_size; | |
139 | offset_p = (pointer) offset; | |
140 | ptr2 = ptr + offset_p | |
141 | ||
142 | Will get turned into: | |
143 | ||
144 | ptr2 = &x[index]; | |
145 | ||
146 | ||
4ee9c684 | 147 | This will (of course) be extended as other needs arise. */ |
148 | ||
148aa112 | 149 | |
150 | /* Set to true if we delete EH edges during the optimization. */ | |
151 | static bool cfg_changed; | |
152 | ||
153 | ||
a3451973 | 154 | /* Given an SSA_NAME VAR, return true if and only if VAR is defined by |
155 | a comparison. */ | |
156 | ||
157 | static bool | |
158 | ssa_name_defined_by_comparison_p (tree var) | |
159 | { | |
160 | tree def = SSA_NAME_DEF_STMT (var); | |
161 | ||
162 | if (TREE_CODE (def) == MODIFY_EXPR) | |
163 | { | |
164 | tree rhs = TREE_OPERAND (def, 1); | |
165 | return COMPARISON_CLASS_P (rhs); | |
166 | } | |
167 | ||
168 | return 0; | |
169 | } | |
170 | ||
e6dfde59 | 171 | /* Forward propagate a single-use variable into COND once. Return a |
172 | new condition if successful. Return NULL_TREE otherwise. */ | |
4ee9c684 | 173 | |
e6dfde59 | 174 | static tree |
175 | forward_propagate_into_cond_1 (tree cond, tree *test_var_p) | |
f5c8cff5 | 176 | { |
e6dfde59 | 177 | tree new_cond = NULL_TREE; |
178 | enum tree_code cond_code = TREE_CODE (cond); | |
179 | tree test_var = NULL_TREE; | |
180 | tree def; | |
181 | tree def_rhs; | |
182 | ||
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 | |
185 | optimizable case. | |
186 | ||
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))))) | |
194 | return NULL_TREE; | |
195 | ||
196 | /* Extract the single variable used in the test into TEST_VAR. */ | |
197 | if (cond_code == SSA_NAME) | |
198 | test_var = cond; | |
199 | else | |
200 | test_var = TREE_OPERAND (cond, 0); | |
201 | ||
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) | |
206 | return NULL_TREE; | |
207 | ||
208 | def_rhs = TREE_OPERAND (def, 1); | |
209 | ||
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) | |
4ee9c684 | 216 | { |
e6dfde59 | 217 | tree op0 = TREE_OPERAND (def_rhs, 0); |
218 | tree op1 = TREE_OPERAND (def_rhs, 1); | |
219 | ||
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))) | |
225 | return NULL_TREE; | |
226 | ||
227 | /* Don't propagate if the first operand occurs in | |
228 | an abnormal PHI. */ | |
229 | if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)) | |
230 | return NULL_TREE; | |
231 | ||
232 | if (has_single_use (test_var)) | |
4ee9c684 | 233 | { |
e6dfde59 | 234 | enum tree_code new_code; |
235 | tree t; | |
236 | ||
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)) | |
246 | return NULL_TREE; | |
247 | ||
248 | new_cond = build (cond_code, boolean_type_node, op0, t); | |
4ee9c684 | 249 | } |
250 | } | |
4ee9c684 | 251 | |
e6dfde59 | 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))) | |
4ee9c684 | 257 | { |
e6dfde59 | 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)) | |
4ee9c684 | 262 | { |
e6dfde59 | 263 | tree op0 = TREE_OPERAND (def_rhs, 0); |
264 | tree op1 = TREE_OPERAND (def_rhs, 1); | |
265 | ||
266 | /* Both operands of DEF_RHS must be SSA_NAMEs or | |
267 | constants. */ | |
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))) | |
272 | return NULL_TREE; | |
273 | ||
274 | /* Don't propagate if the first operand occurs in | |
275 | an abnormal PHI. */ | |
276 | if (TREE_CODE (op0) == SSA_NAME | |
277 | && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)) | |
278 | return NULL_TREE; | |
279 | ||
280 | /* Don't propagate if the second operand occurs in | |
281 | an abnormal PHI. */ | |
282 | if (TREE_CODE (op1) == SSA_NAME | |
283 | && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1)) | |
284 | return NULL_TREE; | |
285 | ||
286 | if (has_single_use (test_var)) | |
4ee9c684 | 287 | { |
288 | /* TEST_VAR was set from a relational operator. */ | |
e6dfde59 | 289 | new_cond = build (TREE_CODE (def_rhs), |
290 | boolean_type_node, op0, op1); | |
4ee9c684 | 291 | |
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)))) | |
297 | { | |
298 | new_cond = invert_truthvalue (new_cond); | |
299 | ||
e6dfde59 | 300 | /* If we did not get a simple relational |
301 | expression or bare SSA_NAME, then we can | |
302 | not optimize this case. */ | |
ce45a448 | 303 | if (!COMPARISON_CLASS_P (new_cond) |
4ee9c684 | 304 | && TREE_CODE (new_cond) != SSA_NAME) |
e6dfde59 | 305 | new_cond = NULL_TREE; |
4ee9c684 | 306 | } |
307 | } | |
e6dfde59 | 308 | } |
309 | ||
310 | /* If TEST_VAR is set from a TRUTH_NOT_EXPR, then it | |
311 | is interesting. */ | |
312 | else if (TREE_CODE (def_rhs) == TRUTH_NOT_EXPR) | |
313 | { | |
314 | enum tree_code new_code; | |
315 | ||
316 | def_rhs = TREE_OPERAND (def_rhs, 0); | |
317 | ||
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)) | |
321 | return NULL_TREE; | |
322 | ||
323 | /* Don't propagate if the operand occurs in | |
324 | an abnormal PHI. */ | |
325 | if (TREE_CODE (def_rhs) == SSA_NAME | |
326 | && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_rhs)) | |
327 | return NULL_TREE; | |
328 | ||
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)))) | |
334 | new_code = EQ_EXPR; | |
335 | else | |
336 | new_code = NE_EXPR; | |
337 | ||
338 | new_cond = build2 (new_code, boolean_type_node, def_rhs, | |
339 | fold_convert (TREE_TYPE (def_rhs), | |
340 | integer_zero_node)); | |
341 | } | |
342 | ||
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) | |
348 | { | |
349 | tree outer_type; | |
350 | tree inner_type; | |
351 | ||
352 | outer_type = TREE_TYPE (def_rhs); | |
353 | inner_type = TREE_TYPE (TREE_OPERAND (def_rhs, 0)); | |
354 | ||
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))) | |
359 | ; | |
a3451973 | 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, | |
364 | 0))) | |
365 | ; | |
4ee9c684 | 366 | else |
e6dfde59 | 367 | return NULL_TREE; |
368 | ||
369 | /* Don't propagate if the operand occurs in | |
370 | an abnormal PHI. */ | |
371 | if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME | |
372 | && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND | |
373 | (def_rhs, 0))) | |
374 | return NULL_TREE; | |
375 | ||
376 | if (has_single_use (test_var)) | |
4ee9c684 | 377 | { |
f5c8cff5 | 378 | enum tree_code new_code; |
5c9198bd | 379 | tree new_arg; |
f5c8cff5 | 380 | |
4ee9c684 | 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)))) | |
f5c8cff5 | 386 | new_code = NE_EXPR; |
4ee9c684 | 387 | else |
f5c8cff5 | 388 | new_code = EQ_EXPR; |
389 | ||
5c9198bd | 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), | |
393 | integer_zero_node)); | |
4ee9c684 | 394 | } |
e6dfde59 | 395 | } |
396 | } | |
4ee9c684 | 397 | |
e6dfde59 | 398 | *test_var_p = test_var; |
399 | return new_cond; | |
400 | } | |
401 | ||
402 | /* Forward propagate a single-use variable into COND_EXPR as many | |
403 | times as possible. */ | |
4ee9c684 | 404 | |
e6dfde59 | 405 | static void |
406 | forward_propagate_into_cond (tree cond_expr) | |
407 | { | |
408 | gcc_assert (TREE_CODE (cond_expr) == COND_EXPR); | |
409 | ||
410 | while (1) | |
411 | { | |
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); | |
415 | ||
416 | /* Return if unsuccessful. */ | |
417 | if (new_cond == NULL_TREE) | |
418 | break; | |
419 | ||
420 | /* Dump details. */ | |
421 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
422 | { | |
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"); | |
4ee9c684 | 428 | } |
429 | ||
e6dfde59 | 430 | COND_EXPR_COND (cond_expr) = new_cond; |
431 | update_stmt (cond_expr); | |
432 | ||
433 | if (has_zero_uses (test_var)) | |
8275f96f | 434 | { |
e6dfde59 | 435 | tree def = SSA_NAME_DEF_STMT (test_var); |
436 | block_stmt_iterator bsi = bsi_for_stmt (def); | |
8275f96f | 437 | bsi_remove (&bsi); |
438 | } | |
4ee9c684 | 439 | } |
440 | } | |
441 | ||
148aa112 | 442 | /* We've just substituted an ADDR_EXPR into stmt. Update all the |
443 | relevant data structures to match. */ | |
444 | ||
445 | static void | |
446 | tidy_after_forward_propagate_addr (tree stmt) | |
447 | { | |
448 | mark_new_vars_to_rename (stmt); | |
449 | update_stmt (stmt); | |
450 | ||
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))) | |
454 | cfg_changed = true; | |
455 | } | |
456 | ||
291d763b | 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. | |
461 | ||
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. | |
465 | ||
466 | We then try to fold the entire address expression into a form | |
467 | &array[index]. | |
468 | ||
469 | If we are successful, we replace the right hand side of USE_STMT | |
470 | with the new address computation. */ | |
471 | ||
472 | static bool | |
473 | forward_propagate_addr_into_variable_array_index (tree offset, tree lhs, | |
474 | tree stmt, tree use_stmt) | |
475 | { | |
476 | tree index; | |
477 | ||
478 | /* The offset must be defined by a simple MODIFY_EXPR statement. */ | |
479 | if (TREE_CODE (offset) != MODIFY_EXPR) | |
480 | return false; | |
481 | ||
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)) | |
486 | return false; | |
487 | ||
488 | offset = TREE_OPERAND (offset, 0); | |
489 | if (TREE_CODE (offset) != SSA_NAME) | |
490 | return false; | |
491 | ||
492 | /* Get the defining statement of the offset before type | |
493 | conversion. */ | |
494 | offset = SSA_NAME_DEF_STMT (offset); | |
495 | ||
496 | /* The statement which defines OFFSET before type conversion | |
497 | must be a simple MODIFY_EXPR. */ | |
498 | if (TREE_CODE (offset) != MODIFY_EXPR) | |
499 | return false; | |
500 | ||
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 | |
504 | is constant. */ | |
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))))) | |
510 | return false; | |
511 | ||
512 | /* The first operand to the MULT_EXPR is the desired index. */ | |
513 | index = TREE_OPERAND (offset, 0); | |
514 | ||
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; | |
518 | ||
519 | /* That should have created gimple, so there is no need to | |
520 | record information to undo the propagation. */ | |
148aa112 | 521 | fold_stmt_inplace (use_stmt); |
522 | tidy_after_forward_propagate_addr (use_stmt); | |
291d763b | 523 | return true; |
524 | } | |
525 | ||
526 | /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>. | |
527 | ||
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. */ | |
531 | ||
532 | static bool | |
533 | forward_propagate_addr_expr (tree stmt) | |
534 | { | |
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; | |
539 | ||
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); | |
545 | if (!use_stmt) | |
546 | return false; | |
547 | ||
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) | |
551 | return false; | |
552 | ||
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) | |
557 | return false; | |
558 | ||
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); | |
563 | ||
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) | |
567 | { | |
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)); | |
148aa112 | 571 | fold_stmt_inplace (use_stmt); |
572 | tidy_after_forward_propagate_addr (use_stmt); | |
291d763b | 573 | return true; |
574 | } | |
575 | ||
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 | |
582 | for example. */ | |
583 | if (TREE_CODE (lhs) == SSA_NAME && TREE_OPERAND (use_stmt, 1) == name) | |
584 | { | |
585 | TREE_OPERAND (use_stmt, 1) = unshare_expr (TREE_OPERAND (stmt, 1)); | |
148aa112 | 586 | tidy_after_forward_propagate_addr (use_stmt); |
291d763b | 587 | return true; |
588 | } | |
589 | ||
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); | |
594 | ||
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) | |
598 | { | |
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)); | |
148aa112 | 602 | fold_stmt_inplace (use_stmt); |
603 | tidy_after_forward_propagate_addr (use_stmt); | |
291d763b | 604 | return true; |
605 | } | |
606 | ||
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 | |
610 | is nothing to do. */ | |
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))) | |
615 | return false; | |
616 | ||
617 | /* If the use of the ADDR_EXPR must be a PLUS_EXPR, or else there | |
618 | is nothing to do. */ | |
619 | if (TREE_CODE (rhs) != PLUS_EXPR) | |
620 | return false; | |
621 | ||
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) | |
626 | { | |
627 | tree orig = unshare_expr (rhs); | |
628 | TREE_OPERAND (rhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1)); | |
629 | ||
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. */ | |
148aa112 | 633 | if (fold_stmt_inplace (use_stmt)) |
291d763b | 634 | { |
148aa112 | 635 | tidy_after_forward_propagate_addr (use_stmt); |
291d763b | 636 | return true; |
637 | } | |
638 | else | |
639 | { | |
640 | TREE_OPERAND (use_stmt, 1) = orig; | |
641 | update_stmt (use_stmt); | |
642 | return false; | |
643 | } | |
644 | } | |
645 | ||
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))) | |
655 | { | |
656 | tree offset_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 1)); | |
657 | return forward_propagate_addr_into_variable_array_index (offset_stmt, lhs, | |
658 | stmt, use_stmt); | |
659 | } | |
660 | ||
661 | /* Same as the previous case, except the operands of the PLUS_EXPR | |
662 | were reversed. */ | |
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))) | |
668 | { | |
669 | tree offset_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0)); | |
670 | return forward_propagate_addr_into_variable_array_index (offset_stmt, lhs, | |
671 | stmt, use_stmt); | |
672 | } | |
673 | return false; | |
674 | } | |
675 | ||
4ee9c684 | 676 | /* Main entry point for the forward propagation optimizer. */ |
677 | ||
678 | static void | |
679 | tree_ssa_forward_propagate_single_use_vars (void) | |
680 | { | |
f5c8cff5 | 681 | basic_block bb; |
4ee9c684 | 682 | |
148aa112 | 683 | cfg_changed = false; |
684 | ||
f5c8cff5 | 685 | FOR_EACH_BB (bb) |
686 | { | |
291d763b | 687 | block_stmt_iterator bsi; |
688 | ||
689 | /* Note we update BSI within the loop as necessary. */ | |
690 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); ) | |
691 | { | |
692 | tree stmt = bsi_stmt (bsi); | |
693 | ||
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) | |
699 | { | |
700 | if (forward_propagate_addr_expr (stmt)) | |
701 | bsi_remove (&bsi); | |
702 | else | |
703 | bsi_next (&bsi); | |
704 | } | |
705 | else if (TREE_CODE (stmt) == COND_EXPR) | |
706 | { | |
707 | forward_propagate_into_cond (stmt); | |
708 | bsi_next (&bsi); | |
709 | } | |
710 | else | |
711 | bsi_next (&bsi); | |
712 | } | |
f5c8cff5 | 713 | } |
148aa112 | 714 | |
715 | if (cfg_changed) | |
716 | cleanup_tree_cfg (); | |
4ee9c684 | 717 | } |
718 | ||
719 | ||
720 | static bool | |
721 | gate_forwprop (void) | |
722 | { | |
723 | return 1; | |
724 | } | |
725 | ||
726 | struct tree_opt_pass pass_forwprop = { | |
727 | "forwprop", /* name */ | |
728 | gate_forwprop, /* gate */ | |
729 | tree_ssa_forward_propagate_single_use_vars, /* execute */ | |
730 | NULL, /* sub */ | |
731 | NULL, /* next */ | |
732 | 0, /* static_pass_number */ | |
733 | TV_TREE_FORWPROP, /* tv_id */ | |
f45a1ca1 | 734 | PROP_cfg | PROP_ssa |
735 | | PROP_alias, /* properties_required */ | |
4ee9c684 | 736 | 0, /* properties_provided */ |
737 | 0, /* properties_destroyed */ | |
738 | 0, /* todo_flags_start */ | |
739 | TODO_dump_func | TODO_ggc_collect /* todo_flags_finish */ | |
291d763b | 740 | | TODO_update_ssa | TODO_verify_ssa, |
0f9005dd | 741 | 0 /* letter */ |
4ee9c684 | 742 | }; |