1/* Routines for discovering and unpropagating edge equivalences.
2 Copyright (C) 2005-2025 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify
7it under the terms of the GNU General Public License as published by
8the Free Software Foundation; either version 3, or (at your option)
9any later version.
10
11GCC is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14GNU General Public License for more details.
15
16You should have received a copy of the GNU General Public License
17along 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. */
40struct 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
53static void
54associate_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 (i: gsi))
68 continue;
69
70 stmt = gsi_stmt (i: 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 (g: 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 (gs: 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 (gs: stmt);
90 tree op1 = gimple_cond_rhs (gs: 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 (g: stmt) == GIMPLE_SWITCH)
171 {
172 gswitch *switch_stmt = as_a <gswitch *> (p: stmt);
173 tree cond = gimple_switch_index (gs: 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 (gs: 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 (gs: switch_stmt, index: i);
187 basic_block bb = label_to_block (cfun, 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 (ptr: 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
271typedef 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. */
276val_ssa_equiv_t *val_ssa_equiv;
277
278static void uncprop_into_successor_phis (basic_block);
279
280/* Remove the most recently recorded equivalency for VALUE. */
281
282static void
283remove_equivalence (tree value)
284{
285 val_ssa_equiv->get (k: value)->pop ();
286}
287
288/* Record EQUIVALENCE = VALUE into our hash table. */
289
290static void
291record_equiv (tree value, tree equivalence)
292{
293 val_ssa_equiv->get_or_insert (k: value).safe_push (obj: equivalence);
294}
295
296class uncprop_dom_walker : public dom_walker
297{
298public:
299 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
304private:
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
317void
318uncprop_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
319{
320 /* Pop the topmost value off the equiv stack. */
321 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 if (value != NULL)
326 remove_equivalence (value);
327}
328
329/* Unpropagate values from PHI nodes in successor blocks of BB. */
330
331static void
332uncprop_into_successor_phis (basic_block bb)
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 {
342 gimple_seq phis = phi_nodes (bb: e->dest);
343 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 if (gimple_seq_empty_p (s: phis))
348 continue;
349
350 /* Record any equivalency associated with E. */
351 if (e->aux)
352 {
353 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
354 record_equiv (value: equiv->rhs, equivalence: equiv->lhs);
355 }
356
357 /* Walk over the PHI nodes, unpropagating values. */
358 for (gsi = gsi_start (seq&: phis) ; !gsi_end_p (i: gsi); gsi_next (i: &gsi))
359 {
360 gimple *phi = gsi_stmt (i: gsi);
361 tree arg = PHI_ARG_DEF (phi, e->dest_idx);
362 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 if (!is_gimple_min_invariant (arg)
368 && gimple_can_coalesce_p (arg, res))
369 continue;
370
371 /* Lookup this argument's value in the hash table. */
372 vec<tree> *equivalences = val_ssa_equiv->get (k: arg);
373 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 for (int j = equivalences->length () - 1; j >= 0; j--)
381 {
382 tree equiv = (*equivalences)[j];
383
384 if (gimple_can_coalesce_p (equiv, res))
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 {
396 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
397 remove_equivalence (value: equiv->rhs);
398 }
399 }
400}
401
402edge
403uncprop_dom_walker::before_dom_children (basic_block bb)
404{
405 basic_block parent;
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 {
414 edge e = single_pred_edge_ignoring_loop_edges (bb, false);
415
416 if (e && e->src == parent && e->aux)
417 {
418 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
419
420 record_equiv (value: equiv->rhs, equivalence: equiv->lhs);
421 m_equiv_stack.safe_push (obj: equiv->rhs);
422 recorded = true;
423 }
424 }
425
426 if (!recorded)
427 m_equiv_stack.safe_push (NULL_TREE);
428
429 uncprop_into_successor_phis (bb);
430 return NULL;
431}
432
433namespace {
434
435const pass_data pass_data_uncprop =
436{
437 .type: GIMPLE_PASS, /* type */
438 .name: "uncprop", /* name */
439 .optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
440 .tv_id: TV_TREE_SSA_UNCPROP, /* tv_id */
441 .properties_required: ( PROP_cfg | PROP_ssa ), /* properties_required */
442 .properties_provided: 0, /* properties_provided */
443 .properties_destroyed: 0, /* properties_destroyed */
444 .todo_flags_start: 0, /* todo_flags_start */
445 .todo_flags_finish: 0, /* todo_flags_finish */
446};
447
448class pass_uncprop : public gimple_opt_pass
449{
450public:
451 pass_uncprop (gcc::context *ctxt)
452 : gimple_opt_pass (pass_data_uncprop, ctxt)
453 {}
454
455 /* opt_pass methods: */
456 opt_pass * clone () final override { return new pass_uncprop (m_ctxt); }
457 bool gate (function *) final override { return flag_tree_dom != 0; }
458 unsigned int execute (function *) final override;
459
460}; // class pass_uncprop
461
462unsigned int
463pass_uncprop::execute (function *fun)
464{
465 basic_block bb;
466
467 associate_equivalences_with_edges ();
468
469 /* Create our global data structures. */
470 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 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. */
482 delete val_ssa_equiv;
483 val_ssa_equiv = NULL;
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 (ptr: e->aux);
494 e->aux = NULL;
495 }
496 }
497 }
498 return 0;
499}
500
501} // anon namespace
502
503gimple_opt_pass *
504make_pass_uncprop (gcc::context *ctxt)
505{
506 return new pass_uncprop (ctxt);
507}
508

source code of gcc/tree-ssa-uncprop.cc