]>
Commit | Line | Data |
---|---|---|
291d763b | 1 | /* Forward propagation of expressions for single use variables. |
8c4c00c1 | 2 | Copyright (C) 2004, 2005, 2007 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 | |
8c4c00c1 | 8 | the Free Software Foundation; either version 3, or (at your option) |
4ee9c684 | 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 | |
8c4c00c1 | 17 | along with GCC; see the file COPYING3. If not see |
18 | <http://www.gnu.org/licenses/>. */ | |
4ee9c684 | 19 | |
20 | #include "config.h" | |
21 | #include "system.h" | |
22 | #include "coretypes.h" | |
23 | #include "tm.h" | |
4ee9c684 | 24 | #include "ggc.h" |
25 | #include "tree.h" | |
26 | #include "rtl.h" | |
27 | #include "tm_p.h" | |
28 | #include "basic-block.h" | |
29 | #include "timevar.h" | |
30 | #include "diagnostic.h" | |
31 | #include "tree-flow.h" | |
32 | #include "tree-pass.h" | |
33 | #include "tree-dump.h" | |
291d763b | 34 | #include "langhooks.h" |
5adc1066 | 35 | #include "flags.h" |
4ee9c684 | 36 | |
291d763b | 37 | /* This pass propagates the RHS of assignment statements into use |
38 | sites of the LHS of the assignment. It's basically a specialized | |
8f628ee8 | 39 | form of tree combination. It is hoped all of this can disappear |
40 | when we have a generalized tree combiner. | |
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 | ||
8f628ee8 | 146 | We also propagate casts into SWITCH_EXPR and COND_EXPR conditions to |
147 | allow us to remove the cast and {NOT_EXPR,NEG_EXPR} into a subsequent | |
148 | {NOT_EXPR,NEG_EXPR}. | |
291d763b | 149 | |
4ee9c684 | 150 | This will (of course) be extended as other needs arise. */ |
151 | ||
15ec875c | 152 | static bool forward_propagate_addr_expr (tree name, tree rhs); |
148aa112 | 153 | |
154 | /* Set to true if we delete EH edges during the optimization. */ | |
155 | static bool cfg_changed; | |
156 | ||
157 | ||
83a20baf | 158 | /* Get the next statement we can propagate NAME's value into skipping |
5adc1066 | 159 | trivial copies. Returns the statement that is suitable as a |
160 | propagation destination or NULL_TREE if there is no such one. | |
161 | This only returns destinations in a single-use chain. FINAL_NAME_P | |
162 | if non-NULL is written to the ssa name that represents the use. */ | |
a3451973 | 163 | |
5adc1066 | 164 | static tree |
165 | get_prop_dest_stmt (tree name, tree *final_name_p) | |
a3451973 | 166 | { |
5adc1066 | 167 | use_operand_p use; |
168 | tree use_stmt; | |
a3451973 | 169 | |
5adc1066 | 170 | do { |
171 | /* If name has multiple uses, bail out. */ | |
172 | if (!single_imm_use (name, &use, &use_stmt)) | |
173 | return NULL_TREE; | |
a3451973 | 174 | |
5adc1066 | 175 | /* If this is not a trivial copy, we found it. */ |
176 | if (TREE_CODE (use_stmt) != GIMPLE_MODIFY_STMT | |
177 | || TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 0)) != SSA_NAME | |
178 | || GIMPLE_STMT_OPERAND (use_stmt, 1) != name) | |
179 | break; | |
180 | ||
181 | /* Continue searching uses of the copy destination. */ | |
182 | name = GIMPLE_STMT_OPERAND (use_stmt, 0); | |
183 | } while (1); | |
184 | ||
185 | if (final_name_p) | |
186 | *final_name_p = name; | |
187 | ||
188 | return use_stmt; | |
a3451973 | 189 | } |
190 | ||
5adc1066 | 191 | /* Get the statement we can propagate from into NAME skipping |
192 | trivial copies. Returns the statement which defines the | |
193 | propagation source or NULL_TREE if there is no such one. | |
194 | If SINGLE_USE_ONLY is set considers only sources which have | |
195 | a single use chain up to NAME. If SINGLE_USE_P is non-null, | |
196 | it is set to whether the chain to NAME is a single use chain | |
197 | or not. SINGLE_USE_P is not written to if SINGLE_USE_ONLY is set. */ | |
4ee9c684 | 198 | |
e6dfde59 | 199 | static tree |
5adc1066 | 200 | get_prop_source_stmt (tree name, bool single_use_only, bool *single_use_p) |
f5c8cff5 | 201 | { |
5adc1066 | 202 | bool single_use = true; |
203 | ||
204 | do { | |
205 | tree def_stmt = SSA_NAME_DEF_STMT (name); | |
206 | ||
207 | if (!has_single_use (name)) | |
208 | { | |
209 | single_use = false; | |
210 | if (single_use_only) | |
211 | return NULL_TREE; | |
212 | } | |
213 | ||
214 | /* If name is defined by a PHI node or is the default def, bail out. */ | |
215 | if (TREE_CODE (def_stmt) != GIMPLE_MODIFY_STMT) | |
216 | return NULL_TREE; | |
217 | ||
218 | /* If name is not a simple copy destination, we found it. */ | |
219 | if (TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) != SSA_NAME) | |
220 | { | |
221 | if (!single_use_only && single_use_p) | |
222 | *single_use_p = single_use; | |
223 | ||
224 | return def_stmt; | |
225 | } | |
226 | ||
227 | /* Continue searching the def of the copy source name. */ | |
228 | name = GIMPLE_STMT_OPERAND (def_stmt, 1); | |
229 | } while (1); | |
230 | } | |
e6dfde59 | 231 | |
5adc1066 | 232 | /* Checks if the destination ssa name in DEF_STMT can be used as |
233 | propagation source. Returns true if so, otherwise false. */ | |
e6dfde59 | 234 | |
5adc1066 | 235 | static bool |
236 | can_propagate_from (tree def_stmt) | |
237 | { | |
238 | tree rhs = GIMPLE_STMT_OPERAND (def_stmt, 1); | |
e6dfde59 | 239 | |
484b827b | 240 | /* If the rhs has side-effects we cannot propagate from it. */ |
241 | if (TREE_SIDE_EFFECTS (rhs)) | |
242 | return false; | |
243 | ||
244 | /* If the rhs is a load we cannot propagate from it. */ | |
245 | if (REFERENCE_CLASS_P (rhs)) | |
246 | return false; | |
247 | ||
5adc1066 | 248 | /* We cannot propagate ssa names that occur in abnormal phi nodes. */ |
249 | switch (TREE_CODE_LENGTH (TREE_CODE (rhs))) | |
4ee9c684 | 250 | { |
5adc1066 | 251 | case 3: |
252 | if (TREE_OPERAND (rhs, 2) != NULL_TREE | |
253 | && TREE_CODE (TREE_OPERAND (rhs, 2)) == SSA_NAME | |
254 | && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (rhs, 2))) | |
255 | return false; | |
256 | case 2: | |
257 | if (TREE_OPERAND (rhs, 1) != NULL_TREE | |
258 | && TREE_CODE (TREE_OPERAND (rhs, 1)) == SSA_NAME | |
259 | && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (rhs, 1))) | |
260 | return false; | |
261 | case 1: | |
262 | if (TREE_OPERAND (rhs, 0) != NULL_TREE | |
263 | && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME | |
264 | && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (rhs, 0))) | |
265 | return false; | |
266 | break; | |
267 | ||
268 | default: | |
269 | return false; | |
4ee9c684 | 270 | } |
4ee9c684 | 271 | |
5adc1066 | 272 | /* If the definition is a conversion of a pointer to a function type, |
273 | then we can not apply optimizations as some targets require function | |
274 | pointers to be canonicalized and in this case this optimization could | |
275 | eliminate a necessary canonicalization. */ | |
276 | if ((TREE_CODE (rhs) == NOP_EXPR | |
277 | || TREE_CODE (rhs) == CONVERT_EXPR) | |
278 | && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))) | |
279 | && TREE_CODE (TREE_TYPE (TREE_TYPE | |
280 | (TREE_OPERAND (rhs, 0)))) == FUNCTION_TYPE) | |
281 | return false; | |
4ee9c684 | 282 | |
5adc1066 | 283 | return true; |
e6dfde59 | 284 | } |
285 | ||
5adc1066 | 286 | /* Remove a copy chain ending in NAME along the defs but not |
287 | further or including UP_TO_STMT. If NAME was replaced in | |
288 | its only use then this function can be used to clean up | |
289 | dead stmts. Returns true if UP_TO_STMT can be removed | |
290 | as well, otherwise false. */ | |
8f628ee8 | 291 | |
5adc1066 | 292 | static bool |
293 | remove_prop_source_from_use (tree name, tree up_to_stmt) | |
294 | { | |
295 | block_stmt_iterator bsi; | |
296 | tree stmt; | |
8f628ee8 | 297 | |
5adc1066 | 298 | do { |
299 | if (!has_zero_uses (name)) | |
300 | return false; | |
8f628ee8 | 301 | |
5adc1066 | 302 | stmt = SSA_NAME_DEF_STMT (name); |
303 | if (stmt == up_to_stmt) | |
304 | return true; | |
8f628ee8 | 305 | |
5adc1066 | 306 | bsi = bsi_for_stmt (stmt); |
307 | release_defs (stmt); | |
308 | bsi_remove (&bsi, true); | |
8f628ee8 | 309 | |
5adc1066 | 310 | name = GIMPLE_STMT_OPERAND (stmt, 1); |
311 | } while (TREE_CODE (name) == SSA_NAME); | |
8f628ee8 | 312 | |
5adc1066 | 313 | return false; |
314 | } | |
8f628ee8 | 315 | |
5adc1066 | 316 | /* Combine OP0 CODE OP1 in the context of a COND_EXPR. Returns |
317 | the folded result in a form suitable for COND_EXPR_COND or | |
318 | NULL_TREE, if there is no suitable simplified form. If | |
319 | INVARIANT_ONLY is true only gimple_min_invariant results are | |
320 | considered simplified. */ | |
8f628ee8 | 321 | |
322 | static tree | |
5adc1066 | 323 | combine_cond_expr_cond (enum tree_code code, tree type, |
324 | tree op0, tree op1, bool invariant_only) | |
8f628ee8 | 325 | { |
5adc1066 | 326 | tree t; |
8f628ee8 | 327 | |
5adc1066 | 328 | gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison); |
8f628ee8 | 329 | |
5adc1066 | 330 | t = fold_binary (code, type, op0, op1); |
331 | if (!t) | |
332 | return NULL_TREE; | |
8f628ee8 | 333 | |
5adc1066 | 334 | /* Require that we got a boolean type out if we put one in. */ |
335 | gcc_assert (TREE_CODE (TREE_TYPE (t)) == TREE_CODE (type)); | |
8f628ee8 | 336 | |
a7392604 | 337 | /* Canonicalize the combined condition for use in a COND_EXPR. */ |
338 | t = canonicalize_cond_expr_cond (t); | |
8f628ee8 | 339 | |
5adc1066 | 340 | /* Bail out if we required an invariant but didn't get one. */ |
a7392604 | 341 | if (!t |
342 | || (invariant_only | |
343 | && !is_gimple_min_invariant (t))) | |
5adc1066 | 344 | return NULL_TREE; |
8f628ee8 | 345 | |
a7392604 | 346 | return t; |
8f628ee8 | 347 | } |
348 | ||
5adc1066 | 349 | /* Propagate from the ssa name definition statements of COND_EXPR |
4c580c8c | 350 | in statement STMT into the conditional if that simplifies it. |
351 | Returns zero if no statement was changed, one if there were | |
352 | changes and two if cfg_cleanup needs to run. */ | |
4ee9c684 | 353 | |
4c580c8c | 354 | static int |
ec0fa513 | 355 | forward_propagate_into_cond (tree cond_expr, tree stmt) |
e6dfde59 | 356 | { |
4c580c8c | 357 | int did_something = 0; |
d080be9e | 358 | |
5adc1066 | 359 | do { |
360 | tree tmp = NULL_TREE; | |
361 | tree cond = COND_EXPR_COND (cond_expr); | |
484b827b | 362 | tree name, def_stmt, rhs0 = NULL_TREE, rhs1 = NULL_TREE; |
f4628d45 | 363 | bool single_use0_p = false, single_use1_p = false; |
5adc1066 | 364 | |
365 | /* We can do tree combining on SSA_NAME and comparison expressions. */ | |
366 | if (COMPARISON_CLASS_P (cond) | |
367 | && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME) | |
368 | { | |
369 | /* For comparisons use the first operand, that is likely to | |
370 | simplify comparisons against constants. */ | |
371 | name = TREE_OPERAND (cond, 0); | |
f4628d45 | 372 | def_stmt = get_prop_source_stmt (name, false, &single_use0_p); |
5adc1066 | 373 | if (def_stmt != NULL_TREE |
374 | && can_propagate_from (def_stmt)) | |
375 | { | |
376 | tree op1 = TREE_OPERAND (cond, 1); | |
484b827b | 377 | rhs0 = GIMPLE_STMT_OPERAND (def_stmt, 1); |
5adc1066 | 378 | tmp = combine_cond_expr_cond (TREE_CODE (cond), boolean_type_node, |
484b827b | 379 | fold_convert (TREE_TYPE (op1), rhs0), |
f4628d45 | 380 | op1, !single_use0_p); |
5adc1066 | 381 | } |
382 | /* If that wasn't successful, try the second operand. */ | |
383 | if (tmp == NULL_TREE | |
384 | && TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME) | |
385 | { | |
386 | tree op0 = TREE_OPERAND (cond, 0); | |
387 | name = TREE_OPERAND (cond, 1); | |
f4628d45 | 388 | def_stmt = get_prop_source_stmt (name, false, &single_use1_p); |
5adc1066 | 389 | if (def_stmt == NULL_TREE |
390 | || !can_propagate_from (def_stmt)) | |
d080be9e | 391 | return did_something; |
5adc1066 | 392 | |
484b827b | 393 | rhs1 = GIMPLE_STMT_OPERAND (def_stmt, 1); |
5adc1066 | 394 | tmp = combine_cond_expr_cond (TREE_CODE (cond), boolean_type_node, |
395 | op0, | |
484b827b | 396 | fold_convert (TREE_TYPE (op0), rhs1), |
f4628d45 | 397 | !single_use1_p); |
5adc1066 | 398 | } |
484b827b | 399 | /* If that wasn't successful either, try both operands. */ |
400 | if (tmp == NULL_TREE | |
401 | && rhs0 != NULL_TREE | |
402 | && rhs1 != NULL_TREE) | |
403 | tmp = combine_cond_expr_cond (TREE_CODE (cond), boolean_type_node, | |
404 | rhs0, | |
405 | fold_convert (TREE_TYPE (rhs0), rhs1), | |
f4628d45 | 406 | !(single_use0_p && single_use1_p)); |
5adc1066 | 407 | } |
408 | else if (TREE_CODE (cond) == SSA_NAME) | |
409 | { | |
410 | name = cond; | |
411 | def_stmt = get_prop_source_stmt (name, true, NULL); | |
412 | if (def_stmt == NULL_TREE | |
413 | || !can_propagate_from (def_stmt)) | |
d080be9e | 414 | return did_something; |
5adc1066 | 415 | |
484b827b | 416 | rhs0 = GIMPLE_STMT_OPERAND (def_stmt, 1); |
417 | tmp = combine_cond_expr_cond (NE_EXPR, boolean_type_node, rhs0, | |
418 | build_int_cst (TREE_TYPE (rhs0), 0), | |
5adc1066 | 419 | false); |
420 | } | |
421 | ||
422 | if (tmp) | |
423 | { | |
424 | if (dump_file && tmp) | |
425 | { | |
426 | fprintf (dump_file, " Replaced '"); | |
427 | print_generic_expr (dump_file, cond, 0); | |
428 | fprintf (dump_file, "' with '"); | |
429 | print_generic_expr (dump_file, tmp, 0); | |
430 | fprintf (dump_file, "'\n"); | |
431 | } | |
432 | ||
433 | COND_EXPR_COND (cond_expr) = unshare_expr (tmp); | |
434 | update_stmt (stmt); | |
435 | ||
436 | /* Remove defining statements. */ | |
437 | remove_prop_source_from_use (name, NULL); | |
438 | ||
4c580c8c | 439 | if (is_gimple_min_invariant (tmp)) |
440 | did_something = 2; | |
441 | else if (did_something == 0) | |
442 | did_something = 1; | |
d080be9e | 443 | |
5adc1066 | 444 | /* Continue combining. */ |
445 | continue; | |
446 | } | |
447 | ||
448 | break; | |
449 | } while (1); | |
d080be9e | 450 | |
451 | return did_something; | |
4ee9c684 | 452 | } |
453 | ||
148aa112 | 454 | /* We've just substituted an ADDR_EXPR into stmt. Update all the |
455 | relevant data structures to match. */ | |
456 | ||
457 | static void | |
458 | tidy_after_forward_propagate_addr (tree stmt) | |
459 | { | |
148aa112 | 460 | /* We may have turned a trapping insn into a non-trapping insn. */ |
461 | if (maybe_clean_or_replace_eh_stmt (stmt, stmt) | |
462 | && tree_purge_dead_eh_edges (bb_for_stmt (stmt))) | |
463 | cfg_changed = true; | |
f2fae51f | 464 | |
35cc02b5 | 465 | if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == ADDR_EXPR) |
466 | recompute_tree_invariant_for_addr_expr (GIMPLE_STMT_OPERAND (stmt, 1)); | |
f2fae51f | 467 | |
de6ed584 | 468 | mark_symbols_for_renaming (stmt); |
148aa112 | 469 | } |
470 | ||
6c01267c | 471 | /* DEF_RHS contains the address of the 0th element in an array. |
472 | USE_STMT uses type of DEF_RHS to compute the address of an | |
291d763b | 473 | arbitrary element within the array. The (variable) byte offset |
474 | of the element is contained in OFFSET. | |
475 | ||
476 | We walk back through the use-def chains of OFFSET to verify that | |
477 | it is indeed computing the offset of an element within the array | |
478 | and extract the index corresponding to the given byte offset. | |
479 | ||
480 | We then try to fold the entire address expression into a form | |
481 | &array[index]. | |
482 | ||
483 | If we are successful, we replace the right hand side of USE_STMT | |
484 | with the new address computation. */ | |
485 | ||
486 | static bool | |
6c01267c | 487 | forward_propagate_addr_into_variable_array_index (tree offset, |
15ec875c | 488 | tree def_rhs, tree use_stmt) |
291d763b | 489 | { |
490 | tree index; | |
491 | ||
1a773ec5 | 492 | /* Try to find an expression for a proper index. This is either |
493 | a multiplication expression by the element size or just the | |
494 | ssa name we came along in case the element size is one. */ | |
6c01267c | 495 | if (integer_onep (TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (def_rhs))))) |
1a773ec5 | 496 | index = offset; |
497 | else | |
498 | { | |
0de36bdb | 499 | /* Get the offset's defining statement. */ |
1a773ec5 | 500 | offset = SSA_NAME_DEF_STMT (offset); |
291d763b | 501 | |
0de36bdb | 502 | /* The statement which defines OFFSET before type conversion |
503 | must be a simple GIMPLE_MODIFY_STMT. */ | |
1a773ec5 | 504 | if (TREE_CODE (offset) != GIMPLE_MODIFY_STMT) |
505 | return false; | |
291d763b | 506 | |
0de36bdb | 507 | /* The RHS of the statement which defines OFFSET must be a |
508 | multiplication of an object by the size of the array elements. | |
509 | This implicitly verifies that the size of the array elements | |
510 | is constant. */ | |
511 | offset = GIMPLE_STMT_OPERAND (offset, 1); | |
1a773ec5 | 512 | if (TREE_CODE (offset) != MULT_EXPR |
513 | || TREE_CODE (TREE_OPERAND (offset, 1)) != INTEGER_CST | |
514 | || !simple_cst_equal (TREE_OPERAND (offset, 1), | |
6c01267c | 515 | TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (def_rhs))))) |
1a773ec5 | 516 | return false; |
291d763b | 517 | |
1a773ec5 | 518 | /* The first operand to the MULT_EXPR is the desired index. */ |
519 | index = TREE_OPERAND (offset, 0); | |
520 | } | |
291d763b | 521 | |
522 | /* Replace the pointer addition with array indexing. */ | |
15ec875c | 523 | GIMPLE_STMT_OPERAND (use_stmt, 1) = unshare_expr (def_rhs); |
35cc02b5 | 524 | TREE_OPERAND (TREE_OPERAND (GIMPLE_STMT_OPERAND (use_stmt, 1), 0), 1) |
525 | = index; | |
291d763b | 526 | |
527 | /* That should have created gimple, so there is no need to | |
528 | record information to undo the propagation. */ | |
148aa112 | 529 | fold_stmt_inplace (use_stmt); |
530 | tidy_after_forward_propagate_addr (use_stmt); | |
291d763b | 531 | return true; |
532 | } | |
533 | ||
15ec875c | 534 | /* NAME is a SSA_NAME representing DEF_RHS which is of the form |
535 | ADDR_EXPR <whatever>. | |
291d763b | 536 | |
3d5cfe81 | 537 | Try to forward propagate the ADDR_EXPR into the use USE_STMT. |
291d763b | 538 | Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF |
3d5cfe81 | 539 | node or for recovery of array indexing from pointer arithmetic. |
6b5a5c42 | 540 | |
6b5a5c42 | 541 | Return true if the propagation was successful (the propagation can |
542 | be not totally successful, yet things may have been changed). */ | |
291d763b | 543 | |
544 | static bool | |
6776dec8 | 545 | forward_propagate_addr_expr_1 (tree name, tree def_rhs, tree use_stmt, |
546 | bool single_use_p) | |
291d763b | 547 | { |
3d5cfe81 | 548 | tree lhs, rhs, array_ref; |
291d763b | 549 | |
631d5db6 | 550 | /* Strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS. |
551 | ADDR_EXPR will not appear on the LHS. */ | |
35cc02b5 | 552 | lhs = GIMPLE_STMT_OPERAND (use_stmt, 0); |
d42c14ae | 553 | while (handled_component_p (lhs)) |
291d763b | 554 | lhs = TREE_OPERAND (lhs, 0); |
555 | ||
15ec875c | 556 | rhs = GIMPLE_STMT_OPERAND (use_stmt, 1); |
557 | ||
291d763b | 558 | /* Now see if the LHS node is an INDIRECT_REF using NAME. If so, |
559 | propagate the ADDR_EXPR into the use of NAME and fold the result. */ | |
560 | if (TREE_CODE (lhs) == INDIRECT_REF && TREE_OPERAND (lhs, 0) == name) | |
561 | { | |
562 | /* This should always succeed in creating gimple, so there is | |
563 | no need to save enough state to undo this propagation. */ | |
15ec875c | 564 | TREE_OPERAND (lhs, 0) = unshare_expr (def_rhs); |
148aa112 | 565 | fold_stmt_inplace (use_stmt); |
566 | tidy_after_forward_propagate_addr (use_stmt); | |
291d763b | 567 | |
d42c14ae | 568 | /* Continue propagating into the RHS. */ |
291d763b | 569 | } |
570 | ||
6776dec8 | 571 | /* Trivial cases. The use statement could be a trivial copy or a |
15ec875c | 572 | useless conversion. Recurse to the uses of the lhs as copyprop does |
573 | not copy through differen variant pointers and FRE does not catch | |
6776dec8 | 574 | all useless conversions. Treat the case of a single-use name and |
575 | a conversion to def_rhs type separate, though. */ | |
576 | else if (TREE_CODE (lhs) == SSA_NAME | |
577 | && (TREE_CODE (rhs) == NOP_EXPR | |
578 | || TREE_CODE (rhs) == CONVERT_EXPR) | |
579 | && TREE_TYPE (rhs) == TREE_TYPE (def_rhs) | |
580 | && single_use_p) | |
581 | { | |
582 | GIMPLE_STMT_OPERAND (use_stmt, 1) = unshare_expr (def_rhs); | |
583 | return true; | |
584 | } | |
15ec875c | 585 | else if ((TREE_CODE (lhs) == SSA_NAME |
586 | && rhs == name) | |
587 | || ((TREE_CODE (rhs) == NOP_EXPR | |
588 | || TREE_CODE (rhs) == CONVERT_EXPR) | |
548044d8 | 589 | && useless_type_conversion_p (TREE_TYPE (rhs), |
590 | TREE_TYPE (def_rhs)))) | |
15ec875c | 591 | return forward_propagate_addr_expr (lhs, def_rhs); |
592 | ||
631d5db6 | 593 | /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR |
594 | nodes from the RHS. */ | |
d42c14ae | 595 | while (handled_component_p (rhs) |
631d5db6 | 596 | || TREE_CODE (rhs) == ADDR_EXPR) |
291d763b | 597 | rhs = TREE_OPERAND (rhs, 0); |
598 | ||
599 | /* Now see if the RHS node is an INDIRECT_REF using NAME. If so, | |
600 | propagate the ADDR_EXPR into the use of NAME and fold the result. */ | |
601 | if (TREE_CODE (rhs) == INDIRECT_REF && TREE_OPERAND (rhs, 0) == name) | |
602 | { | |
603 | /* This should always succeed in creating gimple, so there is | |
604 | no need to save enough state to undo this propagation. */ | |
15ec875c | 605 | TREE_OPERAND (rhs, 0) = unshare_expr (def_rhs); |
148aa112 | 606 | fold_stmt_inplace (use_stmt); |
607 | tidy_after_forward_propagate_addr (use_stmt); | |
291d763b | 608 | return true; |
609 | } | |
610 | ||
611 | /* The remaining cases are all for turning pointer arithmetic into | |
612 | array indexing. They only apply when we have the address of | |
613 | element zero in an array. If that is not the case then there | |
614 | is nothing to do. */ | |
15ec875c | 615 | array_ref = TREE_OPERAND (def_rhs, 0); |
291d763b | 616 | if (TREE_CODE (array_ref) != ARRAY_REF |
617 | || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE | |
618 | || !integer_zerop (TREE_OPERAND (array_ref, 1))) | |
619 | return false; | |
620 | ||
0de36bdb | 621 | /* If the use of the ADDR_EXPR is not a POINTER_PLUS_EXPR, there |
291d763b | 622 | is nothing to do. */ |
0de36bdb | 623 | if (TREE_CODE (rhs) != POINTER_PLUS_EXPR) |
291d763b | 624 | return false; |
625 | ||
0de36bdb | 626 | /* Try to optimize &x[0] p+ C where C is a multiple of the size |
291d763b | 627 | of the elements in X into &x[C/element size]. */ |
628 | if (TREE_OPERAND (rhs, 0) == name | |
629 | && TREE_CODE (TREE_OPERAND (rhs, 1)) == INTEGER_CST) | |
630 | { | |
631 | tree orig = unshare_expr (rhs); | |
15ec875c | 632 | TREE_OPERAND (rhs, 0) = unshare_expr (def_rhs); |
291d763b | 633 | |
634 | /* If folding succeeds, then we have just exposed new variables | |
635 | in USE_STMT which will need to be renamed. If folding fails, | |
636 | then we need to put everything back the way it was. */ | |
148aa112 | 637 | if (fold_stmt_inplace (use_stmt)) |
291d763b | 638 | { |
148aa112 | 639 | tidy_after_forward_propagate_addr (use_stmt); |
291d763b | 640 | return true; |
641 | } | |
642 | else | |
643 | { | |
35cc02b5 | 644 | GIMPLE_STMT_OPERAND (use_stmt, 1) = orig; |
291d763b | 645 | update_stmt (use_stmt); |
646 | return false; | |
647 | } | |
648 | } | |
649 | ||
0de36bdb | 650 | /* Try to optimize &x[0] p+ OFFSET where OFFSET is defined by |
291d763b | 651 | converting a multiplication of an index by the size of the |
652 | array elements, then the result is converted into the proper | |
653 | type for the arithmetic. */ | |
654 | if (TREE_OPERAND (rhs, 0) == name | |
655 | && TREE_CODE (TREE_OPERAND (rhs, 1)) == SSA_NAME | |
656 | /* Avoid problems with IVopts creating PLUS_EXPRs with a | |
657 | different type than their operands. */ | |
c8ca3ee7 | 658 | && useless_type_conversion_p (TREE_TYPE (rhs), TREE_TYPE (name))) |
291d763b | 659 | { |
6b5a5c42 | 660 | bool res; |
6b5a5c42 | 661 | |
0de36bdb | 662 | res = forward_propagate_addr_into_variable_array_index (TREE_OPERAND (rhs, 1), |
15ec875c | 663 | def_rhs, use_stmt); |
6b5a5c42 | 664 | return res; |
291d763b | 665 | } |
666 | return false; | |
667 | } | |
668 | ||
3d5cfe81 | 669 | /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>. |
670 | ||
671 | Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME. | |
672 | Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF | |
673 | node or for recovery of array indexing from pointer arithmetic. | |
674 | Returns true, if all uses have been propagated into. */ | |
675 | ||
676 | static bool | |
15ec875c | 677 | forward_propagate_addr_expr (tree name, tree rhs) |
3d5cfe81 | 678 | { |
15ec875c | 679 | int stmt_loop_depth = bb_for_stmt (SSA_NAME_DEF_STMT (name))->loop_depth; |
3d5cfe81 | 680 | imm_use_iterator iter; |
09aca5bc | 681 | tree use_stmt; |
3d5cfe81 | 682 | bool all = true; |
6776dec8 | 683 | bool single_use_p = has_single_use (name); |
3d5cfe81 | 684 | |
09aca5bc | 685 | FOR_EACH_IMM_USE_STMT (use_stmt, iter, name) |
3d5cfe81 | 686 | { |
c96420f8 | 687 | bool result; |
3d5cfe81 | 688 | |
689 | /* If the use is not in a simple assignment statement, then | |
690 | there is nothing we can do. */ | |
35cc02b5 | 691 | if (TREE_CODE (use_stmt) != GIMPLE_MODIFY_STMT) |
3d5cfe81 | 692 | { |
693 | all = false; | |
694 | continue; | |
695 | } | |
696 | ||
a540e2fe | 697 | /* If the use is in a deeper loop nest, then we do not want |
3d5cfe81 | 698 | to propagate the ADDR_EXPR into the loop as that is likely |
699 | adding expression evaluations into the loop. */ | |
700 | if (bb_for_stmt (use_stmt)->loop_depth > stmt_loop_depth) | |
701 | { | |
702 | all = false; | |
703 | continue; | |
704 | } | |
a540e2fe | 705 | |
de6ed584 | 706 | push_stmt_changes (&use_stmt); |
707 | ||
6776dec8 | 708 | result = forward_propagate_addr_expr_1 (name, rhs, use_stmt, |
709 | single_use_p); | |
c96420f8 | 710 | all &= result; |
de6ed584 | 711 | |
712 | pop_stmt_changes (&use_stmt); | |
15ec875c | 713 | |
714 | /* Remove intermediate now unused copy and conversion chains. */ | |
715 | if (result | |
716 | && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 0)) == SSA_NAME | |
717 | && (TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == SSA_NAME | |
718 | || TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == NOP_EXPR | |
719 | || TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == CONVERT_EXPR)) | |
720 | { | |
721 | block_stmt_iterator bsi = bsi_for_stmt (use_stmt); | |
722 | release_defs (use_stmt); | |
723 | bsi_remove (&bsi, true); | |
724 | } | |
3d5cfe81 | 725 | } |
726 | ||
727 | return all; | |
728 | } | |
729 | ||
5adc1066 | 730 | /* Forward propagate the comparison COND defined in STMT like |
731 | cond_1 = x CMP y to uses of the form | |
732 | a_1 = (T')cond_1 | |
733 | a_1 = !cond_1 | |
734 | a_1 = cond_1 != 0 | |
735 | Returns true if stmt is now unused. */ | |
736 | ||
737 | static bool | |
738 | forward_propagate_comparison (tree cond, tree stmt) | |
739 | { | |
740 | tree name = GIMPLE_STMT_OPERAND (stmt, 0); | |
741 | tree use_stmt, tmp = NULL_TREE; | |
742 | ||
743 | /* Don't propagate ssa names that occur in abnormal phis. */ | |
744 | if ((TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME | |
745 | && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (cond, 0))) | |
746 | || (TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME | |
747 | && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (cond, 1)))) | |
748 | return false; | |
749 | ||
750 | /* Do not un-cse comparisons. But propagate through copies. */ | |
751 | use_stmt = get_prop_dest_stmt (name, &name); | |
752 | if (use_stmt == NULL_TREE) | |
753 | return false; | |
754 | ||
755 | /* Conversion of the condition result to another integral type. */ | |
756 | if (TREE_CODE (use_stmt) == GIMPLE_MODIFY_STMT | |
757 | && (TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == CONVERT_EXPR | |
758 | || TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == NOP_EXPR | |
759 | || COMPARISON_CLASS_P (GIMPLE_STMT_OPERAND (use_stmt, 1)) | |
760 | || TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == TRUTH_NOT_EXPR) | |
761 | && INTEGRAL_TYPE_P (TREE_TYPE (GIMPLE_STMT_OPERAND (use_stmt, 0)))) | |
762 | { | |
763 | tree lhs = GIMPLE_STMT_OPERAND (use_stmt, 0); | |
764 | tree rhs = GIMPLE_STMT_OPERAND (use_stmt, 1); | |
765 | ||
766 | /* We can propagate the condition into a conversion. */ | |
767 | if (TREE_CODE (rhs) == CONVERT_EXPR | |
768 | || TREE_CODE (rhs) == NOP_EXPR) | |
769 | { | |
770 | /* Avoid using fold here as that may create a COND_EXPR with | |
771 | non-boolean condition as canonical form. */ | |
772 | tmp = build2 (TREE_CODE (cond), TREE_TYPE (lhs), | |
773 | TREE_OPERAND (cond, 0), TREE_OPERAND (cond, 1)); | |
774 | } | |
775 | /* We can propagate the condition into X op CST where op | |
776 | is EQ_EXRP or NE_EXPR and CST is either one or zero. */ | |
777 | else if (COMPARISON_CLASS_P (rhs) | |
778 | && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME | |
779 | && TREE_CODE (TREE_OPERAND (rhs, 1)) == INTEGER_CST) | |
780 | { | |
781 | enum tree_code code = TREE_CODE (rhs); | |
782 | tree cst = TREE_OPERAND (rhs, 1); | |
783 | ||
784 | tmp = combine_cond_expr_cond (code, TREE_TYPE (lhs), | |
785 | fold_convert (TREE_TYPE (cst), cond), | |
786 | cst, false); | |
787 | if (tmp == NULL_TREE) | |
788 | return false; | |
789 | } | |
790 | /* We can propagate the condition into a statement that | |
791 | computes the logical negation of the comparison result. */ | |
792 | else if (TREE_CODE (rhs) == TRUTH_NOT_EXPR) | |
793 | { | |
794 | tree type = TREE_TYPE (TREE_OPERAND (cond, 0)); | |
795 | bool nans = HONOR_NANS (TYPE_MODE (type)); | |
796 | enum tree_code code; | |
797 | code = invert_tree_comparison (TREE_CODE (cond), nans); | |
798 | if (code == ERROR_MARK) | |
799 | return false; | |
800 | ||
801 | tmp = build2 (code, TREE_TYPE (lhs), TREE_OPERAND (cond, 0), | |
802 | TREE_OPERAND (cond, 1)); | |
803 | } | |
804 | else | |
805 | return false; | |
806 | ||
807 | GIMPLE_STMT_OPERAND (use_stmt, 1) = unshare_expr (tmp); | |
808 | update_stmt (use_stmt); | |
809 | ||
810 | /* Remove defining statements. */ | |
811 | remove_prop_source_from_use (name, stmt); | |
812 | ||
813 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
814 | { | |
815 | fprintf (dump_file, " Replaced '"); | |
816 | print_generic_expr (dump_file, rhs, dump_flags); | |
817 | fprintf (dump_file, "' with '"); | |
818 | print_generic_expr (dump_file, tmp, dump_flags); | |
819 | fprintf (dump_file, "'\n"); | |
820 | } | |
821 | ||
822 | return true; | |
823 | } | |
824 | ||
825 | return false; | |
826 | } | |
827 | ||
3a938499 | 828 | /* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y. |
829 | If so, we can change STMT into lhs = y which can later be copy | |
830 | propagated. Similarly for negation. | |
831 | ||
832 | This could trivially be formulated as a forward propagation | |
833 | to immediate uses. However, we already had an implementation | |
834 | from DOM which used backward propagation via the use-def links. | |
835 | ||
836 | It turns out that backward propagation is actually faster as | |
837 | there's less work to do for each NOT/NEG expression we find. | |
838 | Backwards propagation needs to look at the statement in a single | |
839 | backlink. Forward propagation needs to look at potentially more | |
840 | than one forward link. */ | |
841 | ||
842 | static void | |
843 | simplify_not_neg_expr (tree stmt) | |
844 | { | |
35cc02b5 | 845 | tree rhs = GIMPLE_STMT_OPERAND (stmt, 1); |
3a938499 | 846 | tree rhs_def_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0)); |
847 | ||
848 | /* See if the RHS_DEF_STMT has the same form as our statement. */ | |
35cc02b5 | 849 | if (TREE_CODE (rhs_def_stmt) == GIMPLE_MODIFY_STMT |
850 | && TREE_CODE (GIMPLE_STMT_OPERAND (rhs_def_stmt, 1)) == TREE_CODE (rhs)) | |
3a938499 | 851 | { |
35cc02b5 | 852 | tree rhs_def_operand = |
853 | TREE_OPERAND (GIMPLE_STMT_OPERAND (rhs_def_stmt, 1), 0); | |
3a938499 | 854 | |
855 | /* Verify that RHS_DEF_OPERAND is a suitable SSA_NAME. */ | |
856 | if (TREE_CODE (rhs_def_operand) == SSA_NAME | |
857 | && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand)) | |
858 | { | |
35cc02b5 | 859 | GIMPLE_STMT_OPERAND (stmt, 1) = rhs_def_operand; |
3a938499 | 860 | update_stmt (stmt); |
861 | } | |
862 | } | |
863 | } | |
3d5cfe81 | 864 | |
b5860aba | 865 | /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of |
866 | the condition which we may be able to optimize better. */ | |
867 | ||
868 | static void | |
869 | simplify_switch_expr (tree stmt) | |
870 | { | |
871 | tree cond = SWITCH_COND (stmt); | |
872 | tree def, to, ti; | |
873 | ||
874 | /* The optimization that we really care about is removing unnecessary | |
875 | casts. That will let us do much better in propagating the inferred | |
876 | constant at the switch target. */ | |
877 | if (TREE_CODE (cond) == SSA_NAME) | |
878 | { | |
879 | def = SSA_NAME_DEF_STMT (cond); | |
35cc02b5 | 880 | if (TREE_CODE (def) == GIMPLE_MODIFY_STMT) |
b5860aba | 881 | { |
35cc02b5 | 882 | def = GIMPLE_STMT_OPERAND (def, 1); |
b5860aba | 883 | if (TREE_CODE (def) == NOP_EXPR) |
884 | { | |
885 | int need_precision; | |
886 | bool fail; | |
887 | ||
888 | def = TREE_OPERAND (def, 0); | |
889 | ||
890 | #ifdef ENABLE_CHECKING | |
891 | /* ??? Why was Jeff testing this? We are gimple... */ | |
892 | gcc_assert (is_gimple_val (def)); | |
893 | #endif | |
894 | ||
895 | to = TREE_TYPE (cond); | |
896 | ti = TREE_TYPE (def); | |
897 | ||
898 | /* If we have an extension that preserves value, then we | |
899 | can copy the source value into the switch. */ | |
900 | ||
901 | need_precision = TYPE_PRECISION (ti); | |
902 | fail = false; | |
c5237b8b | 903 | if (! INTEGRAL_TYPE_P (ti)) |
904 | fail = true; | |
905 | else if (TYPE_UNSIGNED (to) && !TYPE_UNSIGNED (ti)) | |
b5860aba | 906 | fail = true; |
907 | else if (!TYPE_UNSIGNED (to) && TYPE_UNSIGNED (ti)) | |
908 | need_precision += 1; | |
909 | if (TYPE_PRECISION (to) < need_precision) | |
910 | fail = true; | |
911 | ||
912 | if (!fail) | |
913 | { | |
914 | SWITCH_COND (stmt) = def; | |
915 | update_stmt (stmt); | |
916 | } | |
917 | } | |
918 | } | |
919 | } | |
920 | } | |
921 | ||
4ee9c684 | 922 | /* Main entry point for the forward propagation optimizer. */ |
923 | ||
2a1990e9 | 924 | static unsigned int |
4ee9c684 | 925 | tree_ssa_forward_propagate_single_use_vars (void) |
926 | { | |
f5c8cff5 | 927 | basic_block bb; |
c96420f8 | 928 | unsigned int todoflags = 0; |
4ee9c684 | 929 | |
148aa112 | 930 | cfg_changed = false; |
931 | ||
f5c8cff5 | 932 | FOR_EACH_BB (bb) |
933 | { | |
291d763b | 934 | block_stmt_iterator bsi; |
935 | ||
936 | /* Note we update BSI within the loop as necessary. */ | |
937 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); ) | |
938 | { | |
939 | tree stmt = bsi_stmt (bsi); | |
940 | ||
941 | /* If this statement sets an SSA_NAME to an address, | |
942 | try to propagate the address into the uses of the SSA_NAME. */ | |
35cc02b5 | 943 | if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT) |
291d763b | 944 | { |
35cc02b5 | 945 | tree lhs = GIMPLE_STMT_OPERAND (stmt, 0); |
946 | tree rhs = GIMPLE_STMT_OPERAND (stmt, 1); | |
3a938499 | 947 | |
948 | ||
949 | if (TREE_CODE (lhs) != SSA_NAME) | |
950 | { | |
951 | bsi_next (&bsi); | |
952 | continue; | |
953 | } | |
954 | ||
30fde358 | 955 | if (TREE_CODE (rhs) == ADDR_EXPR |
956 | /* We can also disregard changes in CV qualifiers for | |
957 | the dereferenced value. */ | |
958 | || ((TREE_CODE (rhs) == NOP_EXPR | |
959 | || TREE_CODE (rhs) == CONVERT_EXPR) | |
960 | && TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR | |
961 | && POINTER_TYPE_P (TREE_TYPE (rhs)) | |
cbb0f5f6 | 962 | && types_compatible_p (TREE_TYPE (TREE_TYPE (TREE_OPERAND (rhs, 0))), |
963 | TREE_TYPE (TREE_TYPE (rhs))))) | |
3a938499 | 964 | { |
15ec875c | 965 | if (forward_propagate_addr_expr (lhs, rhs)) |
24838d3f | 966 | { |
967 | release_defs (stmt); | |
ea0ab927 | 968 | todoflags |= TODO_remove_unused_locals; |
24838d3f | 969 | bsi_remove (&bsi, true); |
970 | } | |
3a938499 | 971 | else |
972 | bsi_next (&bsi); | |
973 | } | |
974 | else if ((TREE_CODE (rhs) == BIT_NOT_EXPR | |
975 | || TREE_CODE (rhs) == NEGATE_EXPR) | |
976 | && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME) | |
977 | { | |
978 | simplify_not_neg_expr (stmt); | |
979 | bsi_next (&bsi); | |
980 | } | |
ec0fa513 | 981 | else if (TREE_CODE (rhs) == COND_EXPR) |
982 | { | |
4c580c8c | 983 | int did_something; |
d080be9e | 984 | fold_defer_overflow_warnings (); |
985 | did_something = forward_propagate_into_cond (rhs, stmt); | |
4c580c8c | 986 | if (did_something == 2) |
987 | cfg_changed = true; | |
d080be9e | 988 | fold_undefer_overflow_warnings (!TREE_NO_WARNING (rhs) |
989 | && did_something, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL); | |
ec0fa513 | 990 | bsi_next (&bsi); |
991 | } | |
5adc1066 | 992 | else if (COMPARISON_CLASS_P (rhs)) |
993 | { | |
994 | if (forward_propagate_comparison (rhs, stmt)) | |
995 | { | |
996 | release_defs (stmt); | |
997 | todoflags |= TODO_remove_unused_locals; | |
998 | bsi_remove (&bsi, true); | |
999 | } | |
1000 | else | |
1001 | bsi_next (&bsi); | |
1002 | } | |
291d763b | 1003 | else |
1004 | bsi_next (&bsi); | |
1005 | } | |
b5860aba | 1006 | else if (TREE_CODE (stmt) == SWITCH_EXPR) |
1007 | { | |
1008 | simplify_switch_expr (stmt); | |
1009 | bsi_next (&bsi); | |
1010 | } | |
291d763b | 1011 | else if (TREE_CODE (stmt) == COND_EXPR) |
1012 | { | |
4c580c8c | 1013 | int did_something; |
d080be9e | 1014 | fold_defer_overflow_warnings (); |
1015 | did_something = forward_propagate_into_cond (stmt, stmt); | |
4c580c8c | 1016 | if (did_something == 2) |
1017 | cfg_changed = true; | |
72c59a18 | 1018 | fold_undefer_overflow_warnings (did_something, stmt, |
d080be9e | 1019 | WARN_STRICT_OVERFLOW_CONDITIONAL); |
291d763b | 1020 | bsi_next (&bsi); |
1021 | } | |
1022 | else | |
1023 | bsi_next (&bsi); | |
1024 | } | |
f5c8cff5 | 1025 | } |
148aa112 | 1026 | |
1027 | if (cfg_changed) | |
6fa78c7b | 1028 | todoflags |= TODO_cleanup_cfg; |
c96420f8 | 1029 | return todoflags; |
4ee9c684 | 1030 | } |
1031 | ||
1032 | ||
1033 | static bool | |
1034 | gate_forwprop (void) | |
1035 | { | |
1036 | return 1; | |
1037 | } | |
1038 | ||
1039 | struct tree_opt_pass pass_forwprop = { | |
1040 | "forwprop", /* name */ | |
1041 | gate_forwprop, /* gate */ | |
1042 | tree_ssa_forward_propagate_single_use_vars, /* execute */ | |
1043 | NULL, /* sub */ | |
1044 | NULL, /* next */ | |
1045 | 0, /* static_pass_number */ | |
1046 | TV_TREE_FORWPROP, /* tv_id */ | |
49290934 | 1047 | PROP_cfg | PROP_ssa, /* properties_required */ |
4ee9c684 | 1048 | 0, /* properties_provided */ |
b6246c40 | 1049 | 0, /* properties_destroyed */ |
4ee9c684 | 1050 | 0, /* todo_flags_start */ |
de6ed584 | 1051 | TODO_dump_func |
abd433a7 | 1052 | | TODO_ggc_collect |
de6ed584 | 1053 | | TODO_update_ssa |
1054 | | TODO_verify_ssa, /* todo_flags_finish */ | |
1055 | 0 /* letter */ | |
4ee9c684 | 1056 | }; |
37361b38 | 1057 | |
1058 | ||
1059 | /* Structure to keep track of the value of a dereferenced PHI result | |
1060 | and the set of virtual operands used for that dereference. */ | |
1061 | ||
1062 | struct phiprop_d | |
1063 | { | |
1064 | tree value; | |
1065 | tree vop_stmt; | |
1066 | }; | |
1067 | ||
1068 | /* Verify if the value recorded for NAME in PHIVN is still valid at | |
1069 | the start of basic block BB. */ | |
1070 | ||
1071 | static bool | |
1072 | phivn_valid_p (struct phiprop_d *phivn, tree name, basic_block bb) | |
1073 | { | |
1074 | tree vop_stmt = phivn[SSA_NAME_VERSION (name)].vop_stmt; | |
1075 | ssa_op_iter ui; | |
1076 | tree vuse; | |
1077 | ||
1078 | /* The def stmts of all virtual uses need to be post-dominated | |
1079 | by bb. */ | |
1080 | FOR_EACH_SSA_TREE_OPERAND (vuse, vop_stmt, ui, SSA_OP_VUSE) | |
1081 | { | |
1082 | tree use_stmt; | |
1083 | imm_use_iterator ui2; | |
1084 | bool ok = true; | |
1085 | ||
1086 | FOR_EACH_IMM_USE_STMT (use_stmt, ui2, vuse) | |
1087 | { | |
1088 | /* If BB does not dominate a VDEF, the value is invalid. */ | |
1089 | if (((TREE_CODE (use_stmt) == GIMPLE_MODIFY_STMT | |
1090 | && !ZERO_SSA_OPERANDS (use_stmt, SSA_OP_VDEF)) | |
1091 | || TREE_CODE (use_stmt) == PHI_NODE) | |
1092 | && !dominated_by_p (CDI_DOMINATORS, bb_for_stmt (use_stmt), bb)) | |
1093 | { | |
1094 | ok = false; | |
1095 | BREAK_FROM_IMM_USE_STMT (ui2); | |
1096 | } | |
1097 | } | |
1098 | if (!ok) | |
1099 | return false; | |
1100 | } | |
1101 | ||
1102 | return true; | |
1103 | } | |
1104 | ||
1105 | /* Insert a new phi node for the dereference of PHI at basic_block | |
1106 | BB with the virtual operands from USE_STMT. */ | |
1107 | ||
1108 | static tree | |
1109 | phiprop_insert_phi (basic_block bb, tree phi, tree use_stmt, | |
1110 | struct phiprop_d *phivn, size_t n) | |
1111 | { | |
1112 | tree res, new_phi; | |
1113 | edge_iterator ei; | |
1114 | edge e; | |
1115 | ||
1116 | /* Build a new PHI node to replace the definition of | |
1117 | the indirect reference lhs. */ | |
1118 | res = GIMPLE_STMT_OPERAND (use_stmt, 0); | |
1119 | SSA_NAME_DEF_STMT (res) = new_phi = create_phi_node (res, bb); | |
1120 | ||
1121 | /* Add PHI arguments for each edge inserting loads of the | |
1122 | addressable operands. */ | |
1123 | FOR_EACH_EDGE (e, ei, bb->preds) | |
1124 | { | |
1125 | tree old_arg, new_var, tmp; | |
1126 | ||
1127 | old_arg = PHI_ARG_DEF_FROM_EDGE (phi, e); | |
1128 | while (TREE_CODE (old_arg) == SSA_NAME | |
1129 | && (SSA_NAME_VERSION (old_arg) >= n | |
1130 | || phivn[SSA_NAME_VERSION (old_arg)].value == NULL_TREE)) | |
1131 | { | |
1132 | tree def_stmt = SSA_NAME_DEF_STMT (old_arg); | |
1133 | old_arg = GIMPLE_STMT_OPERAND (def_stmt, 1); | |
1134 | } | |
1135 | ||
1136 | if (TREE_CODE (old_arg) == SSA_NAME) | |
310d2511 | 1137 | /* Reuse a formerly created dereference. */ |
37361b38 | 1138 | new_var = phivn[SSA_NAME_VERSION (old_arg)].value; |
1139 | else | |
1140 | { | |
1141 | old_arg = TREE_OPERAND (old_arg, 0); | |
1142 | new_var = create_tmp_var (TREE_TYPE (old_arg), NULL); | |
1143 | tmp = build2 (GIMPLE_MODIFY_STMT, void_type_node, | |
1144 | NULL_TREE, unshare_expr (old_arg)); | |
1145 | if (TREE_CODE (TREE_TYPE (old_arg)) == COMPLEX_TYPE | |
1146 | || TREE_CODE (TREE_TYPE (old_arg)) == VECTOR_TYPE) | |
1147 | DECL_GIMPLE_REG_P (new_var) = 1; | |
1148 | add_referenced_var (new_var); | |
1149 | new_var = make_ssa_name (new_var, tmp); | |
1150 | GIMPLE_STMT_OPERAND (tmp, 0) = new_var; | |
1151 | ||
1152 | bsi_insert_on_edge (e, tmp); | |
1153 | ||
1154 | update_stmt (tmp); | |
1155 | mark_symbols_for_renaming (tmp); | |
1156 | } | |
1157 | ||
1158 | add_phi_arg (new_phi, new_var, e); | |
1159 | } | |
1160 | ||
1161 | update_stmt (new_phi); | |
1162 | ||
1163 | return res; | |
1164 | } | |
1165 | ||
1166 | /* Propagate between the phi node arguments of PHI in BB and phi result | |
1167 | users. For now this matches | |
1168 | # p_2 = PHI <&x, &y> | |
1169 | <Lx>:; | |
1170 | p_3 = p_2; | |
1171 | z_2 = *p_3; | |
1172 | and converts it to | |
1173 | # z_2 = PHI <x, y> | |
1174 | <Lx>:; | |
1175 | Returns true if a transformation was done and edge insertions | |
1176 | need to be committed. Global data PHIVN and N is used to track | |
1177 | past transformation results. We need to be especially careful here | |
1178 | with aliasing issues as we are moving memory reads. */ | |
1179 | ||
1180 | static bool | |
1181 | propagate_with_phi (basic_block bb, tree phi, struct phiprop_d *phivn, size_t n) | |
1182 | { | |
1183 | tree ptr = PHI_RESULT (phi); | |
1184 | tree use_stmt, res = NULL_TREE; | |
1185 | block_stmt_iterator bsi; | |
1186 | imm_use_iterator ui; | |
1187 | use_operand_p arg_p, use; | |
1188 | ssa_op_iter i; | |
1189 | bool phi_inserted; | |
1190 | ||
1191 | if (MTAG_P (SSA_NAME_VAR (ptr)) | |
1192 | || !POINTER_TYPE_P (TREE_TYPE (ptr)) | |
1193 | || !is_gimple_reg_type (TREE_TYPE (TREE_TYPE (ptr)))) | |
1194 | return false; | |
1195 | ||
1196 | /* Check if we can "cheaply" dereference all phi arguments. */ | |
1197 | FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE) | |
1198 | { | |
1199 | tree arg = USE_FROM_PTR (arg_p); | |
1200 | /* Walk the ssa chain until we reach a ssa name we already | |
1201 | created a value for or we reach a definition of the form | |
1202 | ssa_name_n = &var; */ | |
1203 | while (TREE_CODE (arg) == SSA_NAME | |
1204 | && !SSA_NAME_IS_DEFAULT_DEF (arg) | |
1205 | && (SSA_NAME_VERSION (arg) >= n | |
1206 | || phivn[SSA_NAME_VERSION (arg)].value == NULL_TREE)) | |
1207 | { | |
1208 | tree def_stmt = SSA_NAME_DEF_STMT (arg); | |
1209 | if (TREE_CODE (def_stmt) != GIMPLE_MODIFY_STMT) | |
1210 | return false; | |
1211 | arg = GIMPLE_STMT_OPERAND (def_stmt, 1); | |
1212 | } | |
1213 | if ((TREE_CODE (arg) != ADDR_EXPR | |
1214 | /* Avoid to have to decay *&a to a[0] later. */ | |
1215 | || !is_gimple_reg_type (TREE_TYPE (TREE_OPERAND (arg, 0)))) | |
1216 | && !(TREE_CODE (arg) == SSA_NAME | |
1217 | && phivn[SSA_NAME_VERSION (arg)].value != NULL_TREE | |
1218 | && phivn_valid_p (phivn, arg, bb))) | |
1219 | return false; | |
1220 | } | |
1221 | ||
1222 | /* Find a dereferencing use. First follow (single use) ssa | |
1223 | copy chains for ptr. */ | |
1224 | while (single_imm_use (ptr, &use, &use_stmt) | |
1225 | && TREE_CODE (use_stmt) == GIMPLE_MODIFY_STMT | |
1226 | && GIMPLE_STMT_OPERAND (use_stmt, 1) == ptr | |
1227 | && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 0)) == SSA_NAME) | |
1228 | ptr = GIMPLE_STMT_OPERAND (use_stmt, 0); | |
1229 | ||
1230 | /* Replace the first dereference of *ptr if there is one and if we | |
1231 | can move the loads to the place of the ptr phi node. */ | |
1232 | phi_inserted = false; | |
1233 | FOR_EACH_IMM_USE_STMT (use_stmt, ui, ptr) | |
1234 | { | |
1235 | ssa_op_iter ui2; | |
1236 | tree vuse; | |
1237 | ||
1238 | /* Check whether this is a load of *ptr. */ | |
1239 | if (!(TREE_CODE (use_stmt) == GIMPLE_MODIFY_STMT | |
1240 | && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 0)) == SSA_NAME | |
1241 | && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == INDIRECT_REF | |
1242 | && TREE_OPERAND (GIMPLE_STMT_OPERAND (use_stmt, 1), 0) == ptr | |
1243 | /* We cannot replace a load that may throw or is volatile. */ | |
1244 | && !tree_can_throw_internal (use_stmt))) | |
1245 | continue; | |
1246 | ||
1247 | /* Check if we can move the loads. The def stmts of all virtual uses | |
1248 | need to be post-dominated by bb. */ | |
1249 | FOR_EACH_SSA_TREE_OPERAND (vuse, use_stmt, ui2, SSA_OP_VUSE) | |
1250 | { | |
1251 | tree def_stmt = SSA_NAME_DEF_STMT (vuse); | |
1252 | if (!SSA_NAME_IS_DEFAULT_DEF (vuse) | |
1253 | && (bb_for_stmt (def_stmt) == bb | |
1254 | || !dominated_by_p (CDI_DOMINATORS, | |
1255 | bb, bb_for_stmt (def_stmt)))) | |
1256 | goto next; | |
1257 | } | |
1258 | ||
1259 | /* Found a proper dereference. Insert a phi node if this | |
1260 | is the first load transformation. */ | |
1261 | if (!phi_inserted) | |
1262 | { | |
1263 | res = phiprop_insert_phi (bb, phi, use_stmt, phivn, n); | |
1264 | ||
1265 | /* Remember the value we created for *ptr. */ | |
1266 | phivn[SSA_NAME_VERSION (ptr)].value = res; | |
1267 | phivn[SSA_NAME_VERSION (ptr)].vop_stmt = use_stmt; | |
1268 | ||
1269 | /* Remove old stmt. The phi is taken care of by DCE, if we | |
1270 | want to delete it here we also have to delete all intermediate | |
1271 | copies. */ | |
1272 | bsi = bsi_for_stmt (use_stmt); | |
1273 | bsi_remove (&bsi, 0); | |
1274 | ||
1275 | phi_inserted = true; | |
1276 | } | |
1277 | else | |
1278 | { | |
1279 | /* Further replacements are easy, just make a copy out of the | |
1280 | load. */ | |
1281 | GIMPLE_STMT_OPERAND (use_stmt, 1) = res; | |
1282 | update_stmt (use_stmt); | |
1283 | } | |
1284 | ||
1285 | next:; | |
1286 | /* Continue searching for a proper dereference. */ | |
1287 | } | |
1288 | ||
1289 | return phi_inserted; | |
1290 | } | |
1291 | ||
1292 | /* Helper walking the dominator tree starting from BB and processing | |
1293 | phi nodes with global data PHIVN and N. */ | |
1294 | ||
1295 | static bool | |
1296 | tree_ssa_phiprop_1 (basic_block bb, struct phiprop_d *phivn, size_t n) | |
1297 | { | |
1298 | bool did_something = false; | |
1299 | basic_block son; | |
1300 | tree phi; | |
1301 | ||
1302 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) | |
1303 | did_something |= propagate_with_phi (bb, phi, phivn, n); | |
1304 | ||
1305 | for (son = first_dom_son (CDI_DOMINATORS, bb); | |
1306 | son; | |
1307 | son = next_dom_son (CDI_DOMINATORS, son)) | |
1308 | did_something |= tree_ssa_phiprop_1 (son, phivn, n); | |
1309 | ||
1310 | return did_something; | |
1311 | } | |
1312 | ||
1313 | /* Main entry for phiprop pass. */ | |
1314 | ||
1315 | static unsigned int | |
1316 | tree_ssa_phiprop (void) | |
1317 | { | |
1318 | struct phiprop_d *phivn; | |
1319 | ||
1320 | calculate_dominance_info (CDI_DOMINATORS); | |
1321 | ||
1322 | phivn = XCNEWVEC (struct phiprop_d, num_ssa_names); | |
1323 | ||
1324 | if (tree_ssa_phiprop_1 (ENTRY_BLOCK_PTR, phivn, num_ssa_names)) | |
1325 | bsi_commit_edge_inserts (); | |
1326 | ||
1327 | free (phivn); | |
1328 | ||
1329 | return 0; | |
1330 | } | |
1331 | ||
1332 | static bool | |
1333 | gate_phiprop (void) | |
1334 | { | |
1335 | return 1; | |
1336 | } | |
1337 | ||
1338 | struct tree_opt_pass pass_phiprop = { | |
1339 | "phiprop", /* name */ | |
1340 | gate_phiprop, /* gate */ | |
1341 | tree_ssa_phiprop, /* execute */ | |
1342 | NULL, /* sub */ | |
1343 | NULL, /* next */ | |
1344 | 0, /* static_pass_number */ | |
1345 | TV_TREE_FORWPROP, /* tv_id */ | |
1346 | PROP_cfg | PROP_ssa, /* properties_required */ | |
1347 | 0, /* properties_provided */ | |
1348 | 0, /* properties_destroyed */ | |
1349 | 0, /* todo_flags_start */ | |
1350 | TODO_dump_func | |
1351 | | TODO_ggc_collect | |
1352 | | TODO_update_ssa | |
1353 | | TODO_verify_ssa, /* todo_flags_finish */ | |
1354 | 0 /* letter */ | |
1355 | }; |