]>
Commit | Line | Data |
---|---|---|
5f718c29 | 1 | /* Routines for discovering and unpropagating edge equivalences. |
fbd26352 | 2 | Copyright (C) 2005-2019 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" | |
9ef16211 | 23 | #include "backend.h" |
5f718c29 | 24 | #include "tree.h" |
9ef16211 | 25 | #include "gimple.h" |
7c29e30e | 26 | #include "tree-pass.h" |
9ef16211 | 27 | #include "ssa.h" |
b20a8bb4 | 28 | #include "fold-const.h" |
94ea8568 | 29 | #include "cfganal.h" |
dcf1a1ec | 30 | #include "gimple-iterator.h" |
073c1fd5 | 31 | #include "tree-cfg.h" |
5f718c29 | 32 | #include "domwalk.h" |
f4ff098a | 33 | #include "tree-hash-traits.h" |
94f92c36 | 34 | #include "tree-ssa-live.h" |
35 | #include "tree-ssa-coalesce.h" | |
5f718c29 | 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 | |
48e1416a | 50 | EDGE_EQUIVALENCY structure hanging off the edge's AUX field. |
5f718c29 | 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. */ | |
fc00614f | 60 | FOR_EACH_BB_FN (bb, cfun) |
5f718c29 | 61 | { |
75a70cf9 | 62 | gimple_stmt_iterator gsi = gsi_last_bb (bb); |
42acab1c | 63 | gimple *stmt; |
5f718c29 | 64 | |
65 | /* If the block does not end with a COND_EXPR or SWITCH_EXPR | |
66 | then there is nothing to do. */ | |
75a70cf9 | 67 | if (gsi_end_p (gsi)) |
5f718c29 | 68 | continue; |
69 | ||
75a70cf9 | 70 | stmt = gsi_stmt (gsi); |
5f718c29 | 71 | |
72 | if (!stmt) | |
73 | continue; | |
74 | ||
75 | /* A COND_EXPR may create an equivalency in a variety of different | |
76 | ways. */ | |
75a70cf9 | 77 | if (gimple_code (stmt) == GIMPLE_COND) |
5f718c29 | 78 | { |
5f718c29 | 79 | edge true_edge; |
80 | edge false_edge; | |
81 | struct edge_equivalency *equivalency; | |
75a70cf9 | 82 | enum tree_code code = gimple_cond_code (stmt); |
5f718c29 | 83 | |
84 | extract_true_false_edges_from_block (bb, &true_edge, &false_edge); | |
85 | ||
5f718c29 | 86 | /* Equality tests may create one or two equivalences. */ |
75a70cf9 | 87 | if (code == EQ_EXPR || code == NE_EXPR) |
5f718c29 | 88 | { |
75a70cf9 | 89 | tree op0 = gimple_cond_lhs (stmt); |
90 | tree op1 = gimple_cond_rhs (stmt); | |
5f718c29 | 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 | |
932540b6 | 96 | && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0) |
e390c57d | 97 | && ssa_name_has_boolean_range (op0) |
3a4d3de5 | 98 | && is_gimple_min_invariant (op1) |
99 | && (integer_zerop (op1) || integer_onep (op1))) | |
5f718c29 | 100 | { |
e390c57d | 101 | tree true_val = constant_boolean_node (true, TREE_TYPE (op0)); |
102 | tree false_val = constant_boolean_node (false, | |
103 | TREE_TYPE (op0)); | |
75a70cf9 | 104 | if (code == EQ_EXPR) |
5f718c29 | 105 | { |
945865c5 | 106 | equivalency = XNEW (struct edge_equivalency); |
5f718c29 | 107 | equivalency->lhs = op0; |
108 | equivalency->rhs = (integer_zerop (op1) | |
e390c57d | 109 | ? false_val |
110 | : true_val); | |
5f718c29 | 111 | true_edge->aux = equivalency; |
112 | ||
945865c5 | 113 | equivalency = XNEW (struct edge_equivalency); |
5f718c29 | 114 | equivalency->lhs = op0; |
115 | equivalency->rhs = (integer_zerop (op1) | |
e390c57d | 116 | ? true_val |
117 | : false_val); | |
5f718c29 | 118 | false_edge->aux = equivalency; |
119 | } | |
120 | else | |
121 | { | |
945865c5 | 122 | equivalency = XNEW (struct edge_equivalency); |
5f718c29 | 123 | equivalency->lhs = op0; |
124 | equivalency->rhs = (integer_zerop (op1) | |
e390c57d | 125 | ? true_val |
126 | : false_val); | |
5f718c29 | 127 | true_edge->aux = equivalency; |
128 | ||
945865c5 | 129 | equivalency = XNEW (struct edge_equivalency); |
5f718c29 | 130 | equivalency->lhs = op0; |
131 | equivalency->rhs = (integer_zerop (op1) | |
e390c57d | 132 | ? false_val |
133 | : true_val); | |
5f718c29 | 134 | false_edge->aux = equivalency; |
135 | } | |
136 | } | |
137 | ||
024e445d | 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)))) | |
5f718c29 | 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. */ | |
fe994837 | 148 | if (HONOR_SIGNED_ZEROS (op0) |
5f718c29 | 149 | && (TREE_CODE (op1) != REAL_CST |
20cb53c9 | 150 | || real_equal (&dconst0, &TREE_REAL_CST (op1)))) |
5f718c29 | 151 | continue; |
152 | ||
945865c5 | 153 | equivalency = XNEW (struct edge_equivalency); |
5f718c29 | 154 | equivalency->lhs = op0; |
155 | equivalency->rhs = op1; | |
75a70cf9 | 156 | if (code == EQ_EXPR) |
5f718c29 | 157 | true_edge->aux = equivalency; |
48e1416a | 158 | else |
5f718c29 | 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. */ | |
75a70cf9 | 170 | else if (gimple_code (stmt) == GIMPLE_SWITCH) |
5f718c29 | 171 | { |
1a91d914 | 172 | gswitch *switch_stmt = as_a <gswitch *> (stmt); |
173 | tree cond = gimple_switch_index (switch_stmt); | |
5f718c29 | 174 | |
932540b6 | 175 | if (TREE_CODE (cond) == SSA_NAME |
176 | && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond)) | |
5f718c29 | 177 | { |
1a91d914 | 178 | int i, n_labels = gimple_switch_num_labels (switch_stmt); |
fe672ac0 | 179 | tree *info = XCNEWVEC (tree, last_basic_block_for_fn (cfun)); |
5f718c29 | 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 | { | |
1a91d914 | 186 | tree label = gimple_switch_label (switch_stmt, i); |
0fb4f2ce | 187 | basic_block bb = label_to_block (cfun, CASE_LABEL (label)); |
5f718c29 | 188 | |
5f718c29 | 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. */ | |
a28770e1 | 199 | for (i = 0; i < n_basic_blocks_for_fn (cfun); i++) |
5f718c29 | 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. */ | |
945865c5 | 211 | equivalency = XNEW (struct edge_equivalency); |
5f718c29 | 212 | equivalency->rhs = x; |
213 | equivalency->lhs = cond; | |
f5a6b05f | 214 | find_edge (bb, BASIC_BLOCK_FOR_FN (cfun, i))->aux = |
215 | equivalency; | |
5f718c29 | 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 | |
25f6297d | 247 | the SSA optimizers to do a better job. However, in the cases |
5f718c29 | 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 | ||
dc4e0f45 | 271 | typedef hash_map<tree_operand_hash, auto_vec<tree> > val_ssa_equiv_t; |
d0085ba9 | 272 | |
d9dd21a8 | 273 | /* Global hash table implementing a mapping from invariant values |
274 | to a list of SSA_NAMEs which have the same value. We might be | |
275 | able to reuse tree-vn for this code. */ | |
d0085ba9 | 276 | val_ssa_equiv_t *val_ssa_equiv; |
d9dd21a8 | 277 | |
d9dd21a8 | 278 | static void uncprop_into_successor_phis (basic_block); |
279 | ||
5f718c29 | 280 | /* Remove the most recently recorded equivalency for VALUE. */ |
281 | ||
282 | static void | |
283 | remove_equivalence (tree value) | |
284 | { | |
d62dd039 | 285 | val_ssa_equiv->get (value)->pop (); |
5f718c29 | 286 | } |
287 | ||
288 | /* Record EQUIVALENCE = VALUE into our hash table. */ | |
289 | ||
290 | static void | |
291 | record_equiv (tree value, tree equivalence) | |
292 | { | |
d62dd039 | 293 | val_ssa_equiv->get_or_insert (value).safe_push (equivalence); |
5f718c29 | 294 | } |
295 | ||
54c91640 | 296 | class uncprop_dom_walker : public dom_walker |
297 | { | |
298 | public: | |
e85cf4e5 | 299 | uncprop_dom_walker (cdi_direction direction) : dom_walker (direction) {} |
54c91640 | 300 | |
96752458 | 301 | virtual edge before_dom_children (basic_block); |
54c91640 | 302 | virtual void after_dom_children (basic_block); |
303 | ||
304 | private: | |
305 | ||
ae84f584 | 306 | /* As we enter each block we record the value for any edge equivalency |
307 | leading to this block. If no such edge equivalency exists, then we | |
308 | record NULL. These equivalences are live until we leave the dominator | |
309 | subtree rooted at the block where we record the equivalency. */ | |
4997014d | 310 | auto_vec<tree, 2> m_equiv_stack; |
54c91640 | 311 | }; |
312 | ||
5f718c29 | 313 | /* We have finished processing the dominator children of BB, perform |
314 | any finalization actions in preparation for leaving this node in | |
315 | the dominator tree. */ | |
316 | ||
54c91640 | 317 | void |
318 | uncprop_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED) | |
5f718c29 | 319 | { |
5f718c29 | 320 | /* Pop the topmost value off the equiv stack. */ |
ae84f584 | 321 | tree value = m_equiv_stack.pop (); |
5f718c29 | 322 | |
323 | /* If that value was non-null, then pop the topmost equivalency off | |
324 | its equivalency stack. */ | |
325 | if (value != NULL) | |
326 | remove_equivalence (value); | |
327 | } | |
328 | ||
329 | /* Unpropagate values from PHI nodes in successor blocks of BB. */ | |
330 | ||
331 | static void | |
6bf320fb | 332 | uncprop_into_successor_phis (basic_block bb) |
5f718c29 | 333 | { |
334 | edge e; | |
335 | edge_iterator ei; | |
336 | ||
337 | /* For each successor edge, first temporarily record any equivalence | |
338 | on that edge. Then unpropagate values in any PHI nodes at the | |
339 | destination of the edge. Then remove the temporary equivalence. */ | |
340 | FOR_EACH_EDGE (e, ei, bb->succs) | |
341 | { | |
75a70cf9 | 342 | gimple_seq phis = phi_nodes (e->dest); |
343 | gimple_stmt_iterator gsi; | |
5f718c29 | 344 | |
345 | /* If there are no PHI nodes in this destination, then there is | |
346 | no sense in recording any equivalences. */ | |
be2517f5 | 347 | if (gimple_seq_empty_p (phis)) |
5f718c29 | 348 | continue; |
349 | ||
350 | /* Record any equivalency associated with E. */ | |
351 | if (e->aux) | |
352 | { | |
945865c5 | 353 | struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux; |
5f718c29 | 354 | record_equiv (equiv->rhs, equiv->lhs); |
355 | } | |
356 | ||
357 | /* Walk over the PHI nodes, unpropagating values. */ | |
75a70cf9 | 358 | for (gsi = gsi_start (phis) ; !gsi_end_p (gsi); gsi_next (&gsi)) |
5f718c29 | 359 | { |
42acab1c | 360 | gimple *phi = gsi_stmt (gsi); |
5f718c29 | 361 | tree arg = PHI_ARG_DEF (phi, e->dest_idx); |
ec11736b | 362 | tree res = PHI_RESULT (phi); |
5f718c29 | 363 | |
f82f0ea5 | 364 | /* If the argument is not an invariant and can be potentially |
365 | coalesced with the result, then there's no point in | |
366 | un-propagating the argument. */ | |
5f718c29 | 367 | if (!is_gimple_min_invariant (arg) |
f82f0ea5 | 368 | && gimple_can_coalesce_p (arg, res)) |
5f718c29 | 369 | continue; |
370 | ||
371 | /* Lookup this argument's value in the hash table. */ | |
d62dd039 | 372 | vec<tree> *equivalences = val_ssa_equiv->get (arg); |
373 | if (equivalences) | |
5f718c29 | 374 | { |
5f718c29 | 375 | /* Walk every equivalence with the same value. If we find |
f82f0ea5 | 376 | one that can potentially coalesce with the PHI rsult, |
5f718c29 | 377 | then replace the value in the argument with its equivalent |
25f6297d | 378 | SSA_NAME. Use the most recent equivalence as hopefully |
5f718c29 | 379 | that results in shortest lifetimes. */ |
d62dd039 | 380 | for (int j = equivalences->length () - 1; j >= 0; j--) |
5f718c29 | 381 | { |
d62dd039 | 382 | tree equiv = (*equivalences)[j]; |
5f718c29 | 383 | |
f82f0ea5 | 384 | if (gimple_can_coalesce_p (equiv, res)) |
5f718c29 | 385 | { |
386 | SET_PHI_ARG_DEF (phi, e->dest_idx, equiv); | |
387 | break; | |
388 | } | |
389 | } | |
390 | } | |
391 | } | |
392 | ||
393 | /* If we had an equivalence associated with this edge, remove it. */ | |
394 | if (e->aux) | |
395 | { | |
945865c5 | 396 | struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux; |
5f718c29 | 397 | remove_equivalence (equiv->rhs); |
398 | } | |
399 | } | |
400 | } | |
401 | ||
96752458 | 402 | edge |
54c91640 | 403 | uncprop_dom_walker::before_dom_children (basic_block bb) |
5f718c29 | 404 | { |
405 | basic_block parent; | |
5f718c29 | 406 | bool recorded = false; |
407 | ||
408 | /* If this block is dominated by a single incoming edge and that edge | |
409 | has an equivalency, then record the equivalency and push the | |
410 | VALUE onto EQUIV_STACK. Else push a NULL entry on EQUIV_STACK. */ | |
411 | parent = get_immediate_dominator (CDI_DOMINATORS, bb); | |
412 | if (parent) | |
413 | { | |
1477a5a7 | 414 | edge e = single_pred_edge_ignoring_loop_edges (bb, false); |
5f718c29 | 415 | |
416 | if (e && e->src == parent && e->aux) | |
417 | { | |
945865c5 | 418 | struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux; |
5f718c29 | 419 | |
420 | record_equiv (equiv->rhs, equiv->lhs); | |
ae84f584 | 421 | m_equiv_stack.safe_push (equiv->rhs); |
5f718c29 | 422 | recorded = true; |
423 | } | |
424 | } | |
425 | ||
426 | if (!recorded) | |
ae84f584 | 427 | m_equiv_stack.safe_push (NULL_TREE); |
6bf320fb | 428 | |
429 | uncprop_into_successor_phis (bb); | |
96752458 | 430 | return NULL; |
5f718c29 | 431 | } |
432 | ||
cbe8bda8 | 433 | namespace { |
434 | ||
435 | const pass_data pass_data_uncprop = | |
5f718c29 | 436 | { |
cbe8bda8 | 437 | GIMPLE_PASS, /* type */ |
438 | "uncprop", /* name */ | |
439 | OPTGROUP_NONE, /* optinfo_flags */ | |
cbe8bda8 | 440 | TV_TREE_SSA_UNCPROP, /* tv_id */ |
441 | ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
442 | 0, /* properties_provided */ | |
443 | 0, /* properties_destroyed */ | |
444 | 0, /* todo_flags_start */ | |
8b88439e | 445 | 0, /* todo_flags_finish */ |
5f718c29 | 446 | }; |
cbe8bda8 | 447 | |
448 | class pass_uncprop : public gimple_opt_pass | |
449 | { | |
450 | public: | |
9af5ce0c | 451 | pass_uncprop (gcc::context *ctxt) |
452 | : gimple_opt_pass (pass_data_uncprop, ctxt) | |
cbe8bda8 | 453 | {} |
454 | ||
455 | /* opt_pass methods: */ | |
ae84f584 | 456 | opt_pass * clone () { return new pass_uncprop (m_ctxt); } |
31315c24 | 457 | virtual bool gate (function *) { return flag_tree_dom != 0; } |
65b0537f | 458 | virtual unsigned int execute (function *); |
cbe8bda8 | 459 | |
460 | }; // class pass_uncprop | |
461 | ||
65b0537f | 462 | unsigned int |
463 | pass_uncprop::execute (function *fun) | |
464 | { | |
465 | basic_block bb; | |
466 | ||
467 | associate_equivalences_with_edges (); | |
468 | ||
469 | /* Create our global data structures. */ | |
d0085ba9 | 470 | val_ssa_equiv = new val_ssa_equiv_t (1024); |
65b0537f | 471 | |
472 | /* We're going to do a dominator walk, so ensure that we have | |
473 | dominance information. */ | |
474 | calculate_dominance_info (CDI_DOMINATORS); | |
475 | ||
476 | /* Recursively walk the dominator tree undoing unprofitable | |
477 | constant/copy propagations. */ | |
478 | uncprop_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr); | |
479 | ||
480 | /* we just need to empty elements out of the hash table, and cleanup the | |
481 | AUX field on the edges. */ | |
c1f445d2 | 482 | delete val_ssa_equiv; |
483 | val_ssa_equiv = NULL; | |
65b0537f | 484 | FOR_EACH_BB_FN (bb, fun) |
485 | { | |
486 | edge e; | |
487 | edge_iterator ei; | |
488 | ||
489 | FOR_EACH_EDGE (e, ei, bb->succs) | |
490 | { | |
491 | if (e->aux) | |
492 | { | |
493 | free (e->aux); | |
494 | e->aux = NULL; | |
495 | } | |
496 | } | |
497 | } | |
498 | return 0; | |
499 | } | |
500 | ||
cbe8bda8 | 501 | } // anon namespace |
502 | ||
503 | gimple_opt_pass * | |
504 | make_pass_uncprop (gcc::context *ctxt) | |
505 | { | |
506 | return new pass_uncprop (ctxt); | |
507 | } |