]>
Commit | Line | Data |
---|---|---|
5f718c29 | 1 | /* Routines for discovering and unpropagating edge equivalences. |
7cf0dbf3 | 2 | Copyright (C) 2005, 2007, 2008, 2010 |
3 | Free Software Foundation, Inc. | |
5f718c29 | 4 | |
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify | |
8 | it under the terms of the GNU General Public License as published by | |
8c4c00c1 | 9 | the Free Software Foundation; either version 3, or (at your option) |
5f718c29 | 10 | any later version. |
11 | ||
12 | GCC is distributed in the hope that it will be useful, | |
13 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | GNU General Public License for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
8c4c00c1 | 18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
5f718c29 | 20 | |
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "tm.h" | |
25 | #include "tree.h" | |
26 | #include "flags.h" | |
5f718c29 | 27 | #include "tm_p.h" |
5f718c29 | 28 | #include "basic-block.h" |
5f718c29 | 29 | #include "function.h" |
5f718c29 | 30 | #include "timevar.h" |
31 | #include "tree-dump.h" | |
32 | #include "tree-flow.h" | |
33 | #include "domwalk.h" | |
5f718c29 | 34 | #include "tree-pass.h" |
35 | #include "tree-ssa-propagate.h" | |
36 | #include "langhooks.h" | |
37 | ||
38 | /* The basic structure describing an equivalency created by traversing | |
39 | an edge. Traversing the edge effectively means that we can assume | |
40 | that we've seen an assignment LHS = RHS. */ | |
41 | struct edge_equivalency | |
42 | { | |
43 | tree rhs; | |
44 | tree lhs; | |
45 | }; | |
46 | ||
47 | /* This routine finds and records edge equivalences for every edge | |
48 | in the CFG. | |
49 | ||
50 | When complete, each edge that creates an equivalency will have an | |
48e1416a | 51 | EDGE_EQUIVALENCY structure hanging off the edge's AUX field. |
5f718c29 | 52 | The caller is responsible for freeing the AUX fields. */ |
53 | ||
54 | static void | |
55 | associate_equivalences_with_edges (void) | |
56 | { | |
57 | basic_block bb; | |
58 | ||
59 | /* Walk over each block. If the block ends with a control statement, | |
60 | then it might create a useful equivalence. */ | |
61 | FOR_EACH_BB (bb) | |
62 | { | |
75a70cf9 | 63 | gimple_stmt_iterator gsi = gsi_last_bb (bb); |
64 | gimple stmt; | |
5f718c29 | 65 | |
66 | /* If the block does not end with a COND_EXPR or SWITCH_EXPR | |
67 | then there is nothing to do. */ | |
75a70cf9 | 68 | if (gsi_end_p (gsi)) |
5f718c29 | 69 | continue; |
70 | ||
75a70cf9 | 71 | stmt = gsi_stmt (gsi); |
5f718c29 | 72 | |
73 | if (!stmt) | |
74 | continue; | |
75 | ||
76 | /* A COND_EXPR may create an equivalency in a variety of different | |
77 | ways. */ | |
75a70cf9 | 78 | if (gimple_code (stmt) == GIMPLE_COND) |
5f718c29 | 79 | { |
5f718c29 | 80 | edge true_edge; |
81 | edge false_edge; | |
82 | struct edge_equivalency *equivalency; | |
75a70cf9 | 83 | enum tree_code code = gimple_cond_code (stmt); |
5f718c29 | 84 | |
85 | extract_true_false_edges_from_block (bb, &true_edge, &false_edge); | |
86 | ||
5f718c29 | 87 | /* Equality tests may create one or two equivalences. */ |
75a70cf9 | 88 | if (code == EQ_EXPR || code == NE_EXPR) |
5f718c29 | 89 | { |
75a70cf9 | 90 | tree op0 = gimple_cond_lhs (stmt); |
91 | tree op1 = gimple_cond_rhs (stmt); | |
5f718c29 | 92 | |
93 | /* Special case comparing booleans against a constant as we | |
94 | know the value of OP0 on both arms of the branch. i.e., we | |
95 | can record an equivalence for OP0 rather than COND. */ | |
96 | if (TREE_CODE (op0) == SSA_NAME | |
932540b6 | 97 | && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0) |
5f718c29 | 98 | && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE |
99 | && is_gimple_min_invariant (op1)) | |
100 | { | |
75a70cf9 | 101 | if (code == EQ_EXPR) |
5f718c29 | 102 | { |
945865c5 | 103 | equivalency = XNEW (struct edge_equivalency); |
5f718c29 | 104 | equivalency->lhs = op0; |
105 | equivalency->rhs = (integer_zerop (op1) | |
106 | ? boolean_false_node | |
107 | : boolean_true_node); | |
108 | true_edge->aux = equivalency; | |
109 | ||
945865c5 | 110 | equivalency = XNEW (struct edge_equivalency); |
5f718c29 | 111 | equivalency->lhs = op0; |
112 | equivalency->rhs = (integer_zerop (op1) | |
113 | ? boolean_true_node | |
114 | : boolean_false_node); | |
115 | false_edge->aux = equivalency; | |
116 | } | |
117 | else | |
118 | { | |
945865c5 | 119 | equivalency = XNEW (struct edge_equivalency); |
5f718c29 | 120 | equivalency->lhs = op0; |
121 | equivalency->rhs = (integer_zerop (op1) | |
122 | ? boolean_true_node | |
123 | : boolean_false_node); | |
124 | true_edge->aux = equivalency; | |
125 | ||
945865c5 | 126 | equivalency = XNEW (struct edge_equivalency); |
5f718c29 | 127 | equivalency->lhs = op0; |
128 | equivalency->rhs = (integer_zerop (op1) | |
129 | ? boolean_false_node | |
130 | : boolean_true_node); | |
131 | false_edge->aux = equivalency; | |
132 | } | |
133 | } | |
134 | ||
024e445d | 135 | else if (TREE_CODE (op0) == SSA_NAME |
136 | && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0) | |
137 | && (is_gimple_min_invariant (op1) | |
138 | || (TREE_CODE (op1) == SSA_NAME | |
139 | && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1)))) | |
5f718c29 | 140 | { |
141 | /* For IEEE, -0.0 == 0.0, so we don't necessarily know | |
142 | the sign of a variable compared against zero. If | |
143 | we're honoring signed zeros, then we cannot record | |
144 | this value unless we know that the value is nonzero. */ | |
145 | if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op0))) | |
146 | && (TREE_CODE (op1) != REAL_CST | |
147 | || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (op1)))) | |
148 | continue; | |
149 | ||
945865c5 | 150 | equivalency = XNEW (struct edge_equivalency); |
5f718c29 | 151 | equivalency->lhs = op0; |
152 | equivalency->rhs = op1; | |
75a70cf9 | 153 | if (code == EQ_EXPR) |
5f718c29 | 154 | true_edge->aux = equivalency; |
48e1416a | 155 | else |
5f718c29 | 156 | false_edge->aux = equivalency; |
157 | ||
158 | } | |
159 | } | |
160 | ||
161 | /* ??? TRUTH_NOT_EXPR can create an equivalence too. */ | |
162 | } | |
163 | ||
164 | /* For a SWITCH_EXPR, a case label which represents a single | |
165 | value and which is the only case label which reaches the | |
166 | target block creates an equivalence. */ | |
75a70cf9 | 167 | else if (gimple_code (stmt) == GIMPLE_SWITCH) |
5f718c29 | 168 | { |
75a70cf9 | 169 | tree cond = gimple_switch_index (stmt); |
5f718c29 | 170 | |
932540b6 | 171 | if (TREE_CODE (cond) == SSA_NAME |
172 | && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond)) | |
5f718c29 | 173 | { |
75a70cf9 | 174 | int i, n_labels = gimple_switch_num_labels (stmt); |
87490e08 | 175 | tree *info = XCNEWVEC (tree, last_basic_block); |
5f718c29 | 176 | |
177 | /* Walk over the case label vector. Record blocks | |
178 | which are reached by a single case label which represents | |
179 | a single value. */ | |
180 | for (i = 0; i < n_labels; i++) | |
181 | { | |
75a70cf9 | 182 | tree label = gimple_switch_label (stmt, i); |
5f718c29 | 183 | basic_block bb = label_to_block (CASE_LABEL (label)); |
184 | ||
5f718c29 | 185 | if (CASE_HIGH (label) |
186 | || !CASE_LOW (label) | |
187 | || info[bb->index]) | |
188 | info[bb->index] = error_mark_node; | |
189 | else | |
190 | info[bb->index] = label; | |
191 | } | |
192 | ||
193 | /* Now walk over the blocks to determine which ones were | |
194 | marked as being reached by a useful case label. */ | |
195 | for (i = 0; i < n_basic_blocks; i++) | |
196 | { | |
197 | tree node = info[i]; | |
198 | ||
199 | if (node != NULL | |
200 | && node != error_mark_node) | |
201 | { | |
202 | tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node)); | |
203 | struct edge_equivalency *equivalency; | |
204 | ||
205 | /* Record an equivalency on the edge from BB to basic | |
206 | block I. */ | |
945865c5 | 207 | equivalency = XNEW (struct edge_equivalency); |
5f718c29 | 208 | equivalency->rhs = x; |
209 | equivalency->lhs = cond; | |
210 | find_edge (bb, BASIC_BLOCK (i))->aux = equivalency; | |
211 | } | |
212 | } | |
213 | free (info); | |
214 | } | |
215 | } | |
216 | ||
217 | } | |
218 | } | |
219 | ||
220 | ||
221 | /* Translating out of SSA sometimes requires inserting copies and | |
222 | constant initializations on edges to eliminate PHI nodes. | |
223 | ||
224 | In some cases those copies and constant initializations are | |
225 | redundant because the target already has the value on the | |
226 | RHS of the assignment. | |
227 | ||
228 | We previously tried to catch these cases after translating | |
229 | out of SSA form. However, that code often missed cases. Worse | |
230 | yet, the cases it missed were also often missed by the RTL | |
231 | optimizers. Thus the resulting code had redundant instructions. | |
232 | ||
233 | This pass attempts to detect these situations before translating | |
234 | out of SSA form. | |
235 | ||
236 | The key concept that this pass is built upon is that these | |
237 | redundant copies and constant initializations often occur | |
238 | due to constant/copy propagating equivalences resulting from | |
239 | COND_EXPRs and SWITCH_EXPRs. | |
240 | ||
241 | We want to do those propagations as they can sometimes allow | |
25f6297d | 242 | the SSA optimizers to do a better job. However, in the cases |
5f718c29 | 243 | where such propagations do not result in further optimization, |
244 | we would like to "undo" the propagation to avoid the redundant | |
245 | copies and constant initializations. | |
246 | ||
247 | This pass works by first associating equivalences with edges in | |
248 | the CFG. For example, the edge leading from a SWITCH_EXPR to | |
249 | its associated CASE_LABEL will have an equivalency between | |
250 | SWITCH_COND and the value in the case label. | |
251 | ||
252 | Once we have found the edge equivalences, we proceed to walk | |
253 | the CFG in dominator order. As we traverse edges we record | |
254 | equivalences associated with those edges we traverse. | |
255 | ||
256 | When we encounter a PHI node, we walk its arguments to see if we | |
257 | have an equivalence for the PHI argument. If so, then we replace | |
258 | the argument. | |
259 | ||
260 | Equivalences are looked up based on their value (think of it as | |
261 | the RHS of an assignment). A value may be an SSA_NAME or an | |
262 | invariant. We may have several SSA_NAMEs with the same value, | |
263 | so with each value we have a list of SSA_NAMEs that have the | |
264 | same value. */ | |
265 | ||
266 | /* As we enter each block we record the value for any edge equivalency | |
267 | leading to this block. If no such edge equivalency exists, then we | |
268 | record NULL. These equivalences are live until we leave the dominator | |
269 | subtree rooted at the block where we record the equivalency. */ | |
1a5e3743 | 270 | static VEC(tree,heap) *equiv_stack; |
5f718c29 | 271 | |
272 | /* Global hash table implementing a mapping from invariant values | |
273 | to a list of SSA_NAMEs which have the same value. We might be | |
274 | able to reuse tree-vn for this code. */ | |
275 | static htab_t equiv; | |
276 | ||
277 | /* Main structure for recording equivalences into our hash table. */ | |
278 | struct equiv_hash_elt | |
279 | { | |
280 | /* The value/key of this entry. */ | |
281 | tree value; | |
282 | ||
283 | /* List of SSA_NAMEs which have the same value/key. */ | |
96a7ab57 | 284 | VEC(tree,heap) *equivalences; |
5f718c29 | 285 | }; |
286 | ||
6bf320fb | 287 | static void uncprop_enter_block (struct dom_walk_data *, basic_block); |
288 | static void uncprop_leave_block (struct dom_walk_data *, basic_block); | |
289 | static void uncprop_into_successor_phis (basic_block); | |
5f718c29 | 290 | |
291 | /* Hashing and equality routines for the hash table. */ | |
292 | ||
293 | static hashval_t | |
294 | equiv_hash (const void *p) | |
295 | { | |
aae87fc3 | 296 | tree const value = ((const struct equiv_hash_elt *)p)->value; |
5f718c29 | 297 | return iterative_hash_expr (value, 0); |
298 | } | |
299 | ||
300 | static int | |
301 | equiv_eq (const void *p1, const void *p2) | |
302 | { | |
aae87fc3 | 303 | tree value1 = ((const struct equiv_hash_elt *)p1)->value; |
304 | tree value2 = ((const struct equiv_hash_elt *)p2)->value; | |
5f718c29 | 305 | |
306 | return operand_equal_p (value1, value2, 0); | |
307 | } | |
308 | ||
96a7ab57 | 309 | /* Free an instance of equiv_hash_elt. */ |
310 | ||
311 | static void | |
312 | equiv_free (void *p) | |
313 | { | |
314 | struct equiv_hash_elt *elt = (struct equiv_hash_elt *) p; | |
315 | VEC_free (tree, heap, elt->equivalences); | |
316 | free (elt); | |
317 | } | |
318 | ||
5f718c29 | 319 | /* Remove the most recently recorded equivalency for VALUE. */ |
320 | ||
321 | static void | |
322 | remove_equivalence (tree value) | |
323 | { | |
324 | struct equiv_hash_elt equiv_hash_elt, *equiv_hash_elt_p; | |
325 | void **slot; | |
326 | ||
327 | equiv_hash_elt.value = value; | |
328 | equiv_hash_elt.equivalences = NULL; | |
329 | ||
330 | slot = htab_find_slot (equiv, &equiv_hash_elt, NO_INSERT); | |
331 | ||
332 | equiv_hash_elt_p = (struct equiv_hash_elt *) *slot; | |
96a7ab57 | 333 | VEC_pop (tree, equiv_hash_elt_p->equivalences); |
5f718c29 | 334 | } |
335 | ||
336 | /* Record EQUIVALENCE = VALUE into our hash table. */ | |
337 | ||
338 | static void | |
339 | record_equiv (tree value, tree equivalence) | |
340 | { | |
341 | struct equiv_hash_elt *equiv_hash_elt; | |
342 | void **slot; | |
343 | ||
945865c5 | 344 | equiv_hash_elt = XNEW (struct equiv_hash_elt); |
5f718c29 | 345 | equiv_hash_elt->value = value; |
346 | equiv_hash_elt->equivalences = NULL; | |
347 | ||
348 | slot = htab_find_slot (equiv, equiv_hash_elt, INSERT); | |
349 | ||
350 | if (*slot == NULL) | |
351 | *slot = (void *) equiv_hash_elt; | |
352 | else | |
353 | free (equiv_hash_elt); | |
354 | ||
355 | equiv_hash_elt = (struct equiv_hash_elt *) *slot; | |
48e1416a | 356 | |
96a7ab57 | 357 | VEC_safe_push (tree, heap, equiv_hash_elt->equivalences, equivalence); |
5f718c29 | 358 | } |
359 | ||
360 | /* Main driver for un-cprop. */ | |
361 | ||
2a1990e9 | 362 | static unsigned int |
5f718c29 | 363 | tree_ssa_uncprop (void) |
364 | { | |
365 | struct dom_walk_data walk_data; | |
366 | basic_block bb; | |
367 | ||
368 | associate_equivalences_with_edges (); | |
369 | ||
370 | /* Create our global data structures. */ | |
96a7ab57 | 371 | equiv = htab_create (1024, equiv_hash, equiv_eq, equiv_free); |
1a5e3743 | 372 | equiv_stack = VEC_alloc (tree, heap, 2); |
5f718c29 | 373 | |
374 | /* We're going to do a dominator walk, so ensure that we have | |
375 | dominance information. */ | |
376 | calculate_dominance_info (CDI_DOMINATORS); | |
377 | ||
378 | /* Setup callbacks for the generic dominator tree walker. */ | |
5f718c29 | 379 | walk_data.dom_direction = CDI_DOMINATORS; |
380 | walk_data.initialize_block_local_data = NULL; | |
6bf320fb | 381 | walk_data.before_dom_children = uncprop_enter_block; |
382 | walk_data.after_dom_children = uncprop_leave_block; | |
5f718c29 | 383 | walk_data.global_data = NULL; |
384 | walk_data.block_local_data_size = 0; | |
5f718c29 | 385 | |
386 | /* Now initialize the dominator walker. */ | |
387 | init_walk_dominator_tree (&walk_data); | |
388 | ||
389 | /* Recursively walk the dominator tree undoing unprofitable | |
390 | constant/copy propagations. */ | |
391 | walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR); | |
392 | ||
393 | /* Finalize and clean up. */ | |
394 | fini_walk_dominator_tree (&walk_data); | |
395 | ||
1a5e3743 | 396 | /* EQUIV_STACK should already be empty at this point, so we just |
397 | need to empty elements out of the hash table, free EQUIV_STACK, | |
398 | and cleanup the AUX field on the edges. */ | |
5f718c29 | 399 | htab_delete (equiv); |
1a5e3743 | 400 | VEC_free (tree, heap, equiv_stack); |
5f718c29 | 401 | FOR_EACH_BB (bb) |
402 | { | |
403 | edge e; | |
404 | edge_iterator ei; | |
405 | ||
406 | FOR_EACH_EDGE (e, ei, bb->succs) | |
407 | { | |
408 | if (e->aux) | |
409 | { | |
410 | free (e->aux); | |
411 | e->aux = NULL; | |
412 | } | |
413 | } | |
414 | } | |
2a1990e9 | 415 | return 0; |
5f718c29 | 416 | } |
417 | ||
418 | ||
419 | /* We have finished processing the dominator children of BB, perform | |
420 | any finalization actions in preparation for leaving this node in | |
421 | the dominator tree. */ | |
422 | ||
423 | static void | |
6bf320fb | 424 | uncprop_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, |
425 | basic_block bb ATTRIBUTE_UNUSED) | |
5f718c29 | 426 | { |
5f718c29 | 427 | /* Pop the topmost value off the equiv stack. */ |
1a5e3743 | 428 | tree value = VEC_pop (tree, equiv_stack); |
5f718c29 | 429 | |
430 | /* If that value was non-null, then pop the topmost equivalency off | |
431 | its equivalency stack. */ | |
432 | if (value != NULL) | |
433 | remove_equivalence (value); | |
434 | } | |
435 | ||
436 | /* Unpropagate values from PHI nodes in successor blocks of BB. */ | |
437 | ||
438 | static void | |
6bf320fb | 439 | uncprop_into_successor_phis (basic_block bb) |
5f718c29 | 440 | { |
441 | edge e; | |
442 | edge_iterator ei; | |
443 | ||
444 | /* For each successor edge, first temporarily record any equivalence | |
445 | on that edge. Then unpropagate values in any PHI nodes at the | |
446 | destination of the edge. Then remove the temporary equivalence. */ | |
447 | FOR_EACH_EDGE (e, ei, bb->succs) | |
448 | { | |
75a70cf9 | 449 | gimple_seq phis = phi_nodes (e->dest); |
450 | gimple_stmt_iterator gsi; | |
5f718c29 | 451 | |
452 | /* If there are no PHI nodes in this destination, then there is | |
453 | no sense in recording any equivalences. */ | |
be2517f5 | 454 | if (gimple_seq_empty_p (phis)) |
5f718c29 | 455 | continue; |
456 | ||
457 | /* Record any equivalency associated with E. */ | |
458 | if (e->aux) | |
459 | { | |
945865c5 | 460 | struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux; |
5f718c29 | 461 | record_equiv (equiv->rhs, equiv->lhs); |
462 | } | |
463 | ||
464 | /* Walk over the PHI nodes, unpropagating values. */ | |
75a70cf9 | 465 | for (gsi = gsi_start (phis) ; !gsi_end_p (gsi); gsi_next (&gsi)) |
5f718c29 | 466 | { |
75a70cf9 | 467 | gimple phi = gsi_stmt (gsi); |
5f718c29 | 468 | tree arg = PHI_ARG_DEF (phi, e->dest_idx); |
469 | struct equiv_hash_elt equiv_hash_elt; | |
470 | void **slot; | |
471 | ||
472 | /* If the argument is not an invariant, or refers to the same | |
473 | underlying variable as the PHI result, then there's no | |
474 | point in un-propagating the argument. */ | |
475 | if (!is_gimple_min_invariant (arg) | |
476 | && SSA_NAME_VAR (arg) != SSA_NAME_VAR (PHI_RESULT (phi))) | |
477 | continue; | |
478 | ||
479 | /* Lookup this argument's value in the hash table. */ | |
480 | equiv_hash_elt.value = arg; | |
481 | equiv_hash_elt.equivalences = NULL; | |
482 | slot = htab_find_slot (equiv, &equiv_hash_elt, NO_INSERT); | |
483 | ||
484 | if (slot) | |
485 | { | |
945865c5 | 486 | struct equiv_hash_elt *elt = (struct equiv_hash_elt *) *slot; |
5f718c29 | 487 | int j; |
488 | ||
489 | /* Walk every equivalence with the same value. If we find | |
490 | one with the same underlying variable as the PHI result, | |
491 | then replace the value in the argument with its equivalent | |
25f6297d | 492 | SSA_NAME. Use the most recent equivalence as hopefully |
5f718c29 | 493 | that results in shortest lifetimes. */ |
96a7ab57 | 494 | for (j = VEC_length (tree, elt->equivalences) - 1; j >= 0; j--) |
5f718c29 | 495 | { |
96a7ab57 | 496 | tree equiv = VEC_index (tree, elt->equivalences, j); |
5f718c29 | 497 | |
498 | if (SSA_NAME_VAR (equiv) == SSA_NAME_VAR (PHI_RESULT (phi))) | |
499 | { | |
500 | SET_PHI_ARG_DEF (phi, e->dest_idx, equiv); | |
501 | break; | |
502 | } | |
503 | } | |
504 | } | |
505 | } | |
506 | ||
507 | /* If we had an equivalence associated with this edge, remove it. */ | |
508 | if (e->aux) | |
509 | { | |
945865c5 | 510 | struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux; |
5f718c29 | 511 | remove_equivalence (equiv->rhs); |
512 | } | |
513 | } | |
514 | } | |
515 | ||
516 | /* Ignoring loop backedges, if BB has precisely one incoming edge then | |
517 | return that edge. Otherwise return NULL. */ | |
518 | static edge | |
519 | single_incoming_edge_ignoring_loop_edges (basic_block bb) | |
520 | { | |
521 | edge retval = NULL; | |
522 | edge e; | |
523 | edge_iterator ei; | |
524 | ||
525 | FOR_EACH_EDGE (e, ei, bb->preds) | |
526 | { | |
527 | /* A loop back edge can be identified by the destination of | |
528 | the edge dominating the source of the edge. */ | |
529 | if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest)) | |
530 | continue; | |
531 | ||
532 | /* If we have already seen a non-loop edge, then we must have | |
533 | multiple incoming non-loop edges and thus we return NULL. */ | |
534 | if (retval) | |
535 | return NULL; | |
536 | ||
537 | /* This is the first non-loop incoming edge we have found. Record | |
538 | it. */ | |
539 | retval = e; | |
540 | } | |
541 | ||
542 | return retval; | |
543 | } | |
544 | ||
545 | static void | |
6bf320fb | 546 | uncprop_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, |
547 | basic_block bb) | |
5f718c29 | 548 | { |
549 | basic_block parent; | |
550 | edge e; | |
551 | bool recorded = false; | |
552 | ||
553 | /* If this block is dominated by a single incoming edge and that edge | |
554 | has an equivalency, then record the equivalency and push the | |
555 | VALUE onto EQUIV_STACK. Else push a NULL entry on EQUIV_STACK. */ | |
556 | parent = get_immediate_dominator (CDI_DOMINATORS, bb); | |
557 | if (parent) | |
558 | { | |
559 | e = single_incoming_edge_ignoring_loop_edges (bb); | |
560 | ||
561 | if (e && e->src == parent && e->aux) | |
562 | { | |
945865c5 | 563 | struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux; |
5f718c29 | 564 | |
565 | record_equiv (equiv->rhs, equiv->lhs); | |
1a5e3743 | 566 | VEC_safe_push (tree, heap, equiv_stack, equiv->rhs); |
5f718c29 | 567 | recorded = true; |
568 | } | |
569 | } | |
570 | ||
571 | if (!recorded) | |
1a5e3743 | 572 | VEC_safe_push (tree, heap, equiv_stack, NULL_TREE); |
6bf320fb | 573 | |
574 | uncprop_into_successor_phis (bb); | |
5f718c29 | 575 | } |
576 | ||
577 | static bool | |
578 | gate_uncprop (void) | |
579 | { | |
580 | return flag_tree_dom != 0; | |
581 | } | |
582 | ||
48e1416a | 583 | struct gimple_opt_pass pass_uncprop = |
5f718c29 | 584 | { |
20099e35 | 585 | { |
586 | GIMPLE_PASS, | |
5f718c29 | 587 | "uncprop", /* name */ |
588 | gate_uncprop, /* gate */ | |
589 | tree_ssa_uncprop, /* execute */ | |
590 | NULL, /* sub */ | |
591 | NULL, /* next */ | |
592 | 0, /* static_pass_number */ | |
593 | TV_TREE_SSA_UNCPROP, /* tv_id */ | |
594 | PROP_cfg | PROP_ssa, /* properties_required */ | |
595 | 0, /* properties_provided */ | |
596 | 0, /* properties_destroyed */ | |
597 | 0, /* todo_flags_start */ | |
771e2890 | 598 | TODO_verify_ssa /* todo_flags_finish */ |
20099e35 | 599 | } |
5f718c29 | 600 | }; |