Branch data Line data Source code
1 : : /* Routines for discovering and unpropagating edge equivalences.
2 : : Copyright (C) 2005-2024 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 : 987722 : associate_equivalences_with_edges (void)
55 : : {
56 : 987722 : 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 : 13573014 : FOR_EACH_BB_FN (bb, cfun)
61 : : {
62 : 12585292 : gimple_stmt_iterator gsi = gsi_last_bb (bb);
63 : 12585292 : 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 : 12585292 : if (gsi_end_p (gsi))
68 : 12585292 : continue;
69 : :
70 : 8873453 : stmt = gsi_stmt (gsi);
71 : :
72 : 8873453 : if (!stmt)
73 : : continue;
74 : :
75 : : /* A COND_EXPR may create an equivalency in a variety of different
76 : : ways. */
77 : 8873453 : if (gimple_code (stmt) == GIMPLE_COND)
78 : : {
79 : 3881228 : edge true_edge;
80 : 3881228 : edge false_edge;
81 : 3881228 : struct edge_equivalency *equivalency;
82 : 3881228 : enum tree_code code = gimple_cond_code (stmt);
83 : :
84 : 3881228 : extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
85 : :
86 : : /* Equality tests may create one or two equivalences. */
87 : 3881228 : if (code == EQ_EXPR || code == NE_EXPR)
88 : : {
89 : 3177580 : tree op0 = gimple_cond_lhs (stmt);
90 : 3177580 : 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 : 3177580 : if (TREE_CODE (op0) == SSA_NAME
96 : 3106469 : && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)
97 : 3106352 : && ssa_name_has_boolean_range (op0)
98 : 417497 : && is_gimple_min_invariant (op1)
99 : 3581029 : && (integer_zerop (op1) || integer_onep (op1)))
100 : : {
101 : 403449 : tree true_val = constant_boolean_node (true, TREE_TYPE (op0));
102 : 403449 : tree false_val = constant_boolean_node (false,
103 : 403449 : TREE_TYPE (op0));
104 : 403449 : if (code == EQ_EXPR)
105 : : {
106 : 8403 : equivalency = XNEW (struct edge_equivalency);
107 : 8403 : equivalency->lhs = op0;
108 : 8403 : equivalency->rhs = (integer_zerop (op1)
109 : 8403 : ? false_val
110 : : : true_val);
111 : 8403 : true_edge->aux = equivalency;
112 : :
113 : 8403 : equivalency = XNEW (struct edge_equivalency);
114 : 8403 : equivalency->lhs = op0;
115 : 8403 : equivalency->rhs = (integer_zerop (op1)
116 : 8403 : ? true_val
117 : : : false_val);
118 : 8403 : false_edge->aux = equivalency;
119 : : }
120 : : else
121 : : {
122 : 395046 : equivalency = XNEW (struct edge_equivalency);
123 : 395046 : equivalency->lhs = op0;
124 : 395046 : equivalency->rhs = (integer_zerop (op1)
125 : 395046 : ? true_val
126 : : : false_val);
127 : 395046 : true_edge->aux = equivalency;
128 : :
129 : 395046 : equivalency = XNEW (struct edge_equivalency);
130 : 395046 : equivalency->lhs = op0;
131 : 395046 : equivalency->rhs = (integer_zerop (op1)
132 : 395046 : ? false_val
133 : : : true_val);
134 : 395046 : false_edge->aux = equivalency;
135 : : }
136 : : }
137 : :
138 : 2774131 : else if (TREE_CODE (op0) == SSA_NAME
139 : 2703020 : && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)
140 : 5477034 : && (is_gimple_min_invariant (op1)
141 : 586443 : || (TREE_CODE (op1) == SSA_NAME
142 : 586443 : && !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 : 2702902 : if (HONOR_SIGNED_ZEROS (op0)
149 : 2702902 : && (TREE_CODE (op1) != REAL_CST
150 : 85038 : || real_equal (&dconst0, &TREE_REAL_CST (op1))))
151 : 48953 : continue;
152 : :
153 : 2653949 : equivalency = XNEW (struct edge_equivalency);
154 : 2653949 : equivalency->lhs = op0;
155 : 2653949 : equivalency->rhs = op1;
156 : 2653949 : if (code == EQ_EXPR)
157 : 1205660 : true_edge->aux = equivalency;
158 : : else
159 : 1448289 : 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 : 4992225 : else if (gimple_code (stmt) == GIMPLE_SWITCH)
171 : : {
172 : 6246 : gswitch *switch_stmt = as_a <gswitch *> (stmt);
173 : 6246 : tree cond = gimple_switch_index (switch_stmt);
174 : :
175 : 6246 : if (TREE_CODE (cond) == SSA_NAME
176 : 6246 : && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond))
177 : : {
178 : 6246 : int i, n_labels = gimple_switch_num_labels (switch_stmt);
179 : 6246 : 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 : 85097 : for (i = 0; i < n_labels; i++)
185 : : {
186 : 78851 : tree label = gimple_switch_label (switch_stmt, i);
187 : 78851 : basic_block bb = label_to_block (cfun, CASE_LABEL (label));
188 : :
189 : 78851 : if (CASE_HIGH (label)
190 : 75347 : || !CASE_LOW (label)
191 : 147952 : || info[bb->index])
192 : 15913 : info[bb->index] = error_mark_node;
193 : : else
194 : 62938 : 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 : 1035794 : for (i = 0; i < n_basic_blocks_for_fn (cfun); i++)
200 : : {
201 : 1029548 : tree node = info[i];
202 : :
203 : 1029548 : if (node != NULL
204 : 71901 : && node != error_mark_node)
205 : : {
206 : 58568 : tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node));
207 : 58568 : struct edge_equivalency *equivalency;
208 : :
209 : : /* Record an equivalency on the edge from BB to basic
210 : : block I. */
211 : 58568 : equivalency = XNEW (struct edge_equivalency);
212 : 58568 : equivalency->rhs = x;
213 : 58568 : equivalency->lhs = cond;
214 : 58568 : find_edge (bb, BASIC_BLOCK_FOR_FN (cfun, i))->aux =
215 : : equivalency;
216 : : }
217 : : }
218 : 6246 : free (info);
219 : : }
220 : : }
221 : :
222 : : }
223 : 987722 : }
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 : 3518816 : remove_equivalence (tree value)
284 : : {
285 : 3518816 : val_ssa_equiv->get (value)->pop ();
286 : 3518816 : }
287 : :
288 : : /* Record EQUIVALENCE = VALUE into our hash table. */
289 : :
290 : : static void
291 : 3518816 : record_equiv (tree value, tree equivalence)
292 : : {
293 : 3518816 : val_ssa_equiv->get_or_insert (value).safe_push (equivalence);
294 : 3518816 : }
295 : :
296 : : class uncprop_dom_walker : public dom_walker
297 : : {
298 : : public:
299 : 987722 : 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 : 13573014 : uncprop_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
319 : : {
320 : : /* Pop the topmost value off the equiv stack. */
321 : 13573014 : 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 : 13573014 : if (value != NULL)
326 : 3517648 : remove_equivalence (value);
327 : 13573014 : }
328 : :
329 : : /* Unpropagate values from PHI nodes in successor blocks of BB. */
330 : :
331 : : static void
332 : 13573014 : uncprop_into_successor_phis (basic_block bb)
333 : : {
334 : 13573014 : edge e;
335 : 13573014 : 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 : 31187540 : FOR_EACH_EDGE (e, ei, bb->succs)
341 : : {
342 : 17614526 : gimple_seq phis = phi_nodes (e->dest);
343 : 17614526 : 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 : 17614526 : if (gimple_seq_empty_p (phis))
348 : 11737852 : continue;
349 : :
350 : : /* Record any equivalency associated with E. */
351 : 5876674 : if (e->aux)
352 : : {
353 : 1168 : struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
354 : 1168 : record_equiv (equiv->rhs, equiv->lhs);
355 : : }
356 : :
357 : : /* Walk over the PHI nodes, unpropagating values. */
358 : 16037796 : for (gsi = gsi_start (phis) ; !gsi_end_p (gsi); gsi_next (&gsi))
359 : : {
360 : 10161122 : gimple *phi = gsi_stmt (gsi);
361 : 10161122 : tree arg = PHI_ARG_DEF (phi, e->dest_idx);
362 : 10161122 : 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 : 10161122 : if (!is_gimple_min_invariant (arg)
368 : 10161122 : && gimple_can_coalesce_p (arg, res))
369 : 8861988 : continue;
370 : :
371 : : /* Lookup this argument's value in the hash table. */
372 : 1299134 : vec<tree> *equivalences = val_ssa_equiv->get (arg);
373 : 1299134 : 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 : 1630222 : for (int j = equivalences->length () - 1; j >= 0; j--)
381 : : {
382 : 563082 : tree equiv = (*equivalences)[j];
383 : :
384 : 563082 : if (gimple_can_coalesce_p (equiv, res))
385 : : {
386 : 141532 : SET_PHI_ARG_DEF (phi, e->dest_idx, equiv);
387 : 141532 : break;
388 : : }
389 : : }
390 : : }
391 : : }
392 : :
393 : : /* If we had an equivalence associated with this edge, remove it. */
394 : 5876674 : if (e->aux)
395 : : {
396 : 1168 : struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
397 : 1168 : remove_equivalence (equiv->rhs);
398 : : }
399 : : }
400 : 13573014 : }
401 : :
402 : : edge
403 : 13573014 : uncprop_dom_walker::before_dom_children (basic_block bb)
404 : : {
405 : 13573014 : basic_block parent;
406 : 13573014 : 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 : 13573014 : parent = get_immediate_dominator (CDI_DOMINATORS, bb);
412 : 13573014 : if (parent)
413 : : {
414 : 12585292 : edge e = single_pred_edge_ignoring_loop_edges (bb, false);
415 : :
416 : 12585292 : if (e && e->src == parent && e->aux)
417 : : {
418 : 3517648 : struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
419 : :
420 : 3517648 : record_equiv (equiv->rhs, equiv->lhs);
421 : 3517648 : m_equiv_stack.safe_push (equiv->rhs);
422 : 3517648 : recorded = true;
423 : : }
424 : : }
425 : :
426 : 3517648 : if (!recorded)
427 : 10055366 : m_equiv_stack.safe_push (NULL_TREE);
428 : :
429 : 13573014 : uncprop_into_successor_phis (bb);
430 : 13573014 : 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 : 563828 : pass_uncprop (gcc::context *ctxt)
452 : 1127656 : : gimple_opt_pass (pass_data_uncprop, ctxt)
453 : : {}
454 : :
455 : : /* opt_pass methods: */
456 : 281914 : opt_pass * clone () final override { return new pass_uncprop (m_ctxt); }
457 : 988057 : 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 : 987722 : pass_uncprop::execute (function *fun)
464 : : {
465 : 987722 : basic_block bb;
466 : :
467 : 987722 : associate_equivalences_with_edges ();
468 : :
469 : : /* Create our global data structures. */
470 : 987722 : 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 : 987722 : calculate_dominance_info (CDI_DOMINATORS);
475 : :
476 : : /* Recursively walk the dominator tree undoing unprofitable
477 : : constant/copy propagations. */
478 : 987722 : 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 : 1975444 : delete val_ssa_equiv;
483 : 987722 : val_ssa_equiv = NULL;
484 : 13573014 : FOR_EACH_BB_FN (bb, fun)
485 : : {
486 : 12585292 : edge e;
487 : 12585292 : edge_iterator ei;
488 : :
489 : 29212096 : FOR_EACH_EDGE (e, ei, bb->succs)
490 : : {
491 : 16626804 : if (e->aux)
492 : : {
493 : 3519415 : free (e->aux);
494 : 3519415 : e->aux = NULL;
495 : : }
496 : : }
497 : : }
498 : 987722 : return 0;
499 : : }
500 : :
501 : : } // anon namespace
502 : :
503 : : gimple_opt_pass *
504 : 281914 : make_pass_uncprop (gcc::context *ctxt)
505 : : {
506 : 281914 : return new pass_uncprop (ctxt);
507 : : }
|
