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