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