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