1 | /* Routines for discovering and unpropagating edge equivalences. |
2 | Copyright (C) 2005-2017 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 "backend.h" |
24 | #include "tree.h" |
25 | #include "gimple.h" |
26 | #include "tree-pass.h" |
27 | #include "ssa.h" |
28 | #include "fold-const.h" |
29 | #include "cfganal.h" |
30 | #include "gimple-iterator.h" |
31 | #include "tree-cfg.h" |
32 | #include "domwalk.h" |
33 | #include "tree-hash-traits.h" |
34 | #include "tree-ssa-live.h" |
35 | #include "tree-ssa-coalesce.h" |
36 | |
37 | /* The basic structure describing an equivalency created by traversing |
38 | an edge. Traversing the edge effectively means that we can assume |
39 | that we've seen an assignment LHS = RHS. */ |
40 | struct edge_equivalency |
41 | { |
42 | tree rhs; |
43 | tree lhs; |
44 | }; |
45 | |
46 | /* This routine finds and records edge equivalences for every edge |
47 | in the CFG. |
48 | |
49 | When complete, each edge that creates an equivalency will have an |
50 | EDGE_EQUIVALENCY structure hanging off the edge's AUX field. |
51 | The caller is responsible for freeing the AUX fields. */ |
52 | |
53 | static void |
54 | associate_equivalences_with_edges (void) |
55 | { |
56 | basic_block bb; |
57 | |
58 | /* Walk over each block. If the block ends with a control statement, |
59 | then it might create a useful equivalence. */ |
60 | FOR_EACH_BB_FN (bb, cfun) |
61 | { |
62 | gimple_stmt_iterator gsi = gsi_last_bb (bb); |
63 | gimple *stmt; |
64 | |
65 | /* If the block does not end with a COND_EXPR or SWITCH_EXPR |
66 | then there is nothing to do. */ |
67 | if (gsi_end_p (gsi)) |
68 | continue; |
69 | |
70 | stmt = gsi_stmt (gsi); |
71 | |
72 | if (!stmt) |
73 | continue; |
74 | |
75 | /* A COND_EXPR may create an equivalency in a variety of different |
76 | ways. */ |
77 | if (gimple_code (stmt) == GIMPLE_COND) |
78 | { |
79 | edge true_edge; |
80 | edge false_edge; |
81 | struct edge_equivalency *equivalency; |
82 | enum tree_code code = gimple_cond_code (stmt); |
83 | |
84 | extract_true_false_edges_from_block (bb, &true_edge, &false_edge); |
85 | |
86 | /* Equality tests may create one or two equivalences. */ |
87 | if (code == EQ_EXPR || code == NE_EXPR) |
88 | { |
89 | tree op0 = gimple_cond_lhs (stmt); |
90 | tree op1 = gimple_cond_rhs (stmt); |
91 | |
92 | /* Special case comparing booleans against a constant as we |
93 | know the value of OP0 on both arms of the branch. i.e., we |
94 | can record an equivalence for OP0 rather than COND. */ |
95 | if (TREE_CODE (op0) == SSA_NAME |
96 | && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0) |
97 | && ssa_name_has_boolean_range (op0) |
98 | && is_gimple_min_invariant (op1) |
99 | && (integer_zerop (op1) || integer_onep (op1))) |
100 | { |
101 | tree true_val = constant_boolean_node (true, TREE_TYPE (op0)); |
102 | tree false_val = constant_boolean_node (false, |
103 | TREE_TYPE (op0)); |
104 | if (code == EQ_EXPR) |
105 | { |
106 | equivalency = XNEW (struct edge_equivalency); |
107 | equivalency->lhs = op0; |
108 | equivalency->rhs = (integer_zerop (op1) |
109 | ? false_val |
110 | : true_val); |
111 | true_edge->aux = equivalency; |
112 | |
113 | equivalency = XNEW (struct edge_equivalency); |
114 | equivalency->lhs = op0; |
115 | equivalency->rhs = (integer_zerop (op1) |
116 | ? true_val |
117 | : false_val); |
118 | false_edge->aux = equivalency; |
119 | } |
120 | else |
121 | { |
122 | equivalency = XNEW (struct edge_equivalency); |
123 | equivalency->lhs = op0; |
124 | equivalency->rhs = (integer_zerop (op1) |
125 | ? true_val |
126 | : false_val); |
127 | true_edge->aux = equivalency; |
128 | |
129 | equivalency = XNEW (struct edge_equivalency); |
130 | equivalency->lhs = op0; |
131 | equivalency->rhs = (integer_zerop (op1) |
132 | ? false_val |
133 | : true_val); |
134 | false_edge->aux = equivalency; |
135 | } |
136 | } |
137 | |
138 | else if (TREE_CODE (op0) == SSA_NAME |
139 | && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0) |
140 | && (is_gimple_min_invariant (op1) |
141 | || (TREE_CODE (op1) == SSA_NAME |
142 | && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1)))) |
143 | { |
144 | /* For IEEE, -0.0 == 0.0, so we don't necessarily know |
145 | the sign of a variable compared against zero. If |
146 | we're honoring signed zeros, then we cannot record |
147 | this value unless we know that the value is nonzero. */ |
148 | if (HONOR_SIGNED_ZEROS (op0) |
149 | && (TREE_CODE (op1) != REAL_CST |
150 | || real_equal (&dconst0, &TREE_REAL_CST (op1)))) |
151 | continue; |
152 | |
153 | equivalency = XNEW (struct edge_equivalency); |
154 | equivalency->lhs = op0; |
155 | equivalency->rhs = op1; |
156 | if (code == EQ_EXPR) |
157 | true_edge->aux = equivalency; |
158 | else |
159 | false_edge->aux = equivalency; |
160 | |
161 | } |
162 | } |
163 | |
164 | /* ??? TRUTH_NOT_EXPR can create an equivalence too. */ |
165 | } |
166 | |
167 | /* For a SWITCH_EXPR, a case label which represents a single |
168 | value and which is the only case label which reaches the |
169 | target block creates an equivalence. */ |
170 | else if (gimple_code (stmt) == GIMPLE_SWITCH) |
171 | { |
172 | gswitch *switch_stmt = as_a <gswitch *> (stmt); |
173 | tree cond = gimple_switch_index (switch_stmt); |
174 | |
175 | if (TREE_CODE (cond) == SSA_NAME |
176 | && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond)) |
177 | { |
178 | int i, n_labels = gimple_switch_num_labels (switch_stmt); |
179 | tree *info = XCNEWVEC (tree, last_basic_block_for_fn (cfun)); |
180 | |
181 | /* Walk over the case label vector. Record blocks |
182 | which are reached by a single case label which represents |
183 | a single value. */ |
184 | for (i = 0; i < n_labels; i++) |
185 | { |
186 | tree label = gimple_switch_label (switch_stmt, i); |
187 | basic_block bb = label_to_block (CASE_LABEL (label)); |
188 | |
189 | if (CASE_HIGH (label) |
190 | || !CASE_LOW (label) |
191 | || info[bb->index]) |
192 | info[bb->index] = error_mark_node; |
193 | else |
194 | info[bb->index] = label; |
195 | } |
196 | |
197 | /* Now walk over the blocks to determine which ones were |
198 | marked as being reached by a useful case label. */ |
199 | for (i = 0; i < n_basic_blocks_for_fn (cfun); i++) |
200 | { |
201 | tree node = info[i]; |
202 | |
203 | if (node != NULL |
204 | && node != error_mark_node) |
205 | { |
206 | tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node)); |
207 | struct edge_equivalency *equivalency; |
208 | |
209 | /* Record an equivalency on the edge from BB to basic |
210 | block I. */ |
211 | equivalency = XNEW (struct edge_equivalency); |
212 | equivalency->rhs = x; |
213 | equivalency->lhs = cond; |
214 | find_edge (bb, BASIC_BLOCK_FOR_FN (cfun, i))->aux = |
215 | 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 | |
272 | /* Main structure for recording equivalences into our hash table. */ |
273 | struct equiv_hash_elt |
274 | { |
275 | /* The value/key of this entry. */ |
276 | tree value; |
277 | |
278 | /* List of SSA_NAMEs which have the same value/key. */ |
279 | vec<tree> equivalences; |
280 | }; |
281 | |
282 | /* Global hash table implementing a mapping from invariant values |
283 | to a list of SSA_NAMEs which have the same value. We might be |
284 | able to reuse tree-vn for this code. */ |
285 | static hash_map<tree, auto_vec<tree> > *val_ssa_equiv; |
286 | |
287 | static void uncprop_into_successor_phis (basic_block); |
288 | |
289 | /* Remove the most recently recorded equivalency for VALUE. */ |
290 | |
291 | static void |
292 | remove_equivalence (tree value) |
293 | { |
294 | val_ssa_equiv->get (value)->pop (); |
295 | } |
296 | |
297 | /* Record EQUIVALENCE = VALUE into our hash table. */ |
298 | |
299 | static void |
300 | record_equiv (tree value, tree equivalence) |
301 | { |
302 | val_ssa_equiv->get_or_insert (value).safe_push (equivalence); |
303 | } |
304 | |
305 | class uncprop_dom_walker : public dom_walker |
306 | { |
307 | public: |
308 | uncprop_dom_walker (cdi_direction direction) : dom_walker (direction) {} |
309 | |
310 | virtual edge before_dom_children (basic_block); |
311 | virtual void after_dom_children (basic_block); |
312 | |
313 | private: |
314 | |
315 | /* As we enter each block we record the value for any edge equivalency |
316 | leading to this block. If no such edge equivalency exists, then we |
317 | record NULL. These equivalences are live until we leave the dominator |
318 | subtree rooted at the block where we record the equivalency. */ |
319 | auto_vec<tree, 2> m_equiv_stack; |
320 | }; |
321 | |
322 | /* We have finished processing the dominator children of BB, perform |
323 | any finalization actions in preparation for leaving this node in |
324 | the dominator tree. */ |
325 | |
326 | void |
327 | uncprop_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED) |
328 | { |
329 | /* Pop the topmost value off the equiv stack. */ |
330 | tree value = m_equiv_stack.pop (); |
331 | |
332 | /* If that value was non-null, then pop the topmost equivalency off |
333 | its equivalency stack. */ |
334 | if (value != NULL) |
335 | remove_equivalence (value); |
336 | } |
337 | |
338 | /* Unpropagate values from PHI nodes in successor blocks of BB. */ |
339 | |
340 | static void |
341 | uncprop_into_successor_phis (basic_block bb) |
342 | { |
343 | edge e; |
344 | edge_iterator ei; |
345 | |
346 | /* For each successor edge, first temporarily record any equivalence |
347 | on that edge. Then unpropagate values in any PHI nodes at the |
348 | destination of the edge. Then remove the temporary equivalence. */ |
349 | FOR_EACH_EDGE (e, ei, bb->succs) |
350 | { |
351 | gimple_seq phis = phi_nodes (e->dest); |
352 | gimple_stmt_iterator gsi; |
353 | |
354 | /* If there are no PHI nodes in this destination, then there is |
355 | no sense in recording any equivalences. */ |
356 | if (gimple_seq_empty_p (phis)) |
357 | continue; |
358 | |
359 | /* Record any equivalency associated with E. */ |
360 | if (e->aux) |
361 | { |
362 | struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux; |
363 | record_equiv (equiv->rhs, equiv->lhs); |
364 | } |
365 | |
366 | /* Walk over the PHI nodes, unpropagating values. */ |
367 | for (gsi = gsi_start (phis) ; !gsi_end_p (gsi); gsi_next (&gsi)) |
368 | { |
369 | gimple *phi = gsi_stmt (gsi); |
370 | tree arg = PHI_ARG_DEF (phi, e->dest_idx); |
371 | tree res = PHI_RESULT (phi); |
372 | |
373 | /* If the argument is not an invariant and can be potentially |
374 | coalesced with the result, then there's no point in |
375 | un-propagating the argument. */ |
376 | if (!is_gimple_min_invariant (arg) |
377 | && gimple_can_coalesce_p (arg, res)) |
378 | continue; |
379 | |
380 | /* Lookup this argument's value in the hash table. */ |
381 | vec<tree> *equivalences = val_ssa_equiv->get (arg); |
382 | if (equivalences) |
383 | { |
384 | /* Walk every equivalence with the same value. If we find |
385 | one that can potentially coalesce with the PHI rsult, |
386 | then replace the value in the argument with its equivalent |
387 | SSA_NAME. Use the most recent equivalence as hopefully |
388 | that results in shortest lifetimes. */ |
389 | for (int j = equivalences->length () - 1; j >= 0; j--) |
390 | { |
391 | tree equiv = (*equivalences)[j]; |
392 | |
393 | if (gimple_can_coalesce_p (equiv, res)) |
394 | { |
395 | SET_PHI_ARG_DEF (phi, e->dest_idx, equiv); |
396 | break; |
397 | } |
398 | } |
399 | } |
400 | } |
401 | |
402 | /* If we had an equivalence associated with this edge, remove it. */ |
403 | if (e->aux) |
404 | { |
405 | struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux; |
406 | remove_equivalence (equiv->rhs); |
407 | } |
408 | } |
409 | } |
410 | |
411 | edge |
412 | uncprop_dom_walker::before_dom_children (basic_block bb) |
413 | { |
414 | basic_block parent; |
415 | bool recorded = false; |
416 | |
417 | /* If this block is dominated by a single incoming edge and that edge |
418 | has an equivalency, then record the equivalency and push the |
419 | VALUE onto EQUIV_STACK. Else push a NULL entry on EQUIV_STACK. */ |
420 | parent = get_immediate_dominator (CDI_DOMINATORS, bb); |
421 | if (parent) |
422 | { |
423 | edge e = single_pred_edge_ignoring_loop_edges (bb, false); |
424 | |
425 | if (e && e->src == parent && e->aux) |
426 | { |
427 | struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux; |
428 | |
429 | record_equiv (equiv->rhs, equiv->lhs); |
430 | m_equiv_stack.safe_push (equiv->rhs); |
431 | recorded = true; |
432 | } |
433 | } |
434 | |
435 | if (!recorded) |
436 | m_equiv_stack.safe_push (NULL_TREE); |
437 | |
438 | uncprop_into_successor_phis (bb); |
439 | return NULL; |
440 | } |
441 | |
442 | namespace { |
443 | |
444 | const pass_data pass_data_uncprop = |
445 | { |
446 | GIMPLE_PASS, /* type */ |
447 | "uncprop" , /* name */ |
448 | OPTGROUP_NONE, /* optinfo_flags */ |
449 | TV_TREE_SSA_UNCPROP, /* tv_id */ |
450 | ( PROP_cfg | PROP_ssa ), /* properties_required */ |
451 | 0, /* properties_provided */ |
452 | 0, /* properties_destroyed */ |
453 | 0, /* todo_flags_start */ |
454 | 0, /* todo_flags_finish */ |
455 | }; |
456 | |
457 | class pass_uncprop : public gimple_opt_pass |
458 | { |
459 | public: |
460 | pass_uncprop (gcc::context *ctxt) |
461 | : gimple_opt_pass (pass_data_uncprop, ctxt) |
462 | {} |
463 | |
464 | /* opt_pass methods: */ |
465 | opt_pass * clone () { return new pass_uncprop (m_ctxt); } |
466 | virtual bool gate (function *) { return flag_tree_dom != 0; } |
467 | virtual unsigned int execute (function *); |
468 | |
469 | }; // class pass_uncprop |
470 | |
471 | unsigned int |
472 | pass_uncprop::execute (function *fun) |
473 | { |
474 | basic_block bb; |
475 | |
476 | associate_equivalences_with_edges (); |
477 | |
478 | /* Create our global data structures. */ |
479 | val_ssa_equiv = new hash_map<tree, auto_vec<tree> > (1024); |
480 | |
481 | /* We're going to do a dominator walk, so ensure that we have |
482 | dominance information. */ |
483 | calculate_dominance_info (CDI_DOMINATORS); |
484 | |
485 | /* Recursively walk the dominator tree undoing unprofitable |
486 | constant/copy propagations. */ |
487 | uncprop_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr); |
488 | |
489 | /* we just need to empty elements out of the hash table, and cleanup the |
490 | AUX field on the edges. */ |
491 | delete val_ssa_equiv; |
492 | val_ssa_equiv = NULL; |
493 | FOR_EACH_BB_FN (bb, fun) |
494 | { |
495 | edge e; |
496 | edge_iterator ei; |
497 | |
498 | FOR_EACH_EDGE (e, ei, bb->succs) |
499 | { |
500 | if (e->aux) |
501 | { |
502 | free (e->aux); |
503 | e->aux = NULL; |
504 | } |
505 | } |
506 | } |
507 | return 0; |
508 | } |
509 | |
510 | } // anon namespace |
511 | |
512 | gimple_opt_pass * |
513 | make_pass_uncprop (gcc::context *ctxt) |
514 | { |
515 | return new pass_uncprop (ctxt); |
516 | } |
517 | |