1/* Strongly-connected copy propagation pass for the GNU compiler.
2 Copyright (C) 2023-2024 Free Software Foundation, Inc.
3 Contributed by Filip Kastl <fkastl@suse.cz>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#define INCLUDE_ALGORITHM
22#include "config.h"
23#include "system.h"
24#include "coretypes.h"
25#include "backend.h"
26#include "tree.h"
27#include "gimple.h"
28#include "tree-pass.h"
29#include "ssa.h"
30#include "gimple-iterator.h"
31#include "vec.h"
32#include "hash-set.h"
33#include "ssa-iterators.h"
34#include "gimple-fold.h"
35#include "gimplify.h"
36#include "tree-cfg.h"
37#include "tree-eh.h"
38#include "builtins.h"
39#include "tree-ssa-dce.h"
40#include "fold-const.h"
41
42/* Strongly connected copy propagation pass.
43
44 This is a lightweight copy propagation pass that is also able to eliminate
45 redundant PHI statements. The pass considers the following types of copy
46 statements:
47
48 1 An assignment statement with a single argument.
49
50 _3 = _2;
51 _4 = 5;
52
53 2 A degenerate PHI statement. A degenerate PHI is a PHI that only refers to
54 itself or one other value.
55
56 _5 = PHI <_1>;
57 _6 = PHI <_6, _6, _1, _1>;
58 _7 = PHI <16, _7>;
59
60 3 A set of PHI statements that only refer to each other or to one other
61 value.
62
63 _8 = PHI <_9, _10>;
64 _9 = PHI <_8, _10>;
65 _10 = PHI <_8, _9, _1>;
66
67 All of these statements produce copies and can be eliminated from the
68 program. For a copy statement we identify the value it creates a copy of
69 and replace references to the statement with the value -- we propagate the
70 copy.
71
72 _3 = _2; // Replace all occurences of _3 by _2
73
74 _8 = PHI <_9, _10>;
75 _9 = PHI <_8, _10>;
76 _10 = PHI <_8, _9, _1>; // Replace all occurences of _8, _9 and _10 by _1
77
78 To find all three types of copy statements we use an algorithm based on
79 strongly-connected components (SCCs) in dataflow graph. The algorithm was
80 introduced in an article from 2013[1]. We describe the algorithm bellow.
81
82 To identify SCCs we implement the Robert Tarjan's SCC algorithm. For the
83 SCC computation we wrap potential copy statements in the 'vertex' struct.
84 To each of these statements we also assign a vertex number ('vxnum'). Since
85 the main algorithm has to be able to compute SCCs of subgraphs of the whole
86 dataflow graph we use GIMPLE stmt flags to prevent Tarjan's algorithm from
87 leaving the subgraph.
88
89 References:
90
91 [1] Simple and Efficient Construction of Static Single Assignmemnt Form,
92 Braun, Buchwald, Hack, Leissa, Mallon, Zwinkau, 2013, LNCS vol. 7791,
93 Section 3.2. */
94
95/* Bitmap tracking statements which were propagated to be removed at the end of
96 the pass. */
97
98namespace {
99static bitmap dead_stmts;
100
101/* State of vertex during SCC discovery.
102
103 unvisited Vertex hasn't yet been popped from worklist.
104 vopen DFS has visited vertex for the first time. Vertex has been put
105 on Tarjan stack.
106 closed DFS has backtracked through vertex. At this point, vertex
107 doesn't have any unvisited neighbors.
108 in_scc Vertex has been popped from Tarjan stack. */
109
110enum vstate
111{
112 unvisited,
113 vopen,
114 closed,
115 in_scc
116};
117
118/* Information about a vertex. Used by SCC discovery. */
119
120struct vertex
121{
122 bool active; /* scc_discovery::compute_sccs () only considers a subgraph of
123 the whole dataflow graph. It uses this flag so that it knows
124 which vertices are part of this subgraph. */
125 vstate state;
126 unsigned index;
127 unsigned lowlink;
128};
129
130/* SCC discovery.
131
132 Used to find SCCs in a dataflow graph. Implements Tarjan's SCC
133 algorithm. */
134
135class scc_discovery
136{
137public:
138 scc_discovery ();
139 ~scc_discovery ();
140 auto_vec<vec<gimple *>> compute_sccs (vec<gimple *> &stmts);
141
142private:
143 vertex* vertices; /* Indexed by SSA_NAME_VERSION. */
144 auto_vec<unsigned> worklist; /* DFS stack. */
145 auto_vec<unsigned> stack; /* Tarjan stack. */
146
147 void visit_neighbor (tree neigh_tree, unsigned parent_vxnum);
148};
149
150scc_discovery::scc_discovery ()
151{
152 /* Create vertex struct for each SSA name. */
153 vertices = XNEWVEC (struct vertex, num_ssa_names);
154 unsigned i = 0;
155 for (i = 0; i < num_ssa_names; i++)
156 vertices[i].active = false;
157}
158
159scc_discovery::~scc_discovery ()
160{
161 XDELETEVEC (vertices);
162}
163
164/* Part of 'scc_discovery::compute_sccs ()'. */
165
166void
167scc_discovery::visit_neighbor (tree neigh_tree, unsigned parent_version)
168{
169 if (TREE_CODE (neigh_tree) != SSA_NAME)
170 return; /* Skip any neighbor that isn't an SSA name. */
171 unsigned neigh_version = SSA_NAME_VERSION (neigh_tree);
172
173 /* Skip neighbors outside the subgraph that Tarjan currently works
174 with. */
175 if (!vertices[neigh_version].active)
176 return;
177
178 vstate neigh_state = vertices[neigh_version].state;
179 vstate parent_state = vertices[parent_version].state;
180 if (parent_state == vopen) /* We're currently opening parent. */
181 {
182 /* Put unvisited neighbors on worklist. Update lowlink of parent
183 vertex according to indices of neighbors present on stack. */
184 switch (neigh_state)
185 {
186 case unvisited:
187 worklist.safe_push (obj: neigh_version);
188 break;
189 case vopen:
190 case closed:
191 vertices[parent_version].lowlink
192 = std::min (a: vertices[parent_version].lowlink,
193 b: vertices[neigh_version].index);
194 break;
195 case in_scc:
196 /* Ignore these edges. */
197 break;
198 }
199 }
200 else if (parent_state == closed) /* We're currently closing parent. */
201 {
202 /* Update lowlink of parent vertex according to lowlinks of
203 children of parent (in terms of DFS tree). */
204 if (neigh_state == closed)
205 {
206 vertices[parent_version].lowlink
207 = std::min (a: vertices[parent_version].lowlink,
208 b: vertices[neigh_version].lowlink);
209 }
210 }
211}
212
213/* Compute SCCs in dataflow graph on given statements 'stmts'. Ignore
214 statements outside 'stmts'. Return the SCCs in a reverse topological
215 order.
216
217 stmt_may_generate_copy () must be true for all statements from 'stmts'! */
218
219auto_vec<vec<gimple *>>
220scc_discovery::compute_sccs (vec<gimple *> &stmts)
221{
222 auto_vec<vec<gimple *>> sccs;
223
224 for (gimple *stmt : stmts)
225 {
226 unsigned i;
227 switch (gimple_code (g: stmt))
228 {
229 case GIMPLE_ASSIGN:
230 i = SSA_NAME_VERSION (gimple_assign_lhs (stmt));
231 break;
232 case GIMPLE_PHI:
233 i = SSA_NAME_VERSION (gimple_phi_result (stmt));
234 break;
235 default:
236 gcc_unreachable ();
237 }
238
239 vertices[i].index = 0;
240 vertices[i].lowlink = 0;
241 vertices[i].state = unvisited;
242 vertices[i].active = true; /* Mark the subgraph we'll be working on so
243 that we don't leave it. */
244
245 worklist.safe_push (obj: i);
246 }
247
248 /* Worklist loop. */
249 unsigned curr_index = 0;
250 while (!worklist.is_empty ())
251 {
252 unsigned i = worklist.pop ();
253 gimple *stmt = SSA_NAME_DEF_STMT (ssa_name (i));
254 vstate state = vertices[i].state;
255
256 if (state == unvisited)
257 {
258 vertices[i].state = vopen;
259
260 /* Assign index to this vertex. */
261 vertices[i].index = curr_index;
262 vertices[i].lowlink = curr_index;
263 curr_index++;
264
265 /* Put vertex on stack and also on worklist to be closed later. */
266 stack.safe_push (obj: i);
267 worklist.safe_push (obj: i);
268 }
269 else if (state == vopen)
270 vertices[i].state = closed;
271
272 /* Visit neighbors of this vertex. */
273 tree op;
274 gphi *phi;
275 switch (gimple_code (g: stmt))
276 {
277 case GIMPLE_PHI:
278 phi = as_a <gphi *> (p: stmt);
279 unsigned j;
280 for (j = 0; j < gimple_phi_num_args (gs: phi); j++)
281 {
282 op = gimple_phi_arg_def (gs: phi, index: j);
283 visit_neighbor (neigh_tree: op, parent_version: i);
284 }
285 break;
286 case GIMPLE_ASSIGN:
287 op = gimple_assign_rhs1 (gs: stmt);
288 visit_neighbor (neigh_tree: op, parent_version: i);
289 break;
290 default:
291 gcc_unreachable ();
292 }
293
294 /* If we've just closed a root vertex of an scc, pop scc from stack. */
295 if (state == vopen && vertices[i].lowlink == vertices[i].index)
296 {
297 vec<gimple *> scc = vNULL;
298
299 unsigned j;
300 do
301 {
302 j = stack.pop ();
303 scc.safe_push (SSA_NAME_DEF_STMT (ssa_name (j)));
304 vertices[j].state = in_scc;
305 }
306 while (j != i);
307
308 sccs.safe_push (obj: scc);
309 }
310 }
311
312 if (!stack.is_empty ())
313 gcc_unreachable ();
314
315 /* Clear 'active' flags. */
316 for (gimple *stmt : stmts)
317 {
318 unsigned i;
319 switch (gimple_code (g: stmt))
320 {
321 case GIMPLE_ASSIGN:
322 i = SSA_NAME_VERSION (gimple_assign_lhs (stmt));
323 break;
324 case GIMPLE_PHI:
325 i = SSA_NAME_VERSION (gimple_phi_result (stmt));
326 break;
327 default:
328 gcc_unreachable ();
329 }
330
331 vertices[i].active = false;
332 }
333
334 return sccs;
335}
336
337} // anon namespace
338
339/* Could this statement potentially be a copy statement?
340
341 This pass only considers statements for which this function returns 'true'.
342 Those are basically PHI functions and assignment statements similar to
343
344 _2 = _1;
345 or
346 _2 = 5; */
347
348static bool
349stmt_may_generate_copy (gimple *stmt)
350{
351 /* A PHI may generate a copy. */
352 if (gimple_code (g: stmt) == GIMPLE_PHI)
353 {
354 gphi *phi = as_a <gphi *> (p: stmt);
355
356 /* No OCCURS_IN_ABNORMAL_PHI SSA names in lhs nor rhs. */
357 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (phi)))
358 return false;
359
360 unsigned i;
361 for (i = 0; i < gimple_phi_num_args (gs: phi); i++)
362 {
363 tree op = gimple_phi_arg_def (gs: phi, index: i);
364 if (TREE_CODE (op) == SSA_NAME
365 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
366 return false;
367 }
368
369 /* If PHI has more than one unique non-SSA arguments, it won't generate a
370 copy. */
371 tree const_op = NULL_TREE;
372 for (i = 0; i < gimple_phi_num_args (gs: phi); i++)
373 {
374 tree op = gimple_phi_arg_def (gs: phi, index: i);
375 if (TREE_CODE (op) != SSA_NAME)
376 {
377 if (const_op && !operand_equal_p (op, const_op))
378 return false;
379 const_op = op;
380 }
381 }
382
383 return true;
384 }
385
386 /* Or a statement of type _2 = _1; OR _2 = 5; may generate a copy. */
387
388 if (!gimple_assign_single_p (gs: stmt))
389 return false;
390
391 tree lhs = gimple_assign_lhs (gs: stmt);
392 tree rhs = gimple_assign_rhs1 (gs: stmt);
393
394 if (TREE_CODE (lhs) != SSA_NAME)
395 return false;
396
397 /* lhs shouldn't flow through any abnormal edges. */
398 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
399 return false;
400
401 if (is_gimple_min_invariant (rhs))
402 return true; /* A statement of type _2 = 5;. */
403
404 if (TREE_CODE (rhs) != SSA_NAME)
405 return false;
406
407 /* rhs shouldn't flow through any abnormal edges. */
408 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
409 return false;
410
411 /* It is possible that lhs has more alignment or value range information. By
412 propagating we would lose this information. So in the case that alignment
413 or value range information differs, we are conservative and do not
414 propagate.
415
416 FIXME: Propagate alignment and value range info the same way copy-prop
417 does. */
418 if (POINTER_TYPE_P (TREE_TYPE (lhs))
419 && POINTER_TYPE_P (TREE_TYPE (rhs))
420 && SSA_NAME_PTR_INFO (lhs) != SSA_NAME_PTR_INFO (rhs))
421 return false;
422 if (!POINTER_TYPE_P (TREE_TYPE (lhs))
423 && !POINTER_TYPE_P (TREE_TYPE (rhs))
424 && SSA_NAME_RANGE_INFO (lhs) != SSA_NAME_RANGE_INFO (rhs))
425 return false;
426
427 return true; /* A statement of type _2 = _1;. */
428}
429
430/* Return all statements in cfun that could generate copies. All statements
431 for which stmt_may_generate_copy returns 'true'. */
432
433static auto_vec<gimple *>
434get_all_stmt_may_generate_copy (void)
435{
436 auto_vec<gimple *> result;
437
438 basic_block bb;
439 FOR_EACH_BB_FN (bb, cfun)
440 {
441 gimple_stmt_iterator gsi;
442 for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
443 {
444 gimple *s = gsi_stmt (i: gsi);
445 if (stmt_may_generate_copy (stmt: s))
446 result.safe_push (obj: s);
447 }
448
449 gphi_iterator pi;
450 for (pi = gsi_start_phis (bb); !gsi_end_p (i: pi); gsi_next (i: &pi))
451 {
452 gimple *s = pi.phi ();
453 if (stmt_may_generate_copy (stmt: s))
454 result.safe_push (obj: s);
455 }
456 }
457
458 return result;
459}
460
461/* For each statement from given SCC, replace its usages by value
462 VAL. */
463
464static void
465replace_scc_by_value (vec<gimple *> scc, tree val)
466{
467 for (gimple *stmt : scc)
468 {
469 tree name = gimple_get_lhs (stmt);
470 replace_uses_by (name, val);
471 bitmap_set_bit (dead_stmts, SSA_NAME_VERSION (name));
472 }
473
474 if (dump_file)
475 fprintf (stream: dump_file, format: "Replacing SCC of size %d\n", scc.length ());
476}
477
478/* Part of 'sccopy_propagate ()'. */
479
480static void
481sccopy_visit_op (tree op, hash_set<tree> &outer_ops,
482 hash_set<gimple *> &scc_set, bool &is_inner,
483 tree &last_outer_op)
484{
485 bool op_in_scc = false;
486
487 if (TREE_CODE (op) == SSA_NAME)
488 {
489 gimple *op_stmt = SSA_NAME_DEF_STMT (op);
490 if (scc_set.contains (k: op_stmt))
491 op_in_scc = true;
492 }
493
494 if (!op_in_scc)
495 {
496 outer_ops.add (k: op);
497 last_outer_op = op;
498 is_inner = false;
499 }
500}
501
502/* Main function of this pass. Find and propagate all three types of copy
503 statements (see pass description above).
504
505 This is an implementation of an algorithm from the paper Simple and
506 Efficient Construction of Static Single Assignmemnt Form[1]. It is based
507 on strongly-connected components (SCCs) in dataflow graph. The original
508 algorithm only considers PHI statements. We extend it to also consider
509 assignment statements of type _2 = _1;.
510
511 The algorithm is based on this definition of a set of redundant PHIs[1]:
512
513 A non-empty set P of PHI functions is redundant iff the PHI functions just
514 reference each other or one other value
515
516 It uses this lemma[1]:
517
518 Let P be a redundant set of PHI functions. Then there is a
519 strongly-connected component S subset of P that is also redundant.
520
521 The algorithm works in this way:
522
523 1 Find SCCs
524 2 For each SCC S in topological order:
525 3 Construct set 'inner' of statements that only have other statements
526 from S on their right hand side
527 4 Construct set 'outer' of values that originate outside S and appear on
528 right hand side of some statement from S
529 5 If |outer| = 1, outer only contains a value v. Statements in S only
530 refer to each other or to v -- they are redundant. Propagate v.
531 Else, recurse on statements in inner.
532
533 The implementation is non-recursive.
534
535 References:
536
537 [1] Simple and Efficient Construction of Static Single Assignmemnt Form,
538 Braun, Buchwald, Hack, Leissa, Mallon, Zwinkau, 2013, LNCS vol. 7791,
539 Section 3.2. */
540
541static void
542sccopy_propagate ()
543{
544 auto_vec<gimple *> useful_stmts = get_all_stmt_may_generate_copy ();
545 scc_discovery discovery;
546
547 auto_vec<vec<gimple *>> worklist = discovery.compute_sccs (stmts&: useful_stmts);
548
549 while (!worklist.is_empty ())
550 {
551 vec<gimple *> scc = worklist.pop ();
552
553 auto_vec<gimple *> inner;
554 hash_set<tree> outer_ops;
555 tree last_outer_op = NULL_TREE;
556
557 /* Prepare hash set of PHIs in scc to query later. */
558 hash_set<gimple *> scc_set;
559 for (gimple *stmt : scc)
560 scc_set.add (k: stmt);
561
562 for (gimple *stmt : scc)
563 {
564 bool is_inner = true;
565
566 gphi *phi;
567 tree op;
568
569 switch (gimple_code (g: stmt))
570 {
571 case GIMPLE_PHI:
572 phi = as_a <gphi *> (p: stmt);
573 unsigned j;
574 for (j = 0; j < gimple_phi_num_args (gs: phi); j++)
575 {
576 op = gimple_phi_arg_def (gs: phi, index: j);
577 sccopy_visit_op (op, outer_ops, scc_set, is_inner,
578 last_outer_op);
579 }
580 break;
581 case GIMPLE_ASSIGN:
582 op = gimple_assign_rhs1 (gs: stmt);
583 sccopy_visit_op (op, outer_ops, scc_set, is_inner,
584 last_outer_op);
585 break;
586 default:
587 gcc_unreachable ();
588 }
589
590 if (is_inner)
591 inner.safe_push (obj: stmt);
592 }
593
594 if (outer_ops.elements () == 1)
595 {
596 /* The only operand in outer_ops. */
597 tree outer_op = last_outer_op;
598 replace_scc_by_value (scc, val: outer_op);
599 }
600 else if (outer_ops.elements () > 1)
601 {
602 /* Add inner sccs to worklist. */
603 auto_vec<vec<gimple *>> inner_sccs
604 = discovery.compute_sccs (stmts&: inner);
605 for (vec<gimple *> inner_scc : inner_sccs)
606 worklist.safe_push (obj: inner_scc);
607 }
608 else
609 gcc_unreachable ();
610
611 scc.release ();
612 }
613}
614
615/* Called when pass execution starts. */
616
617static void
618init_sccopy (void)
619{
620 /* For propagated statements. */
621 dead_stmts = BITMAP_ALLOC (NULL);
622}
623
624/* Called before pass execution ends. */
625
626static void
627finalize_sccopy (void)
628{
629 /* Remove all propagated statements. */
630 simple_dce_from_worklist (dead_stmts);
631 BITMAP_FREE (dead_stmts);
632
633 /* Propagating a constant may create dead eh edges. */
634 basic_block bb;
635 FOR_EACH_BB_FN (bb, cfun)
636 gimple_purge_dead_eh_edges (bb);
637}
638
639namespace {
640
641const pass_data pass_data_sccopy =
642{
643 .type: GIMPLE_PASS, /* type */
644 .name: "sccopy", /* name */
645 .optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
646 .tv_id: TV_NONE, /* tv_id */
647 .properties_required: ( PROP_cfg | PROP_ssa ), /* properties_required */
648 .properties_provided: 0, /* properties_provided */
649 .properties_destroyed: 0, /* properties_destroyed */
650 .todo_flags_start: 0, /* todo_flags_start */
651 TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */
652};
653
654class pass_sccopy : public gimple_opt_pass
655{
656public:
657 pass_sccopy (gcc::context *ctxt)
658 : gimple_opt_pass (pass_data_sccopy, ctxt)
659 {}
660
661 /* opt_pass methods: */
662 virtual bool gate (function *) { return true; }
663 virtual unsigned int execute (function *);
664 opt_pass * clone () final override { return new pass_sccopy (m_ctxt); }
665}; // class pass_sccopy
666
667unsigned
668pass_sccopy::execute (function *)
669{
670 init_sccopy ();
671 sccopy_propagate ();
672 finalize_sccopy ();
673 return 0;
674}
675
676} // anon namespace
677
678gimple_opt_pass *
679make_pass_sccopy (gcc::context *ctxt)
680{
681 return new pass_sccopy (ctxt);
682}
683

source code of gcc/gimple-ssa-sccopy.cc