]>
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; |
9481f629 | 688 | tree use_rhs; |
3d5cfe81 | 689 | |
690 | /* If the use is not in a simple assignment statement, then | |
691 | there is nothing we can do. */ | |
35cc02b5 | 692 | if (TREE_CODE (use_stmt) != GIMPLE_MODIFY_STMT) |
3d5cfe81 | 693 | { |
694 | all = false; | |
695 | continue; | |
696 | } | |
697 | ||
a540e2fe | 698 | /* If the use is in a deeper loop nest, then we do not want |
3d5cfe81 | 699 | to propagate the ADDR_EXPR into the loop as that is likely |
700 | adding expression evaluations into the loop. */ | |
701 | if (bb_for_stmt (use_stmt)->loop_depth > stmt_loop_depth) | |
702 | { | |
703 | all = false; | |
704 | continue; | |
705 | } | |
a540e2fe | 706 | |
de6ed584 | 707 | push_stmt_changes (&use_stmt); |
708 | ||
6776dec8 | 709 | result = forward_propagate_addr_expr_1 (name, rhs, use_stmt, |
710 | single_use_p); | |
c96420f8 | 711 | all &= result; |
de6ed584 | 712 | |
713 | pop_stmt_changes (&use_stmt); | |
15ec875c | 714 | |
715 | /* Remove intermediate now unused copy and conversion chains. */ | |
9481f629 | 716 | use_rhs = GIMPLE_STMT_OPERAND (use_stmt, 1); |
15ec875c | 717 | if (result |
718 | && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 0)) == SSA_NAME | |
9481f629 | 719 | && (TREE_CODE (use_rhs) == SSA_NAME |
720 | || ((TREE_CODE (use_rhs) == NOP_EXPR | |
721 | || TREE_CODE (use_rhs) == CONVERT_EXPR) | |
722 | && TREE_CODE (TREE_OPERAND (use_rhs, 0)) == SSA_NAME))) | |
15ec875c | 723 | { |
724 | block_stmt_iterator bsi = bsi_for_stmt (use_stmt); | |
725 | release_defs (use_stmt); | |
726 | bsi_remove (&bsi, true); | |
727 | } | |
3d5cfe81 | 728 | } |
729 | ||
730 | return all; | |
731 | } | |
732 | ||
5adc1066 | 733 | /* Forward propagate the comparison COND defined in STMT like |
734 | cond_1 = x CMP y to uses of the form | |
735 | a_1 = (T')cond_1 | |
736 | a_1 = !cond_1 | |
737 | a_1 = cond_1 != 0 | |
738 | Returns true if stmt is now unused. */ | |
739 | ||
740 | static bool | |
741 | forward_propagate_comparison (tree cond, tree stmt) | |
742 | { | |
743 | tree name = GIMPLE_STMT_OPERAND (stmt, 0); | |
744 | tree use_stmt, tmp = NULL_TREE; | |
745 | ||
746 | /* Don't propagate ssa names that occur in abnormal phis. */ | |
747 | if ((TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME | |
748 | && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (cond, 0))) | |
749 | || (TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME | |
750 | && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (cond, 1)))) | |
751 | return false; | |
752 | ||
753 | /* Do not un-cse comparisons. But propagate through copies. */ | |
754 | use_stmt = get_prop_dest_stmt (name, &name); | |
755 | if (use_stmt == NULL_TREE) | |
756 | return false; | |
757 | ||
758 | /* Conversion of the condition result to another integral type. */ | |
759 | if (TREE_CODE (use_stmt) == GIMPLE_MODIFY_STMT | |
760 | && (TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == CONVERT_EXPR | |
761 | || TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == NOP_EXPR | |
762 | || COMPARISON_CLASS_P (GIMPLE_STMT_OPERAND (use_stmt, 1)) | |
763 | || TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == TRUTH_NOT_EXPR) | |
764 | && INTEGRAL_TYPE_P (TREE_TYPE (GIMPLE_STMT_OPERAND (use_stmt, 0)))) | |
765 | { | |
766 | tree lhs = GIMPLE_STMT_OPERAND (use_stmt, 0); | |
767 | tree rhs = GIMPLE_STMT_OPERAND (use_stmt, 1); | |
768 | ||
769 | /* We can propagate the condition into a conversion. */ | |
770 | if (TREE_CODE (rhs) == CONVERT_EXPR | |
771 | || TREE_CODE (rhs) == NOP_EXPR) | |
772 | { | |
773 | /* Avoid using fold here as that may create a COND_EXPR with | |
774 | non-boolean condition as canonical form. */ | |
775 | tmp = build2 (TREE_CODE (cond), TREE_TYPE (lhs), | |
776 | TREE_OPERAND (cond, 0), TREE_OPERAND (cond, 1)); | |
777 | } | |
778 | /* We can propagate the condition into X op CST where op | |
779 | is EQ_EXRP or NE_EXPR and CST is either one or zero. */ | |
780 | else if (COMPARISON_CLASS_P (rhs) | |
781 | && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME | |
782 | && TREE_CODE (TREE_OPERAND (rhs, 1)) == INTEGER_CST) | |
783 | { | |
784 | enum tree_code code = TREE_CODE (rhs); | |
785 | tree cst = TREE_OPERAND (rhs, 1); | |
786 | ||
787 | tmp = combine_cond_expr_cond (code, TREE_TYPE (lhs), | |
788 | fold_convert (TREE_TYPE (cst), cond), | |
789 | cst, false); | |
790 | if (tmp == NULL_TREE) | |
791 | return false; | |
792 | } | |
793 | /* We can propagate the condition into a statement that | |
794 | computes the logical negation of the comparison result. */ | |
795 | else if (TREE_CODE (rhs) == TRUTH_NOT_EXPR) | |
796 | { | |
797 | tree type = TREE_TYPE (TREE_OPERAND (cond, 0)); | |
798 | bool nans = HONOR_NANS (TYPE_MODE (type)); | |
799 | enum tree_code code; | |
800 | code = invert_tree_comparison (TREE_CODE (cond), nans); | |
801 | if (code == ERROR_MARK) | |
802 | return false; | |
803 | ||
804 | tmp = build2 (code, TREE_TYPE (lhs), TREE_OPERAND (cond, 0), | |
805 | TREE_OPERAND (cond, 1)); | |
806 | } | |
807 | else | |
808 | return false; | |
809 | ||
810 | GIMPLE_STMT_OPERAND (use_stmt, 1) = unshare_expr (tmp); | |
811 | update_stmt (use_stmt); | |
812 | ||
813 | /* Remove defining statements. */ | |
814 | remove_prop_source_from_use (name, stmt); | |
815 | ||
816 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
817 | { | |
818 | fprintf (dump_file, " Replaced '"); | |
819 | print_generic_expr (dump_file, rhs, dump_flags); | |
820 | fprintf (dump_file, "' with '"); | |
821 | print_generic_expr (dump_file, tmp, dump_flags); | |
822 | fprintf (dump_file, "'\n"); | |
823 | } | |
824 | ||
825 | return true; | |
826 | } | |
827 | ||
828 | return false; | |
829 | } | |
830 | ||
3a938499 | 831 | /* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y. |
832 | If so, we can change STMT into lhs = y which can later be copy | |
833 | propagated. Similarly for negation. | |
834 | ||
835 | This could trivially be formulated as a forward propagation | |
836 | to immediate uses. However, we already had an implementation | |
837 | from DOM which used backward propagation via the use-def links. | |
838 | ||
839 | It turns out that backward propagation is actually faster as | |
840 | there's less work to do for each NOT/NEG expression we find. | |
841 | Backwards propagation needs to look at the statement in a single | |
842 | backlink. Forward propagation needs to look at potentially more | |
843 | than one forward link. */ | |
844 | ||
845 | static void | |
846 | simplify_not_neg_expr (tree stmt) | |
847 | { | |
35cc02b5 | 848 | tree rhs = GIMPLE_STMT_OPERAND (stmt, 1); |
3a938499 | 849 | tree rhs_def_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0)); |
850 | ||
851 | /* See if the RHS_DEF_STMT has the same form as our statement. */ | |
35cc02b5 | 852 | if (TREE_CODE (rhs_def_stmt) == GIMPLE_MODIFY_STMT |
853 | && TREE_CODE (GIMPLE_STMT_OPERAND (rhs_def_stmt, 1)) == TREE_CODE (rhs)) | |
3a938499 | 854 | { |
35cc02b5 | 855 | tree rhs_def_operand = |
856 | TREE_OPERAND (GIMPLE_STMT_OPERAND (rhs_def_stmt, 1), 0); | |
3a938499 | 857 | |
858 | /* Verify that RHS_DEF_OPERAND is a suitable SSA_NAME. */ | |
859 | if (TREE_CODE (rhs_def_operand) == SSA_NAME | |
860 | && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand)) | |
861 | { | |
35cc02b5 | 862 | GIMPLE_STMT_OPERAND (stmt, 1) = rhs_def_operand; |
3a938499 | 863 | update_stmt (stmt); |
864 | } | |
865 | } | |
866 | } | |
3d5cfe81 | 867 | |
b5860aba | 868 | /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of |
869 | the condition which we may be able to optimize better. */ | |
870 | ||
871 | static void | |
872 | simplify_switch_expr (tree stmt) | |
873 | { | |
874 | tree cond = SWITCH_COND (stmt); | |
875 | tree def, to, ti; | |
876 | ||
877 | /* The optimization that we really care about is removing unnecessary | |
878 | casts. That will let us do much better in propagating the inferred | |
879 | constant at the switch target. */ | |
880 | if (TREE_CODE (cond) == SSA_NAME) | |
881 | { | |
882 | def = SSA_NAME_DEF_STMT (cond); | |
35cc02b5 | 883 | if (TREE_CODE (def) == GIMPLE_MODIFY_STMT) |
b5860aba | 884 | { |
35cc02b5 | 885 | def = GIMPLE_STMT_OPERAND (def, 1); |
b5860aba | 886 | if (TREE_CODE (def) == NOP_EXPR) |
887 | { | |
888 | int need_precision; | |
889 | bool fail; | |
890 | ||
891 | def = TREE_OPERAND (def, 0); | |
892 | ||
893 | #ifdef ENABLE_CHECKING | |
894 | /* ??? Why was Jeff testing this? We are gimple... */ | |
895 | gcc_assert (is_gimple_val (def)); | |
896 | #endif | |
897 | ||
898 | to = TREE_TYPE (cond); | |
899 | ti = TREE_TYPE (def); | |
900 | ||
901 | /* If we have an extension that preserves value, then we | |
902 | can copy the source value into the switch. */ | |
903 | ||
904 | need_precision = TYPE_PRECISION (ti); | |
905 | fail = false; | |
c5237b8b | 906 | if (! INTEGRAL_TYPE_P (ti)) |
907 | fail = true; | |
908 | else if (TYPE_UNSIGNED (to) && !TYPE_UNSIGNED (ti)) | |
b5860aba | 909 | fail = true; |
910 | else if (!TYPE_UNSIGNED (to) && TYPE_UNSIGNED (ti)) | |
911 | need_precision += 1; | |
912 | if (TYPE_PRECISION (to) < need_precision) | |
913 | fail = true; | |
914 | ||
915 | if (!fail) | |
916 | { | |
917 | SWITCH_COND (stmt) = def; | |
918 | update_stmt (stmt); | |
919 | } | |
920 | } | |
921 | } | |
922 | } | |
923 | } | |
924 | ||
4ee9c684 | 925 | /* Main entry point for the forward propagation optimizer. */ |
926 | ||
2a1990e9 | 927 | static unsigned int |
4ee9c684 | 928 | tree_ssa_forward_propagate_single_use_vars (void) |
929 | { | |
f5c8cff5 | 930 | basic_block bb; |
c96420f8 | 931 | unsigned int todoflags = 0; |
4ee9c684 | 932 | |
148aa112 | 933 | cfg_changed = false; |
934 | ||
f5c8cff5 | 935 | FOR_EACH_BB (bb) |
936 | { | |
291d763b | 937 | block_stmt_iterator bsi; |
938 | ||
939 | /* Note we update BSI within the loop as necessary. */ | |
940 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); ) | |
941 | { | |
942 | tree stmt = bsi_stmt (bsi); | |
943 | ||
944 | /* If this statement sets an SSA_NAME to an address, | |
945 | try to propagate the address into the uses of the SSA_NAME. */ | |
35cc02b5 | 946 | if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT) |
291d763b | 947 | { |
35cc02b5 | 948 | tree lhs = GIMPLE_STMT_OPERAND (stmt, 0); |
949 | tree rhs = GIMPLE_STMT_OPERAND (stmt, 1); | |
3a938499 | 950 | |
951 | ||
952 | if (TREE_CODE (lhs) != SSA_NAME) | |
953 | { | |
954 | bsi_next (&bsi); | |
955 | continue; | |
956 | } | |
957 | ||
30fde358 | 958 | if (TREE_CODE (rhs) == ADDR_EXPR |
d9d723d9 | 959 | /* We can also disregard changes in const qualifiers for |
30fde358 | 960 | the dereferenced value. */ |
961 | || ((TREE_CODE (rhs) == NOP_EXPR | |
962 | || TREE_CODE (rhs) == CONVERT_EXPR) | |
963 | && TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR | |
964 | && POINTER_TYPE_P (TREE_TYPE (rhs)) | |
d9d723d9 | 965 | /* But do not propagate changes in volatileness. */ |
966 | && (TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (rhs))) | |
967 | == TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (TREE_OPERAND (rhs, 0))))) | |
cbb0f5f6 | 968 | && types_compatible_p (TREE_TYPE (TREE_TYPE (TREE_OPERAND (rhs, 0))), |
969 | TREE_TYPE (TREE_TYPE (rhs))))) | |
3a938499 | 970 | { |
b75537fb | 971 | if (!stmt_references_abnormal_ssa_name (stmt) |
972 | && forward_propagate_addr_expr (lhs, rhs)) | |
24838d3f | 973 | { |
974 | release_defs (stmt); | |
ea0ab927 | 975 | todoflags |= TODO_remove_unused_locals; |
24838d3f | 976 | bsi_remove (&bsi, true); |
977 | } | |
3a938499 | 978 | else |
979 | bsi_next (&bsi); | |
980 | } | |
981 | else if ((TREE_CODE (rhs) == BIT_NOT_EXPR | |
982 | || TREE_CODE (rhs) == NEGATE_EXPR) | |
983 | && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME) | |
984 | { | |
985 | simplify_not_neg_expr (stmt); | |
986 | bsi_next (&bsi); | |
987 | } | |
ec0fa513 | 988 | else if (TREE_CODE (rhs) == COND_EXPR) |
989 | { | |
4c580c8c | 990 | int did_something; |
d080be9e | 991 | fold_defer_overflow_warnings (); |
992 | did_something = forward_propagate_into_cond (rhs, stmt); | |
4c580c8c | 993 | if (did_something == 2) |
994 | cfg_changed = true; | |
d080be9e | 995 | fold_undefer_overflow_warnings (!TREE_NO_WARNING (rhs) |
996 | && did_something, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL); | |
ec0fa513 | 997 | bsi_next (&bsi); |
998 | } | |
5adc1066 | 999 | else if (COMPARISON_CLASS_P (rhs)) |
1000 | { | |
1001 | if (forward_propagate_comparison (rhs, stmt)) | |
1002 | { | |
1003 | release_defs (stmt); | |
1004 | todoflags |= TODO_remove_unused_locals; | |
1005 | bsi_remove (&bsi, true); | |
1006 | } | |
1007 | else | |
1008 | bsi_next (&bsi); | |
1009 | } | |
291d763b | 1010 | else |
1011 | bsi_next (&bsi); | |
1012 | } | |
b5860aba | 1013 | else if (TREE_CODE (stmt) == SWITCH_EXPR) |
1014 | { | |
1015 | simplify_switch_expr (stmt); | |
1016 | bsi_next (&bsi); | |
1017 | } | |
291d763b | 1018 | else if (TREE_CODE (stmt) == COND_EXPR) |
1019 | { | |
4c580c8c | 1020 | int did_something; |
d080be9e | 1021 | fold_defer_overflow_warnings (); |
1022 | did_something = forward_propagate_into_cond (stmt, stmt); | |
4c580c8c | 1023 | if (did_something == 2) |
1024 | cfg_changed = true; | |
72c59a18 | 1025 | fold_undefer_overflow_warnings (did_something, stmt, |
d080be9e | 1026 | WARN_STRICT_OVERFLOW_CONDITIONAL); |
291d763b | 1027 | bsi_next (&bsi); |
1028 | } | |
1029 | else | |
1030 | bsi_next (&bsi); | |
1031 | } | |
f5c8cff5 | 1032 | } |
148aa112 | 1033 | |
1034 | if (cfg_changed) | |
6fa78c7b | 1035 | todoflags |= TODO_cleanup_cfg; |
c96420f8 | 1036 | return todoflags; |
4ee9c684 | 1037 | } |
1038 | ||
1039 | ||
1040 | static bool | |
1041 | gate_forwprop (void) | |
1042 | { | |
1043 | return 1; | |
1044 | } | |
1045 | ||
1046 | struct tree_opt_pass pass_forwprop = { | |
1047 | "forwprop", /* name */ | |
1048 | gate_forwprop, /* gate */ | |
1049 | tree_ssa_forward_propagate_single_use_vars, /* execute */ | |
1050 | NULL, /* sub */ | |
1051 | NULL, /* next */ | |
1052 | 0, /* static_pass_number */ | |
1053 | TV_TREE_FORWPROP, /* tv_id */ | |
49290934 | 1054 | PROP_cfg | PROP_ssa, /* properties_required */ |
4ee9c684 | 1055 | 0, /* properties_provided */ |
b6246c40 | 1056 | 0, /* properties_destroyed */ |
4ee9c684 | 1057 | 0, /* todo_flags_start */ |
de6ed584 | 1058 | TODO_dump_func |
abd433a7 | 1059 | | TODO_ggc_collect |
de6ed584 | 1060 | | TODO_update_ssa |
1061 | | TODO_verify_ssa, /* todo_flags_finish */ | |
1062 | 0 /* letter */ | |
4ee9c684 | 1063 | }; |
37361b38 | 1064 | |
1065 | ||
1066 | /* Structure to keep track of the value of a dereferenced PHI result | |
1067 | and the set of virtual operands used for that dereference. */ | |
1068 | ||
1069 | struct phiprop_d | |
1070 | { | |
1071 | tree value; | |
1072 | tree vop_stmt; | |
1073 | }; | |
1074 | ||
1075 | /* Verify if the value recorded for NAME in PHIVN is still valid at | |
1076 | the start of basic block BB. */ | |
1077 | ||
1078 | static bool | |
1079 | phivn_valid_p (struct phiprop_d *phivn, tree name, basic_block bb) | |
1080 | { | |
1081 | tree vop_stmt = phivn[SSA_NAME_VERSION (name)].vop_stmt; | |
1082 | ssa_op_iter ui; | |
1083 | tree vuse; | |
1084 | ||
1085 | /* The def stmts of all virtual uses need to be post-dominated | |
1086 | by bb. */ | |
1087 | FOR_EACH_SSA_TREE_OPERAND (vuse, vop_stmt, ui, SSA_OP_VUSE) | |
1088 | { | |
1089 | tree use_stmt; | |
1090 | imm_use_iterator ui2; | |
1091 | bool ok = true; | |
1092 | ||
1093 | FOR_EACH_IMM_USE_STMT (use_stmt, ui2, vuse) | |
1094 | { | |
1095 | /* If BB does not dominate a VDEF, the value is invalid. */ | |
1096 | if (((TREE_CODE (use_stmt) == GIMPLE_MODIFY_STMT | |
1097 | && !ZERO_SSA_OPERANDS (use_stmt, SSA_OP_VDEF)) | |
1098 | || TREE_CODE (use_stmt) == PHI_NODE) | |
1099 | && !dominated_by_p (CDI_DOMINATORS, bb_for_stmt (use_stmt), bb)) | |
1100 | { | |
1101 | ok = false; | |
1102 | BREAK_FROM_IMM_USE_STMT (ui2); | |
1103 | } | |
1104 | } | |
1105 | if (!ok) | |
1106 | return false; | |
1107 | } | |
1108 | ||
1109 | return true; | |
1110 | } | |
1111 | ||
1112 | /* Insert a new phi node for the dereference of PHI at basic_block | |
1113 | BB with the virtual operands from USE_STMT. */ | |
1114 | ||
1115 | static tree | |
1116 | phiprop_insert_phi (basic_block bb, tree phi, tree use_stmt, | |
1117 | struct phiprop_d *phivn, size_t n) | |
1118 | { | |
1119 | tree res, new_phi; | |
1120 | edge_iterator ei; | |
1121 | edge e; | |
1122 | ||
1123 | /* Build a new PHI node to replace the definition of | |
1124 | the indirect reference lhs. */ | |
1125 | res = GIMPLE_STMT_OPERAND (use_stmt, 0); | |
1126 | SSA_NAME_DEF_STMT (res) = new_phi = create_phi_node (res, bb); | |
1127 | ||
1128 | /* Add PHI arguments for each edge inserting loads of the | |
1129 | addressable operands. */ | |
1130 | FOR_EACH_EDGE (e, ei, bb->preds) | |
1131 | { | |
1132 | tree old_arg, new_var, tmp; | |
1133 | ||
1134 | old_arg = PHI_ARG_DEF_FROM_EDGE (phi, e); | |
1135 | while (TREE_CODE (old_arg) == SSA_NAME | |
1136 | && (SSA_NAME_VERSION (old_arg) >= n | |
1137 | || phivn[SSA_NAME_VERSION (old_arg)].value == NULL_TREE)) | |
1138 | { | |
1139 | tree def_stmt = SSA_NAME_DEF_STMT (old_arg); | |
1140 | old_arg = GIMPLE_STMT_OPERAND (def_stmt, 1); | |
1141 | } | |
1142 | ||
1143 | if (TREE_CODE (old_arg) == SSA_NAME) | |
310d2511 | 1144 | /* Reuse a formerly created dereference. */ |
37361b38 | 1145 | new_var = phivn[SSA_NAME_VERSION (old_arg)].value; |
1146 | else | |
1147 | { | |
1148 | old_arg = TREE_OPERAND (old_arg, 0); | |
1149 | new_var = create_tmp_var (TREE_TYPE (old_arg), NULL); | |
1150 | tmp = build2 (GIMPLE_MODIFY_STMT, void_type_node, | |
1151 | NULL_TREE, unshare_expr (old_arg)); | |
1152 | if (TREE_CODE (TREE_TYPE (old_arg)) == COMPLEX_TYPE | |
1153 | || TREE_CODE (TREE_TYPE (old_arg)) == VECTOR_TYPE) | |
1154 | DECL_GIMPLE_REG_P (new_var) = 1; | |
1155 | add_referenced_var (new_var); | |
1156 | new_var = make_ssa_name (new_var, tmp); | |
1157 | GIMPLE_STMT_OPERAND (tmp, 0) = new_var; | |
1158 | ||
1159 | bsi_insert_on_edge (e, tmp); | |
1160 | ||
1161 | update_stmt (tmp); | |
1162 | mark_symbols_for_renaming (tmp); | |
1163 | } | |
1164 | ||
1165 | add_phi_arg (new_phi, new_var, e); | |
1166 | } | |
1167 | ||
1168 | update_stmt (new_phi); | |
1169 | ||
1170 | return res; | |
1171 | } | |
1172 | ||
1173 | /* Propagate between the phi node arguments of PHI in BB and phi result | |
1174 | users. For now this matches | |
1175 | # p_2 = PHI <&x, &y> | |
1176 | <Lx>:; | |
1177 | p_3 = p_2; | |
1178 | z_2 = *p_3; | |
1179 | and converts it to | |
1180 | # z_2 = PHI <x, y> | |
1181 | <Lx>:; | |
1182 | Returns true if a transformation was done and edge insertions | |
1183 | need to be committed. Global data PHIVN and N is used to track | |
1184 | past transformation results. We need to be especially careful here | |
1185 | with aliasing issues as we are moving memory reads. */ | |
1186 | ||
1187 | static bool | |
1188 | propagate_with_phi (basic_block bb, tree phi, struct phiprop_d *phivn, size_t n) | |
1189 | { | |
1190 | tree ptr = PHI_RESULT (phi); | |
1191 | tree use_stmt, res = NULL_TREE; | |
1192 | block_stmt_iterator bsi; | |
1193 | imm_use_iterator ui; | |
1194 | use_operand_p arg_p, use; | |
1195 | ssa_op_iter i; | |
1196 | bool phi_inserted; | |
1197 | ||
1198 | if (MTAG_P (SSA_NAME_VAR (ptr)) | |
1199 | || !POINTER_TYPE_P (TREE_TYPE (ptr)) | |
1200 | || !is_gimple_reg_type (TREE_TYPE (TREE_TYPE (ptr)))) | |
1201 | return false; | |
1202 | ||
1203 | /* Check if we can "cheaply" dereference all phi arguments. */ | |
1204 | FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE) | |
1205 | { | |
1206 | tree arg = USE_FROM_PTR (arg_p); | |
1207 | /* Walk the ssa chain until we reach a ssa name we already | |
1208 | created a value for or we reach a definition of the form | |
1209 | ssa_name_n = &var; */ | |
1210 | while (TREE_CODE (arg) == SSA_NAME | |
1211 | && !SSA_NAME_IS_DEFAULT_DEF (arg) | |
1212 | && (SSA_NAME_VERSION (arg) >= n | |
1213 | || phivn[SSA_NAME_VERSION (arg)].value == NULL_TREE)) | |
1214 | { | |
1215 | tree def_stmt = SSA_NAME_DEF_STMT (arg); | |
1216 | if (TREE_CODE (def_stmt) != GIMPLE_MODIFY_STMT) | |
1217 | return false; | |
1218 | arg = GIMPLE_STMT_OPERAND (def_stmt, 1); | |
1219 | } | |
1220 | if ((TREE_CODE (arg) != ADDR_EXPR | |
1221 | /* Avoid to have to decay *&a to a[0] later. */ | |
1222 | || !is_gimple_reg_type (TREE_TYPE (TREE_OPERAND (arg, 0)))) | |
1223 | && !(TREE_CODE (arg) == SSA_NAME | |
1224 | && phivn[SSA_NAME_VERSION (arg)].value != NULL_TREE | |
1225 | && phivn_valid_p (phivn, arg, bb))) | |
1226 | return false; | |
1227 | } | |
1228 | ||
1229 | /* Find a dereferencing use. First follow (single use) ssa | |
1230 | copy chains for ptr. */ | |
1231 | while (single_imm_use (ptr, &use, &use_stmt) | |
1232 | && TREE_CODE (use_stmt) == GIMPLE_MODIFY_STMT | |
1233 | && GIMPLE_STMT_OPERAND (use_stmt, 1) == ptr | |
1234 | && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 0)) == SSA_NAME) | |
1235 | ptr = GIMPLE_STMT_OPERAND (use_stmt, 0); | |
1236 | ||
1237 | /* Replace the first dereference of *ptr if there is one and if we | |
1238 | can move the loads to the place of the ptr phi node. */ | |
1239 | phi_inserted = false; | |
1240 | FOR_EACH_IMM_USE_STMT (use_stmt, ui, ptr) | |
1241 | { | |
1242 | ssa_op_iter ui2; | |
1243 | tree vuse; | |
1244 | ||
1245 | /* Check whether this is a load of *ptr. */ | |
1246 | if (!(TREE_CODE (use_stmt) == GIMPLE_MODIFY_STMT | |
1247 | && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 0)) == SSA_NAME | |
1248 | && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == INDIRECT_REF | |
1249 | && TREE_OPERAND (GIMPLE_STMT_OPERAND (use_stmt, 1), 0) == ptr | |
1250 | /* We cannot replace a load that may throw or is volatile. */ | |
1251 | && !tree_can_throw_internal (use_stmt))) | |
1252 | continue; | |
1253 | ||
1254 | /* Check if we can move the loads. The def stmts of all virtual uses | |
1255 | need to be post-dominated by bb. */ | |
1256 | FOR_EACH_SSA_TREE_OPERAND (vuse, use_stmt, ui2, SSA_OP_VUSE) | |
1257 | { | |
1258 | tree def_stmt = SSA_NAME_DEF_STMT (vuse); | |
1259 | if (!SSA_NAME_IS_DEFAULT_DEF (vuse) | |
1260 | && (bb_for_stmt (def_stmt) == bb | |
1261 | || !dominated_by_p (CDI_DOMINATORS, | |
1262 | bb, bb_for_stmt (def_stmt)))) | |
1263 | goto next; | |
1264 | } | |
1265 | ||
1266 | /* Found a proper dereference. Insert a phi node if this | |
1267 | is the first load transformation. */ | |
1268 | if (!phi_inserted) | |
1269 | { | |
1270 | res = phiprop_insert_phi (bb, phi, use_stmt, phivn, n); | |
1271 | ||
1272 | /* Remember the value we created for *ptr. */ | |
1273 | phivn[SSA_NAME_VERSION (ptr)].value = res; | |
1274 | phivn[SSA_NAME_VERSION (ptr)].vop_stmt = use_stmt; | |
1275 | ||
1276 | /* Remove old stmt. The phi is taken care of by DCE, if we | |
1277 | want to delete it here we also have to delete all intermediate | |
1278 | copies. */ | |
1279 | bsi = bsi_for_stmt (use_stmt); | |
1280 | bsi_remove (&bsi, 0); | |
1281 | ||
1282 | phi_inserted = true; | |
1283 | } | |
1284 | else | |
1285 | { | |
1286 | /* Further replacements are easy, just make a copy out of the | |
1287 | load. */ | |
1288 | GIMPLE_STMT_OPERAND (use_stmt, 1) = res; | |
1289 | update_stmt (use_stmt); | |
1290 | } | |
1291 | ||
1292 | next:; | |
1293 | /* Continue searching for a proper dereference. */ | |
1294 | } | |
1295 | ||
1296 | return phi_inserted; | |
1297 | } | |
1298 | ||
1299 | /* Helper walking the dominator tree starting from BB and processing | |
1300 | phi nodes with global data PHIVN and N. */ | |
1301 | ||
1302 | static bool | |
1303 | tree_ssa_phiprop_1 (basic_block bb, struct phiprop_d *phivn, size_t n) | |
1304 | { | |
1305 | bool did_something = false; | |
1306 | basic_block son; | |
1307 | tree phi; | |
1308 | ||
1309 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) | |
1310 | did_something |= propagate_with_phi (bb, phi, phivn, n); | |
1311 | ||
1312 | for (son = first_dom_son (CDI_DOMINATORS, bb); | |
1313 | son; | |
1314 | son = next_dom_son (CDI_DOMINATORS, son)) | |
1315 | did_something |= tree_ssa_phiprop_1 (son, phivn, n); | |
1316 | ||
1317 | return did_something; | |
1318 | } | |
1319 | ||
1320 | /* Main entry for phiprop pass. */ | |
1321 | ||
1322 | static unsigned int | |
1323 | tree_ssa_phiprop (void) | |
1324 | { | |
1325 | struct phiprop_d *phivn; | |
1326 | ||
1327 | calculate_dominance_info (CDI_DOMINATORS); | |
1328 | ||
1329 | phivn = XCNEWVEC (struct phiprop_d, num_ssa_names); | |
1330 | ||
1331 | if (tree_ssa_phiprop_1 (ENTRY_BLOCK_PTR, phivn, num_ssa_names)) | |
1332 | bsi_commit_edge_inserts (); | |
1333 | ||
1334 | free (phivn); | |
1335 | ||
1336 | return 0; | |
1337 | } | |
1338 | ||
1339 | static bool | |
1340 | gate_phiprop (void) | |
1341 | { | |
1342 | return 1; | |
1343 | } | |
1344 | ||
1345 | struct tree_opt_pass pass_phiprop = { | |
1346 | "phiprop", /* name */ | |
1347 | gate_phiprop, /* gate */ | |
1348 | tree_ssa_phiprop, /* execute */ | |
1349 | NULL, /* sub */ | |
1350 | NULL, /* next */ | |
1351 | 0, /* static_pass_number */ | |
1352 | TV_TREE_FORWPROP, /* tv_id */ | |
1353 | PROP_cfg | PROP_ssa, /* properties_required */ | |
1354 | 0, /* properties_provided */ | |
1355 | 0, /* properties_destroyed */ | |
1356 | 0, /* todo_flags_start */ | |
1357 | TODO_dump_func | |
1358 | | TODO_ggc_collect | |
1359 | | TODO_update_ssa | |
1360 | | TODO_verify_ssa, /* todo_flags_finish */ | |
1361 | 0 /* letter */ | |
1362 | }; |