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 1043784 : associate_equivalences_with_edges (void)
55 : {
56 1043784 : 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 14743654 : FOR_EACH_BB_FN (bb, cfun)
61 : {
62 13699870 : gimple_stmt_iterator gsi = gsi_last_bb (bb);
63 13699870 : 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 13699870 : if (gsi_end_p (gsi))
68 13699870 : continue;
69 :
70 9618413 : stmt = gsi_stmt (gsi);
71 :
72 9618413 : if (!stmt)
73 : continue;
74 :
75 : /* A COND_EXPR may create an equivalency in a variety of different
76 : ways. */
77 9618413 : if (gimple_code (stmt) == GIMPLE_COND)
78 : {
79 4386238 : edge true_edge;
80 4386238 : edge false_edge;
81 4386238 : struct edge_equivalency *equivalency;
82 4386238 : enum tree_code code = gimple_cond_code (stmt);
83 :
84 4386238 : extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
85 :
86 : /* Equality tests may create one or two equivalences. */
87 4386238 : if (code == EQ_EXPR || code == NE_EXPR)
88 : {
89 3552207 : tree op0 = gimple_cond_lhs (stmt);
90 3552207 : 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 3552207 : if (TREE_CODE (op0) == SSA_NAME
96 3551556 : && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)
97 3551432 : && ssa_name_has_boolean_range (op0)
98 456715 : && is_gimple_min_invariant (op1)
99 3993713 : && (integer_zerop (op1) || integer_onep (op1)))
100 : {
101 441506 : tree true_val = constant_boolean_node (true, TREE_TYPE (op0));
102 441506 : tree false_val = constant_boolean_node (false,
103 441506 : TREE_TYPE (op0));
104 441506 : if (code == EQ_EXPR)
105 : {
106 11476 : equivalency = XNEW (struct edge_equivalency);
107 11476 : equivalency->lhs = op0;
108 11476 : equivalency->rhs = (integer_zerop (op1)
109 11476 : ? false_val
110 : : true_val);
111 11476 : true_edge->aux = equivalency;
112 :
113 11476 : equivalency = XNEW (struct edge_equivalency);
114 11476 : equivalency->lhs = op0;
115 11476 : equivalency->rhs = (integer_zerop (op1)
116 11476 : ? true_val
117 : : false_val);
118 11476 : false_edge->aux = equivalency;
119 : }
120 : else
121 : {
122 430030 : equivalency = XNEW (struct edge_equivalency);
123 430030 : equivalency->lhs = op0;
124 430030 : equivalency->rhs = (integer_zerop (op1)
125 430030 : ? true_val
126 : : false_val);
127 430030 : true_edge->aux = equivalency;
128 :
129 430030 : equivalency = XNEW (struct edge_equivalency);
130 430030 : equivalency->lhs = op0;
131 430030 : equivalency->rhs = (integer_zerop (op1)
132 430030 : ? false_val
133 : : true_val);
134 430030 : false_edge->aux = equivalency;
135 : }
136 : }
137 :
138 3110701 : else if (TREE_CODE (op0) == SSA_NAME
139 3110050 : && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)
140 6220627 : && (is_gimple_min_invariant (op1)
141 727425 : || (TREE_CODE (op1) == SSA_NAME
142 727425 : && !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 3109925 : if (HONOR_SIGNED_ZEROS (op0)
149 3109925 : && (TREE_CODE (op1) != REAL_CST
150 86456 : || real_equal (&dconst0, &TREE_REAL_CST (op1))))
151 51661 : continue;
152 :
153 3058264 : equivalency = XNEW (struct edge_equivalency);
154 3058264 : equivalency->lhs = op0;
155 3058264 : equivalency->rhs = op1;
156 3058264 : if (code == EQ_EXPR)
157 1433425 : true_edge->aux = equivalency;
158 : else
159 1624839 : 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 5232175 : else if (gimple_code (stmt) == GIMPLE_SWITCH)
171 : {
172 8023 : gswitch *switch_stmt = as_a <gswitch *> (stmt);
173 8023 : tree cond = gimple_switch_index (switch_stmt);
174 :
175 8023 : if (TREE_CODE (cond) == SSA_NAME
176 8023 : && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond))
177 : {
178 8023 : int i, n_labels = gimple_switch_num_labels (switch_stmt);
179 8023 : 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 94963 : for (i = 0; i < n_labels; i++)
185 : {
186 86940 : tree label = gimple_switch_label (switch_stmt, i);
187 86940 : basic_block bb = label_to_block (cfun, CASE_LABEL (label));
188 :
189 86940 : if (CASE_HIGH (label)
190 81388 : || !CASE_LOW (label)
191 160305 : || info[bb->index])
192 19780 : info[bb->index] = error_mark_node;
193 : else
194 67160 : 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 1275608 : for (i = 0; i < n_basic_blocks_for_fn (cfun); i++)
200 : {
201 1267585 : tree node = info[i];
202 :
203 1267585 : if (node != NULL
204 79786 : && node != error_mark_node)
205 : {
206 61957 : tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node));
207 61957 : struct edge_equivalency *equivalency;
208 :
209 : /* Record an equivalency on the edge from BB to basic
210 : block I. */
211 61957 : equivalency = XNEW (struct edge_equivalency);
212 61957 : equivalency->rhs = x;
213 61957 : equivalency->lhs = cond;
214 61957 : find_edge (bb, BASIC_BLOCK_FOR_FN (cfun, i))->aux =
215 : equivalency;
216 : }
217 : }
218 8023 : free (info);
219 : }
220 : }
221 :
222 : }
223 1043784 : }
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 : typedef hash_map<tree_operand_hash, auto_vec<tree> > val_ssa_equiv_t;
272 :
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. */
276 : val_ssa_equiv_t *val_ssa_equiv;
277 :
278 : static void uncprop_into_successor_phis (basic_block);
279 :
280 : /* Remove the most recently recorded equivalency for VALUE. */
281 :
282 : static void
283 4002508 : remove_equivalence (tree value)
284 : {
285 4002508 : val_ssa_equiv->get (value)->pop ();
286 4002508 : }
287 :
288 : /* Record EQUIVALENCE = VALUE into our hash table. */
289 :
290 : static void
291 4002508 : record_equiv (tree value, tree equivalence)
292 : {
293 4002508 : val_ssa_equiv->get_or_insert (value).safe_push (equivalence);
294 4002508 : }
295 :
296 : class uncprop_dom_walker : public dom_walker
297 : {
298 : public:
299 1043784 : uncprop_dom_walker (cdi_direction direction) : dom_walker (direction) {}
300 :
301 : edge before_dom_children (basic_block) final override;
302 : void after_dom_children (basic_block) final override;
303 :
304 : private:
305 :
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. */
310 : auto_vec<tree, 2> m_equiv_stack;
311 : };
312 :
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 :
317 : void
318 14743654 : uncprop_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
319 : {
320 : /* Pop the topmost value off the equiv stack. */
321 14743654 : tree value = m_equiv_stack.pop ();
322 :
323 : /* If that value was non-null, then pop the topmost equivalency off
324 : its equivalency stack. */
325 14743654 : if (value != NULL)
326 4001126 : remove_equivalence (value);
327 14743654 : }
328 :
329 : /* Unpropagate values from PHI nodes in successor blocks of BB. */
330 :
331 : static void
332 14743654 : uncprop_into_successor_phis (basic_block bb)
333 : {
334 14743654 : edge e;
335 14743654 : 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 33955672 : FOR_EACH_EDGE (e, ei, bb->succs)
341 : {
342 19212018 : gimple_seq phis = phi_nodes (e->dest);
343 19212018 : gimple_stmt_iterator gsi;
344 :
345 : /* If there are no PHI nodes in this destination, then there is
346 : no sense in recording any equivalences. */
347 19212018 : if (gimple_seq_empty_p (phis))
348 12784244 : continue;
349 :
350 : /* Record any equivalency associated with E. */
351 6427774 : if (e->aux)
352 : {
353 1382 : struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
354 1382 : record_equiv (equiv->rhs, equiv->lhs);
355 : }
356 :
357 : /* Walk over the PHI nodes, unpropagating values. */
358 18323384 : for (gsi = gsi_start (phis) ; !gsi_end_p (gsi); gsi_next (&gsi))
359 : {
360 11895610 : gimple *phi = gsi_stmt (gsi);
361 11895610 : tree arg = PHI_ARG_DEF (phi, e->dest_idx);
362 11895610 : tree res = PHI_RESULT (phi);
363 :
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. */
367 11895610 : if (!is_gimple_min_invariant (arg)
368 11895610 : && gimple_can_coalesce_p (arg, res))
369 10284500 : continue;
370 :
371 : /* Lookup this argument's value in the hash table. */
372 1611110 : vec<tree> *equivalences = val_ssa_equiv->get (arg);
373 1611110 : if (equivalences)
374 : {
375 : /* Walk every equivalence with the same value. If we find
376 : one that can potentially coalesce with the PHI rsult,
377 : then replace the value in the argument with its equivalent
378 : SSA_NAME. Use the most recent equivalence as hopefully
379 : that results in shortest lifetimes. */
380 2202083 : for (int j = equivalences->length () - 1; j >= 0; j--)
381 : {
382 818156 : tree equiv = (*equivalences)[j];
383 :
384 818156 : if (gimple_can_coalesce_p (equiv, res))
385 : {
386 188225 : SET_PHI_ARG_DEF (phi, e->dest_idx, equiv);
387 188225 : break;
388 : }
389 : }
390 : }
391 : }
392 :
393 : /* If we had an equivalence associated with this edge, remove it. */
394 6427774 : if (e->aux)
395 : {
396 1382 : struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
397 1382 : remove_equivalence (equiv->rhs);
398 : }
399 : }
400 14743654 : }
401 :
402 : edge
403 14743654 : uncprop_dom_walker::before_dom_children (basic_block bb)
404 : {
405 14743654 : basic_block parent;
406 14743654 : 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 14743654 : parent = get_immediate_dominator (CDI_DOMINATORS, bb);
412 14743654 : if (parent)
413 : {
414 13699870 : edge e = single_pred_edge_ignoring_loop_edges (bb, false);
415 :
416 13699870 : if (e && e->src == parent && e->aux)
417 : {
418 4001126 : struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
419 :
420 4001126 : record_equiv (equiv->rhs, equiv->lhs);
421 4001126 : m_equiv_stack.safe_push (equiv->rhs);
422 4001126 : recorded = true;
423 : }
424 : }
425 :
426 4001126 : if (!recorded)
427 10742528 : m_equiv_stack.safe_push (NULL_TREE);
428 :
429 14743654 : uncprop_into_successor_phis (bb);
430 14743654 : return NULL;
431 : }
432 :
433 : namespace {
434 :
435 : const pass_data pass_data_uncprop =
436 : {
437 : GIMPLE_PASS, /* type */
438 : "uncprop", /* name */
439 : OPTGROUP_NONE, /* optinfo_flags */
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 */
445 : 0, /* todo_flags_finish */
446 : };
447 :
448 : class pass_uncprop : public gimple_opt_pass
449 : {
450 : public:
451 571444 : pass_uncprop (gcc::context *ctxt)
452 1142888 : : gimple_opt_pass (pass_data_uncprop, ctxt)
453 : {}
454 :
455 : /* opt_pass methods: */
456 285722 : opt_pass * clone () final override { return new pass_uncprop (m_ctxt); }
457 1044139 : bool gate (function *) final override { return flag_tree_dom != 0; }
458 : unsigned int execute (function *) final override;
459 :
460 : }; // class pass_uncprop
461 :
462 : unsigned int
463 1043784 : pass_uncprop::execute (function *fun)
464 : {
465 1043784 : basic_block bb;
466 :
467 1043784 : associate_equivalences_with_edges ();
468 :
469 : /* Create our global data structures. */
470 1043784 : val_ssa_equiv = new val_ssa_equiv_t (1024);
471 :
472 : /* We're going to do a dominator walk, so ensure that we have
473 : dominance information. */
474 1043784 : calculate_dominance_info (CDI_DOMINATORS);
475 :
476 : /* Recursively walk the dominator tree undoing unprofitable
477 : constant/copy propagations. */
478 1043784 : 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. */
482 2087568 : delete val_ssa_equiv;
483 1043784 : val_ssa_equiv = NULL;
484 14743654 : FOR_EACH_BB_FN (bb, fun)
485 : {
486 13699870 : edge e;
487 13699870 : edge_iterator ei;
488 :
489 31868104 : FOR_EACH_EDGE (e, ei, bb->succs)
490 : {
491 18168234 : if (e->aux)
492 : {
493 4003233 : free (e->aux);
494 4003233 : e->aux = NULL;
495 : }
496 : }
497 : }
498 1043784 : return 0;
499 : }
500 :
501 : } // anon namespace
502 :
503 : gimple_opt_pass *
504 285722 : make_pass_uncprop (gcc::context *ctxt)
505 : {
506 285722 : return new pass_uncprop (ctxt);
507 : }
|
