Line data Source code
1 : /* Routines for discovering and unpropagating edge equivalences.
2 : Copyright (C) 2005-2026 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 1046371 : associate_equivalences_with_edges (void)
55 : {
56 1046371 : 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 14620805 : FOR_EACH_BB_FN (bb, cfun)
61 : {
62 13574434 : gimple_stmt_iterator gsi = gsi_last_bb (bb);
63 13574434 : 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 13574434 : if (gsi_end_p (gsi))
68 13574434 : continue;
69 :
70 9562170 : stmt = gsi_stmt (gsi);
71 :
72 9562170 : if (!stmt)
73 : continue;
74 :
75 : /* A COND_EXPR may create an equivalency in a variety of different
76 : ways. */
77 9562170 : if (gimple_code (stmt) == GIMPLE_COND)
78 : {
79 4340312 : edge true_edge;
80 4340312 : edge false_edge;
81 4340312 : struct edge_equivalency *equivalency;
82 4340312 : enum tree_code code = gimple_cond_code (stmt);
83 :
84 4340312 : extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
85 :
86 : /* Equality tests may create one or two equivalences. */
87 4340312 : if (code == EQ_EXPR || code == NE_EXPR)
88 : {
89 3519089 : tree op0 = gimple_cond_lhs (stmt);
90 3519089 : 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 3519089 : if (TREE_CODE (op0) == SSA_NAME
96 3518438 : && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)
97 3518314 : && ssa_name_has_boolean_range (op0)
98 458006 : && is_gimple_min_invariant (op1)
99 3961167 : && (integer_zerop (op1) || integer_onep (op1)))
100 : {
101 442078 : tree true_val = constant_boolean_node (true, TREE_TYPE (op0));
102 442078 : tree false_val = constant_boolean_node (false,
103 442078 : TREE_TYPE (op0));
104 442078 : if (code == EQ_EXPR)
105 : {
106 11165 : equivalency = XNEW (struct edge_equivalency);
107 11165 : equivalency->lhs = op0;
108 11165 : equivalency->rhs = (integer_zerop (op1)
109 11165 : ? false_val
110 : : true_val);
111 11165 : true_edge->aux = equivalency;
112 :
113 11165 : equivalency = XNEW (struct edge_equivalency);
114 11165 : equivalency->lhs = op0;
115 11165 : equivalency->rhs = (integer_zerop (op1)
116 11165 : ? true_val
117 : : false_val);
118 11165 : false_edge->aux = equivalency;
119 : }
120 : else
121 : {
122 430913 : equivalency = XNEW (struct edge_equivalency);
123 430913 : equivalency->lhs = op0;
124 430913 : equivalency->rhs = (integer_zerop (op1)
125 430913 : ? true_val
126 : : false_val);
127 430913 : true_edge->aux = equivalency;
128 :
129 430913 : equivalency = XNEW (struct edge_equivalency);
130 430913 : equivalency->lhs = op0;
131 430913 : equivalency->rhs = (integer_zerop (op1)
132 430913 : ? false_val
133 : : true_val);
134 430913 : false_edge->aux = equivalency;
135 : }
136 : }
137 :
138 3077011 : else if (TREE_CODE (op0) == SSA_NAME
139 3076360 : && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)
140 6153247 : && (is_gimple_min_invariant (op1)
141 719103 : || (TREE_CODE (op1) == SSA_NAME
142 719103 : && !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 3076235 : if (HONOR_SIGNED_ZEROS (op0)
149 3076235 : && (TREE_CODE (op1) != REAL_CST
150 86635 : || real_equal (&dconst0, &TREE_REAL_CST (op1))))
151 51538 : continue;
152 :
153 3024697 : equivalency = XNEW (struct edge_equivalency);
154 3024697 : equivalency->lhs = op0;
155 3024697 : equivalency->rhs = op1;
156 3024697 : if (code == EQ_EXPR)
157 1413637 : true_edge->aux = equivalency;
158 : else
159 1611060 : 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 5221858 : else if (gimple_code (stmt) == GIMPLE_SWITCH)
171 : {
172 6313 : gswitch *switch_stmt = as_a <gswitch *> (stmt);
173 6313 : tree cond = gimple_switch_index (switch_stmt);
174 :
175 6313 : if (TREE_CODE (cond) == SSA_NAME
176 6313 : && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond))
177 : {
178 6313 : int i, n_labels = gimple_switch_num_labels (switch_stmt);
179 : /* info contains NULL, error_mark_node or a value.
180 : error_mark signifies there are multiple values already.
181 : A NULL signifies there it is uninitialized.
182 : A value signifies that is the only value on that edge
183 : to that bb. */
184 6313 : tree *info = XCNEWVEC (tree, last_basic_block_for_fn (cfun));
185 :
186 : /* Walk over the case label vector. Record blocks
187 : which are reached by a single case label which represents
188 : a single value. */
189 78355 : for (i = 0; i < n_labels; i++)
190 : {
191 72042 : tree label = gimple_switch_label (switch_stmt, i);
192 72042 : basic_block bb = label_to_block (cfun, CASE_LABEL (label));
193 :
194 : /* The default case is a case with multiple values.
195 : If the value is already set then it has multiple
196 : values. */
197 72042 : if (CASE_HIGH (label)
198 67856 : || !CASE_LOW (label)
199 133585 : || info[bb->index])
200 16205 : info[bb->index] = error_mark_node;
201 : else
202 : /* Record the one value that can be on that edge to the
203 : target_bb. */
204 55837 : info[bb->index] = CASE_LOW (label);
205 : }
206 :
207 : /* Now walk over the blocks to determine which ones were
208 : marked as being reached by a useful case label. */
209 963066 : for (i = 0; i < n_basic_blocks_for_fn (cfun); i++)
210 : {
211 956753 : tree value = info[i];
212 :
213 956753 : if (value != NULL
214 65586 : && value != error_mark_node)
215 : {
216 51168 : tree x = fold_convert (TREE_TYPE (cond), value);
217 51168 : struct edge_equivalency *equivalency;
218 :
219 : /* Record an equivalency on the edge from BB to basic
220 : block I. */
221 51168 : equivalency = XNEW (struct edge_equivalency);
222 51168 : equivalency->rhs = x;
223 51168 : equivalency->lhs = cond;
224 51168 : find_edge (bb, BASIC_BLOCK_FOR_FN (cfun, i))->aux =
225 : equivalency;
226 : }
227 : }
228 6313 : free (info);
229 : }
230 : }
231 :
232 : }
233 1046371 : }
234 :
235 :
236 : /* Translating out of SSA sometimes requires inserting copies and
237 : constant initializations on edges to eliminate PHI nodes.
238 :
239 : In some cases those copies and constant initializations are
240 : redundant because the target already has the value on the
241 : RHS of the assignment.
242 :
243 : We previously tried to catch these cases after translating
244 : out of SSA form. However, that code often missed cases. Worse
245 : yet, the cases it missed were also often missed by the RTL
246 : optimizers. Thus the resulting code had redundant instructions.
247 :
248 : This pass attempts to detect these situations before translating
249 : out of SSA form.
250 :
251 : The key concept that this pass is built upon is that these
252 : redundant copies and constant initializations often occur
253 : due to constant/copy propagating equivalences resulting from
254 : COND_EXPRs and SWITCH_EXPRs.
255 :
256 : We want to do those propagations as they can sometimes allow
257 : the SSA optimizers to do a better job. However, in the cases
258 : where such propagations do not result in further optimization,
259 : we would like to "undo" the propagation to avoid the redundant
260 : copies and constant initializations.
261 :
262 : This pass works by first associating equivalences with edges in
263 : the CFG. For example, the edge leading from a SWITCH_EXPR to
264 : its associated CASE_LABEL will have an equivalency between
265 : SWITCH_COND and the value in the case label.
266 :
267 : Once we have found the edge equivalences, we proceed to walk
268 : the CFG in dominator order. As we traverse edges we record
269 : equivalences associated with those edges we traverse.
270 :
271 : When we encounter a PHI node, we walk its arguments to see if we
272 : have an equivalence for the PHI argument. If so, then we replace
273 : the argument.
274 :
275 : Equivalences are looked up based on their value (think of it as
276 : the RHS of an assignment). A value may be an SSA_NAME or an
277 : invariant. We may have several SSA_NAMEs with the same value,
278 : so with each value we have a list of SSA_NAMEs that have the
279 : same value. */
280 :
281 : typedef hash_map<tree_operand_hash, auto_vec<tree> > val_ssa_equiv_t;
282 :
283 : /* Global hash table implementing a mapping from invariant values
284 : to a list of SSA_NAMEs which have the same value. We might be
285 : able to reuse tree-vn for this code. */
286 : val_ssa_equiv_t *val_ssa_equiv;
287 :
288 : static void uncprop_into_successor_phis (basic_block);
289 :
290 : /* Remove the most recently recorded equivalency for VALUE. */
291 :
292 : static void
293 3959306 : remove_equivalence (tree value)
294 : {
295 3959306 : val_ssa_equiv->get (value)->pop ();
296 3959306 : }
297 :
298 : /* Record EQUIVALENCE = VALUE into our hash table. */
299 :
300 : static void
301 3959306 : record_equiv (tree value, tree equivalence)
302 : {
303 3959306 : val_ssa_equiv->get_or_insert (value).safe_push (equivalence);
304 3959306 : }
305 :
306 : class uncprop_dom_walker : public dom_walker
307 : {
308 : public:
309 1046371 : uncprop_dom_walker (cdi_direction direction) : dom_walker (direction) {}
310 :
311 : edge before_dom_children (basic_block) final override;
312 : void after_dom_children (basic_block) final override;
313 :
314 : private:
315 :
316 : /* As we enter each block we record the value for any edge equivalency
317 : leading to this block. If no such edge equivalency exists, then we
318 : record NULL. These equivalences are live until we leave the dominator
319 : subtree rooted at the block where we record the equivalency. */
320 : auto_vec<tree, 2> m_equiv_stack;
321 : };
322 :
323 : /* We have finished processing the dominator children of BB, perform
324 : any finalization actions in preparation for leaving this node in
325 : the dominator tree. */
326 :
327 : void
328 14620805 : uncprop_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
329 : {
330 : /* Pop the topmost value off the equiv stack. */
331 14620805 : tree value = m_equiv_stack.pop ();
332 :
333 : /* If that value was non-null, then pop the topmost equivalency off
334 : its equivalency stack. */
335 14620805 : if (value != NULL)
336 3957971 : remove_equivalence (value);
337 14620805 : }
338 :
339 : /* Unpropagate values from PHI nodes in successor blocks of BB. */
340 :
341 : static void
342 14620805 : uncprop_into_successor_phis (basic_block bb)
343 : {
344 14620805 : edge e;
345 14620805 : edge_iterator ei;
346 :
347 : /* For each successor edge, first temporarily record any equivalence
348 : on that edge. Then unpropagate values in any PHI nodes at the
349 : destination of the edge. Then remove the temporary equivalence. */
350 33646913 : FOR_EACH_EDGE (e, ei, bb->succs)
351 : {
352 19026108 : gimple_seq phis = phi_nodes (e->dest);
353 19026108 : gimple_stmt_iterator gsi;
354 :
355 : /* If there are no PHI nodes in this destination, then there is
356 : no sense in recording any equivalences. */
357 19026108 : if (gimple_seq_empty_p (phis))
358 12681223 : continue;
359 :
360 : /* Record any equivalency associated with E. */
361 6344885 : if (e->aux)
362 : {
363 1335 : struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
364 1335 : record_equiv (equiv->rhs, equiv->lhs);
365 : }
366 :
367 : /* Walk over the PHI nodes, unpropagating values. */
368 17974157 : for (gsi = gsi_start (phis) ; !gsi_end_p (gsi); gsi_next (&gsi))
369 : {
370 11629272 : gimple *phi = gsi_stmt (gsi);
371 11629272 : tree arg = PHI_ARG_DEF (phi, e->dest_idx);
372 11629272 : tree res = PHI_RESULT (phi);
373 :
374 : /* If the argument is not an invariant and can be potentially
375 : coalesced with the result, then there's no point in
376 : un-propagating the argument. */
377 11629272 : if (!is_gimple_min_invariant (arg)
378 11629272 : && gimple_can_coalesce_p (arg, res))
379 10105935 : continue;
380 :
381 : /* Lookup this argument's value in the hash table. */
382 1523337 : vec<tree> *equivalences = val_ssa_equiv->get (arg);
383 1523337 : if (equivalences)
384 : {
385 : /* Walk every equivalence with the same value. If we find
386 : one that can potentially coalesce with the PHI rsult,
387 : then replace the value in the argument with its equivalent
388 : SSA_NAME. Use the most recent equivalence as hopefully
389 : that results in shortest lifetimes. */
390 2121472 : for (int j = equivalences->length () - 1; j >= 0; j--)
391 : {
392 804566 : tree equiv = (*equivalences)[j];
393 :
394 804566 : if (gimple_can_coalesce_p (equiv, res))
395 : {
396 185640 : SET_PHI_ARG_DEF (phi, e->dest_idx, equiv);
397 185640 : break;
398 : }
399 : }
400 : }
401 : }
402 :
403 : /* If we had an equivalence associated with this edge, remove it. */
404 6344885 : if (e->aux)
405 : {
406 1335 : struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
407 1335 : remove_equivalence (equiv->rhs);
408 : }
409 : }
410 14620805 : }
411 :
412 : edge
413 14620805 : uncprop_dom_walker::before_dom_children (basic_block bb)
414 : {
415 14620805 : basic_block parent;
416 14620805 : bool recorded = false;
417 :
418 : /* If this block is dominated by a single incoming edge and that edge
419 : has an equivalency, then record the equivalency and push the
420 : VALUE onto EQUIV_STACK. Else push a NULL entry on EQUIV_STACK. */
421 14620805 : parent = get_immediate_dominator (CDI_DOMINATORS, bb);
422 14620805 : if (parent)
423 : {
424 13574434 : edge e = single_pred_edge_ignoring_loop_edges (bb, false);
425 :
426 13574434 : if (e && e->src == parent && e->aux)
427 : {
428 3957971 : struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
429 :
430 3957971 : record_equiv (equiv->rhs, equiv->lhs);
431 3957971 : m_equiv_stack.safe_push (equiv->rhs);
432 3957971 : recorded = true;
433 : }
434 : }
435 :
436 3957971 : if (!recorded)
437 10662834 : m_equiv_stack.safe_push (NULL_TREE);
438 :
439 14620805 : uncprop_into_successor_phis (bb);
440 14620805 : return NULL;
441 : }
442 :
443 : namespace {
444 :
445 : const pass_data pass_data_uncprop =
446 : {
447 : GIMPLE_PASS, /* type */
448 : "uncprop", /* name */
449 : OPTGROUP_NONE, /* optinfo_flags */
450 : TV_TREE_SSA_UNCPROP, /* tv_id */
451 : ( PROP_cfg | PROP_ssa ), /* properties_required */
452 : 0, /* properties_provided */
453 : 0, /* properties_destroyed */
454 : 0, /* todo_flags_start */
455 : 0, /* todo_flags_finish */
456 : };
457 :
458 : class pass_uncprop : public gimple_opt_pass
459 : {
460 : public:
461 577534 : pass_uncprop (gcc::context *ctxt)
462 1155068 : : gimple_opt_pass (pass_data_uncprop, ctxt)
463 : {}
464 :
465 : /* opt_pass methods: */
466 288767 : opt_pass * clone () final override { return new pass_uncprop (m_ctxt); }
467 1046732 : bool gate (function *) final override { return flag_tree_dom != 0; }
468 : unsigned int execute (function *) final override;
469 :
470 : }; // class pass_uncprop
471 :
472 : unsigned int
473 1046371 : pass_uncprop::execute (function *fun)
474 : {
475 1046371 : basic_block bb;
476 :
477 1046371 : associate_equivalences_with_edges ();
478 :
479 : /* Create our global data structures. */
480 1046371 : val_ssa_equiv = new val_ssa_equiv_t (1024);
481 :
482 : /* We're going to do a dominator walk, so ensure that we have
483 : dominance information. */
484 1046371 : calculate_dominance_info (CDI_DOMINATORS);
485 :
486 : /* Recursively walk the dominator tree undoing unprofitable
487 : constant/copy propagations. */
488 1046371 : uncprop_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr);
489 :
490 : /* we just need to empty elements out of the hash table, and cleanup the
491 : AUX field on the edges. */
492 2092742 : delete val_ssa_equiv;
493 1046371 : val_ssa_equiv = NULL;
494 14620805 : FOR_EACH_BB_FN (bb, fun)
495 : {
496 13574434 : edge e;
497 13574434 : edge_iterator ei;
498 :
499 31554171 : FOR_EACH_EDGE (e, ei, bb->succs)
500 : {
501 17979737 : if (e->aux)
502 : {
503 3960021 : free (e->aux);
504 3960021 : e->aux = NULL;
505 : }
506 : }
507 : }
508 1046371 : return 0;
509 : }
510 :
511 : } // anon namespace
512 :
513 : gimple_opt_pass *
514 288767 : make_pass_uncprop (gcc::context *ctxt)
515 : {
516 288767 : return new pass_uncprop (ctxt);
517 : }
|
