1/* Convert a program in SSA form into Normal form.
2 Copyright (C) 2004-2023 Free Software Foundation, Inc.
3 Contributed by Andrew Macleod <amacleod@redhat.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for 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#include "config.h"
22#include "system.h"
23#include "coretypes.h"
24#include "backend.h"
25#include "rtl.h"
26#include "tree.h"
27#include "gimple.h"
28#include "cfghooks.h"
29#include "ssa.h"
30#include "tree-ssa.h"
31#include "memmodel.h"
32#include "emit-rtl.h"
33#include "gimple-pretty-print.h"
34#include "diagnostic-core.h"
35#include "tree-dfa.h"
36#include "stor-layout.h"
37#include "cfgrtl.h"
38#include "cfganal.h"
39#include "tree-eh.h"
40#include "gimple-iterator.h"
41#include "tree-cfg.h"
42#include "dumpfile.h"
43#include "tree-ssa-live.h"
44#include "tree-ssa-ter.h"
45#include "tree-ssa-coalesce.h"
46#include "tree-outof-ssa.h"
47#include "dojump.h"
48
49/* FIXME: A lot of code here deals with expanding to RTL. All that code
50 should be in cfgexpand.cc. */
51#include "explow.h"
52#include "expr.h"
53
54/* Return TRUE if expression STMT is suitable for replacement. */
55
56bool
57ssa_is_replaceable_p (gimple *stmt)
58{
59 use_operand_p use_p;
60 tree def;
61 gimple *use_stmt;
62
63 /* Only consider modify stmts. */
64 if (!is_gimple_assign (gs: stmt))
65 return false;
66
67 /* If the statement may throw an exception, it cannot be replaced. */
68 if (stmt_could_throw_p (cfun, stmt))
69 return false;
70
71 /* Punt if there is more than 1 def. */
72 def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
73 if (!def)
74 return false;
75
76 /* Only consider definitions which have a single use. */
77 if (!single_imm_use (var: def, use_p: &use_p, stmt: &use_stmt))
78 return false;
79
80 /* Used in this block, but at the TOP of the block, not the end. */
81 if (gimple_code (g: use_stmt) == GIMPLE_PHI)
82 return false;
83
84 /* There must be no VDEFs. */
85 if (gimple_vdef (g: stmt))
86 return false;
87
88 /* Float expressions must go through memory if float-store is on. */
89 if (flag_float_store
90 && FLOAT_TYPE_P (TREE_TYPE (def)))
91 return false;
92
93 /* An assignment with a register variable on the RHS is not
94 replaceable. */
95 if (gimple_assign_rhs_code (gs: stmt) == VAR_DECL
96 && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt)))
97 return false;
98
99 /* No function calls can be replaced. */
100 if (is_gimple_call (gs: stmt))
101 return false;
102
103 /* Leave any stmt with volatile operands alone as well. */
104 if (gimple_has_volatile_ops (stmt))
105 return false;
106
107 return true;
108}
109
110
111/* Used to hold all the components required to do SSA PHI elimination.
112 The node and pred/succ list is a simple linear list of nodes and
113 edges represented as pairs of nodes.
114
115 The predecessor and successor list: Nodes are entered in pairs, where
116 [0] ->PRED, [1]->SUCC. All the even indexes in the array represent
117 predecessors, all the odd elements are successors.
118
119 Rationale:
120 When implemented as bitmaps, very large programs SSA->Normal times were
121 being dominated by clearing the interference graph.
122
123 Typically this list of edges is extremely small since it only includes
124 PHI results and uses from a single edge which have not coalesced with
125 each other. This means that no virtual PHI nodes are included, and
126 empirical evidence suggests that the number of edges rarely exceed
127 3, and in a bootstrap of GCC, the maximum size encountered was 7.
128 This also limits the number of possible nodes that are involved to
129 rarely more than 6, and in the bootstrap of gcc, the maximum number
130 of nodes encountered was 12. */
131
132class elim_graph
133{
134public:
135 elim_graph (var_map map);
136
137 /* Size of the elimination vectors. */
138 int size;
139
140 /* List of nodes in the elimination graph. */
141 auto_vec<int> nodes;
142
143 /* The predecessor and successor edge list. */
144 auto_vec<int> edge_list;
145
146 /* Source locus on each edge */
147 auto_vec<location_t> edge_locus;
148
149 /* Visited vector. */
150 auto_sbitmap visited;
151
152 /* Stack for visited nodes. */
153 auto_vec<int> stack;
154
155 /* The variable partition map. */
156 var_map map;
157
158 /* Edge being eliminated by this graph. */
159 edge e;
160
161 /* List of constant copies to emit. These are pushed on in pairs. */
162 auto_vec<int> const_dests;
163 auto_vec<tree> const_copies;
164
165 /* Source locations for any constant copies. */
166 auto_vec<location_t> copy_locus;
167};
168
169
170/* For an edge E find out a good source location to associate with
171 instructions inserted on edge E. If E has an implicit goto set,
172 use its location. Otherwise search instructions in predecessors
173 of E for a location, and use that one. That makes sense because
174 we insert on edges for PHI nodes, and effects of PHIs happen on
175 the end of the predecessor conceptually. An exception is made
176 for EH edges because we don't want to drag the source location
177 of unrelated statements at the beginning of handlers; they would
178 be further reused for various EH constructs, which would damage
179 the coverage information. */
180
181static void
182set_location_for_edge (edge e)
183{
184 if (e->goto_locus)
185 set_curr_insn_location (e->goto_locus);
186 else if (e->flags & EDGE_EH)
187 {
188 basic_block bb = e->dest;
189 gimple_stmt_iterator gsi;
190
191 do
192 {
193 for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
194 {
195 gimple *stmt = gsi_stmt (i: gsi);
196 if (is_gimple_debug (gs: stmt))
197 continue;
198 if (gimple_has_location (g: stmt) || gimple_block (g: stmt))
199 {
200 set_curr_insn_location (gimple_location (g: stmt));
201 return;
202 }
203 }
204 /* Nothing found in this basic block. Make a half-assed attempt
205 to continue with another block. */
206 if (single_succ_p (bb))
207 bb = single_succ (bb);
208 else
209 bb = e->dest;
210 }
211 while (bb != e->dest);
212 }
213 else
214 {
215 basic_block bb = e->src;
216 gimple_stmt_iterator gsi;
217
218 do
219 {
220 for (gsi = gsi_last_bb (bb); !gsi_end_p (i: gsi); gsi_prev (i: &gsi))
221 {
222 gimple *stmt = gsi_stmt (i: gsi);
223 if (is_gimple_debug (gs: stmt))
224 continue;
225 if (gimple_has_location (g: stmt) || gimple_block (g: stmt))
226 {
227 set_curr_insn_location (gimple_location (g: stmt));
228 return;
229 }
230 }
231 /* Nothing found in this basic block. Make a half-assed attempt
232 to continue with another block. */
233 if (single_pred_p (bb))
234 bb = single_pred (bb);
235 else
236 bb = e->src;
237 }
238 while (bb != e->src);
239 }
240}
241
242/* Emit insns to copy SRC into DEST converting SRC if necessary. As
243 SRC/DEST might be BLKmode memory locations SIZEEXP is a tree from
244 which we deduce the size to copy in that case. */
245
246static inline rtx_insn *
247emit_partition_copy (rtx dest, rtx src, int unsignedsrcp, tree sizeexp)
248{
249 start_sequence ();
250
251 if (GET_MODE (src) != VOIDmode && GET_MODE (src) != GET_MODE (dest))
252 src = convert_to_mode (GET_MODE (dest), src, unsignedsrcp);
253 if (GET_MODE (src) == BLKmode)
254 {
255 gcc_assert (GET_MODE (dest) == BLKmode);
256 emit_block_move (dest, src, expr_size (sizeexp), BLOCK_OP_NORMAL);
257 }
258 else
259 emit_move_insn (dest, src);
260 do_pending_stack_adjust ();
261
262 rtx_insn *seq = get_insns ();
263 end_sequence ();
264
265 return seq;
266}
267
268/* Insert a copy instruction from partition SRC to DEST onto edge E. */
269
270static void
271insert_partition_copy_on_edge (edge e, int dest, int src, location_t locus)
272{
273 tree var;
274 if (dump_file && (dump_flags & TDF_DETAILS))
275 {
276 fprintf (stream: dump_file,
277 format: "Inserting a partition copy on edge BB%d->BB%d : "
278 "PART.%d = PART.%d",
279 e->src->index,
280 e->dest->index, dest, src);
281 fprintf (stream: dump_file, format: "\n");
282 }
283
284 gcc_assert (SA.partition_to_pseudo[dest]);
285 gcc_assert (SA.partition_to_pseudo[src]);
286
287 set_location_for_edge (e);
288 /* If a locus is provided, override the default. */
289 if (locus)
290 set_curr_insn_location (locus);
291
292 var = partition_to_var (map: SA.map, i: src);
293 rtx_insn *seq = emit_partition_copy (dest: copy_rtx (SA.partition_to_pseudo[dest]),
294 src: copy_rtx (SA.partition_to_pseudo[src]),
295 TYPE_UNSIGNED (TREE_TYPE (var)),
296 sizeexp: var);
297
298 insert_insn_on_edge (seq, e);
299}
300
301/* Insert a copy instruction from expression SRC to partition DEST
302 onto edge E. */
303
304static void
305insert_value_copy_on_edge (edge e, int dest, tree src, location_t locus)
306{
307 rtx dest_rtx, seq, x;
308 machine_mode dest_mode, src_mode;
309 int unsignedp;
310
311 if (dump_file && (dump_flags & TDF_DETAILS))
312 {
313 fprintf (stream: dump_file,
314 format: "Inserting a value copy on edge BB%d->BB%d : PART.%d = ",
315 e->src->index,
316 e->dest->index, dest);
317 print_generic_expr (dump_file, src, TDF_SLIM);
318 fprintf (stream: dump_file, format: "\n");
319 }
320
321 dest_rtx = copy_rtx (SA.partition_to_pseudo[dest]);
322 gcc_assert (dest_rtx);
323
324 set_location_for_edge (e);
325 /* If a locus is provided, override the default. */
326 if (locus)
327 set_curr_insn_location (locus);
328
329 start_sequence ();
330
331 tree name = partition_to_var (map: SA.map, i: dest);
332 src_mode = TYPE_MODE (TREE_TYPE (src));
333 dest_mode = GET_MODE (dest_rtx);
334 gcc_assert (src_mode == TYPE_MODE (TREE_TYPE (name)));
335 gcc_assert (!REG_P (dest_rtx)
336 || dest_mode == promote_ssa_mode (name, &unsignedp));
337
338 if (src_mode != dest_mode)
339 {
340 x = expand_expr (exp: src, NULL, mode: src_mode, modifier: EXPAND_NORMAL);
341 x = convert_modes (mode: dest_mode, oldmode: src_mode, x, unsignedp);
342 }
343 else if (src_mode == BLKmode)
344 {
345 x = dest_rtx;
346 store_expr (src, x, 0, false, false);
347 }
348 else
349 x = expand_expr (exp: src, target: dest_rtx, mode: dest_mode, modifier: EXPAND_NORMAL);
350
351 if (x != dest_rtx)
352 emit_move_insn (dest_rtx, x);
353 do_pending_stack_adjust ();
354
355 seq = get_insns ();
356 end_sequence ();
357
358 insert_insn_on_edge (seq, e);
359}
360
361/* Insert a copy instruction from RTL expression SRC to partition DEST
362 onto edge E. */
363
364static void
365insert_rtx_to_part_on_edge (edge e, int dest, rtx src, int unsignedsrcp,
366 location_t locus)
367{
368 if (dump_file && (dump_flags & TDF_DETAILS))
369 {
370 fprintf (stream: dump_file,
371 format: "Inserting a temp copy on edge BB%d->BB%d : PART.%d = ",
372 e->src->index,
373 e->dest->index, dest);
374 print_simple_rtl (dump_file, src);
375 fprintf (stream: dump_file, format: "\n");
376 }
377
378 gcc_assert (SA.partition_to_pseudo[dest]);
379
380 set_location_for_edge (e);
381 /* If a locus is provided, override the default. */
382 if (locus)
383 set_curr_insn_location (locus);
384
385 /* We give the destination as sizeexp in case src/dest are BLKmode
386 mems. Usually we give the source. As we result from SSA names
387 the left and right size should be the same (and no WITH_SIZE_EXPR
388 involved), so it doesn't matter. */
389 rtx_insn *seq = emit_partition_copy (dest: copy_rtx (SA.partition_to_pseudo[dest]),
390 src, unsignedsrcp,
391 sizeexp: partition_to_var (map: SA.map, i: dest));
392
393 insert_insn_on_edge (seq, e);
394}
395
396/* Insert a copy instruction from partition SRC to RTL lvalue DEST
397 onto edge E. */
398
399static void
400insert_part_to_rtx_on_edge (edge e, rtx dest, int src, location_t locus)
401{
402 tree var;
403 if (dump_file && (dump_flags & TDF_DETAILS))
404 {
405 fprintf (stream: dump_file,
406 format: "Inserting a temp copy on edge BB%d->BB%d : ",
407 e->src->index,
408 e->dest->index);
409 print_simple_rtl (dump_file, dest);
410 fprintf (stream: dump_file, format: "= PART.%d\n", src);
411 }
412
413 gcc_assert (SA.partition_to_pseudo[src]);
414
415 set_location_for_edge (e);
416 /* If a locus is provided, override the default. */
417 if (locus)
418 set_curr_insn_location (locus);
419
420 var = partition_to_var (map: SA.map, i: src);
421 rtx_insn *seq = emit_partition_copy (dest,
422 src: copy_rtx (SA.partition_to_pseudo[src]),
423 TYPE_UNSIGNED (TREE_TYPE (var)),
424 sizeexp: var);
425
426 insert_insn_on_edge (seq, e);
427}
428
429
430/* Create an elimination graph for map. */
431
432elim_graph::elim_graph (var_map map) :
433 nodes (30), edge_list (20), edge_locus (10), visited (map->num_partitions),
434 stack (30), map (map), const_dests (20), const_copies (20), copy_locus (10)
435{
436}
437
438
439/* Empty elimination graph G. */
440
441static inline void
442clear_elim_graph (elim_graph *g)
443{
444 g->nodes.truncate (size: 0);
445 g->edge_list.truncate (size: 0);
446 g->edge_locus.truncate (size: 0);
447}
448
449
450/* Return the number of nodes in graph G. */
451
452static inline int
453elim_graph_size (elim_graph *g)
454{
455 return g->nodes.length ();
456}
457
458
459/* Add NODE to graph G, if it doesn't exist already. */
460
461static inline void
462elim_graph_add_node (elim_graph *g, int node)
463{
464 int x;
465 int t;
466
467 FOR_EACH_VEC_ELT (g->nodes, x, t)
468 if (t == node)
469 return;
470 g->nodes.safe_push (obj: node);
471}
472
473
474/* Add the edge PRED->SUCC to graph G. */
475
476static inline void
477elim_graph_add_edge (elim_graph *g, int pred, int succ, location_t locus)
478{
479 g->edge_list.safe_push (obj: pred);
480 g->edge_list.safe_push (obj: succ);
481 g->edge_locus.safe_push (obj: locus);
482}
483
484
485/* Remove an edge from graph G for which NODE is the predecessor, and
486 return the successor node. -1 is returned if there is no such edge. */
487
488static inline int
489elim_graph_remove_succ_edge (elim_graph *g, int node, location_t *locus)
490{
491 int y;
492 unsigned x;
493 for (x = 0; x < g->edge_list.length (); x += 2)
494 if (g->edge_list[x] == node)
495 {
496 g->edge_list[x] = -1;
497 y = g->edge_list[x + 1];
498 g->edge_list[x + 1] = -1;
499 *locus = g->edge_locus[x / 2];
500 g->edge_locus[x / 2] = UNKNOWN_LOCATION;
501 return y;
502 }
503 *locus = UNKNOWN_LOCATION;
504 return -1;
505}
506
507
508/* Find all the nodes in GRAPH which are successors to NODE in the
509 edge list. VAR will hold the partition number found. CODE is the
510 code fragment executed for every node found. */
511
512#define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, LOCUS, CODE) \
513do { \
514 unsigned x_; \
515 int y_; \
516 for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \
517 { \
518 y_ = (GRAPH)->edge_list[x_]; \
519 if (y_ != (NODE)) \
520 continue; \
521 (void) ((VAR) = (GRAPH)->edge_list[x_ + 1]); \
522 (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \
523 CODE; \
524 } \
525} while (0)
526
527
528/* Find all the nodes which are predecessors of NODE in the edge list for
529 GRAPH. VAR will hold the partition number found. CODE is the
530 code fragment executed for every node found. */
531
532#define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, LOCUS, CODE) \
533do { \
534 unsigned x_; \
535 int y_; \
536 for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \
537 { \
538 y_ = (GRAPH)->edge_list[x_ + 1]; \
539 if (y_ != (NODE)) \
540 continue; \
541 (void) ((VAR) = (GRAPH)->edge_list[x_]); \
542 (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \
543 CODE; \
544 } \
545} while (0)
546
547
548/* Add T to elimination graph G. */
549
550static inline void
551eliminate_name (elim_graph *g, int T)
552{
553 elim_graph_add_node (g, node: T);
554}
555
556/* Return true if this phi argument T should have a copy queued when using
557 var_map MAP. PHI nodes should contain only ssa_names and invariants. A
558 test for ssa_name is definitely simpler, but don't let invalid contents
559 slip through in the meantime. */
560
561static inline bool
562queue_phi_copy_p (var_map map, tree t)
563{
564 if (TREE_CODE (t) == SSA_NAME)
565 {
566 if (var_to_partition (map, var: t) == NO_PARTITION)
567 return true;
568 return false;
569 }
570 gcc_checking_assert (is_gimple_min_invariant (t));
571 return true;
572}
573
574/* Build elimination graph G for basic block BB on incoming PHI edge
575 G->e. */
576
577static void
578eliminate_build (elim_graph *g)
579{
580 tree Ti;
581 int p0, pi;
582 gphi_iterator gsi;
583
584 clear_elim_graph (g);
585
586 for (gsi = gsi_start_phis (g->e->dest); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
587 {
588 gphi *phi = gsi.phi ();
589 location_t locus;
590
591 p0 = var_to_partition (map: g->map, var: gimple_phi_result (gs: phi));
592 /* Ignore results which are not in partitions. */
593 if (p0 == NO_PARTITION)
594 continue;
595
596 Ti = PHI_ARG_DEF (phi, g->e->dest_idx);
597 /* See set_location_for_edge for the rationale. */
598 if (g->e->flags & EDGE_EH)
599 locus = UNKNOWN_LOCATION;
600 else
601 locus = gimple_phi_arg_location_from_edge (phi, e: g->e);
602
603 /* If this argument is a constant, or a SSA_NAME which is being
604 left in SSA form, just queue a copy to be emitted on this
605 edge. */
606 if (queue_phi_copy_p (map: g->map, t: Ti))
607 {
608 /* Save constant copies until all other copies have been emitted
609 on this edge. */
610 g->const_dests.safe_push (obj: p0);
611 g->const_copies.safe_push (obj: Ti);
612 g->copy_locus.safe_push (obj: locus);
613 }
614 else
615 {
616 pi = var_to_partition (map: g->map, var: Ti);
617 if (p0 != pi)
618 {
619 eliminate_name (g, T: p0);
620 eliminate_name (g, T: pi);
621 elim_graph_add_edge (g, pred: p0, succ: pi, locus);
622 }
623 }
624 }
625}
626
627
628/* Push successors of T onto the elimination stack for G. */
629
630static void
631elim_forward (elim_graph *g, int T)
632{
633 int S;
634 location_t locus;
635
636 bitmap_set_bit (map: g->visited, bitno: T);
637 FOR_EACH_ELIM_GRAPH_SUCC (g, T, S, locus,
638 {
639 if (!bitmap_bit_p (g->visited, S))
640 elim_forward (g, S);
641 });
642 g->stack.safe_push (obj: T);
643}
644
645
646/* Return 1 if there unvisited predecessors of T in graph G. */
647
648static int
649elim_unvisited_predecessor (elim_graph *g, int T)
650{
651 int P;
652 location_t locus;
653
654 FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus,
655 {
656 if (!bitmap_bit_p (g->visited, P))
657 return 1;
658 });
659 return 0;
660}
661
662/* Process predecessors first, and insert a copy. */
663
664static void
665elim_backward (elim_graph *g, int T)
666{
667 int P;
668 location_t locus;
669
670 bitmap_set_bit (map: g->visited, bitno: T);
671 FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus,
672 {
673 if (!bitmap_bit_p (g->visited, P))
674 {
675 elim_backward (g, P);
676 insert_partition_copy_on_edge (g->e, P, T, locus);
677 }
678 });
679}
680
681/* Allocate a new pseudo register usable for storing values sitting
682 in NAME (a decl or SSA name), i.e. with matching mode and attributes. */
683
684static rtx
685get_temp_reg (tree name)
686{
687 tree type = TREE_TYPE (name);
688 int unsignedp;
689 machine_mode reg_mode = promote_ssa_mode (name, &unsignedp);
690 if (reg_mode == BLKmode)
691 return assign_temp (type, 0, 0);
692 rtx x = gen_reg_rtx (reg_mode);
693 if (POINTER_TYPE_P (type))
694 mark_reg_pointer (x, TYPE_ALIGN (TREE_TYPE (type)));
695 return x;
696}
697
698/* Insert required copies for T in graph G. Check for a strongly connected
699 region, and create a temporary to break the cycle if one is found. */
700
701static void
702elim_create (elim_graph *g, int T)
703{
704 int P, S;
705 location_t locus;
706
707 if (elim_unvisited_predecessor (g, T))
708 {
709 tree var = partition_to_var (map: g->map, i: T);
710 rtx U = get_temp_reg (name: var);
711 int unsignedsrcp = TYPE_UNSIGNED (TREE_TYPE (var));
712
713 insert_part_to_rtx_on_edge (e: g->e, dest: U, src: T, UNKNOWN_LOCATION);
714 FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus,
715 {
716 if (!bitmap_bit_p (g->visited, P))
717 {
718 elim_backward (g, P);
719 insert_rtx_to_part_on_edge (g->e, P, U, unsignedsrcp, locus);
720 }
721 });
722 }
723 else
724 {
725 S = elim_graph_remove_succ_edge (g, node: T, locus: &locus);
726 if (S != -1)
727 {
728 bitmap_set_bit (map: g->visited, bitno: T);
729 insert_partition_copy_on_edge (e: g->e, dest: T, src: S, locus);
730 }
731 }
732}
733
734
735/* Eliminate all the phi nodes on edge E in graph G. */
736
737static void
738eliminate_phi (edge e, elim_graph *g)
739{
740 int x;
741
742 gcc_assert (g->const_copies.length () == 0);
743 gcc_assert (g->copy_locus.length () == 0);
744
745 /* Abnormal edges already have everything coalesced. */
746 if (e->flags & EDGE_ABNORMAL)
747 return;
748
749 g->e = e;
750
751 eliminate_build (g);
752
753 if (elim_graph_size (g) != 0)
754 {
755 int part;
756
757 bitmap_clear (g->visited);
758 g->stack.truncate (size: 0);
759
760 FOR_EACH_VEC_ELT (g->nodes, x, part)
761 {
762 if (!bitmap_bit_p (map: g->visited, bitno: part))
763 elim_forward (g, T: part);
764 }
765
766 bitmap_clear (g->visited);
767 while (g->stack.length () > 0)
768 {
769 x = g->stack.pop ();
770 if (!bitmap_bit_p (map: g->visited, bitno: x))
771 elim_create (g, T: x);
772 }
773 }
774
775 /* If there are any pending constant copies, issue them now. */
776 while (g->const_copies.length () > 0)
777 {
778 int dest;
779 tree src;
780 location_t locus;
781
782 src = g->const_copies.pop ();
783 dest = g->const_dests.pop ();
784 locus = g->copy_locus.pop ();
785 insert_value_copy_on_edge (e, dest, src, locus);
786 }
787}
788
789
790/* Remove each argument from PHI. If an arg was the last use of an SSA_NAME,
791 check to see if this allows another PHI node to be removed. */
792
793static void
794remove_gimple_phi_args (gphi *phi)
795{
796 use_operand_p arg_p;
797 ssa_op_iter iter;
798
799 if (dump_file && (dump_flags & TDF_DETAILS))
800 {
801 fprintf (stream: dump_file, format: "Removing Dead PHI definition: ");
802 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
803 }
804
805 FOR_EACH_PHI_ARG (arg_p, phi, iter, SSA_OP_USE)
806 {
807 tree arg = USE_FROM_PTR (arg_p);
808 if (TREE_CODE (arg) == SSA_NAME)
809 {
810 /* Remove the reference to the existing argument. */
811 SET_USE (arg_p, NULL_TREE);
812 if (has_zero_uses (var: arg))
813 {
814 gimple *stmt;
815 gimple_stmt_iterator gsi;
816
817 stmt = SSA_NAME_DEF_STMT (arg);
818
819 /* Also remove the def if it is a PHI node. */
820 if (gimple_code (g: stmt) == GIMPLE_PHI)
821 {
822 remove_gimple_phi_args (phi: as_a <gphi *> (p: stmt));
823 gsi = gsi_for_stmt (stmt);
824 remove_phi_node (&gsi, true);
825 }
826
827 }
828 }
829 }
830}
831
832/* Remove any PHI node which is a virtual PHI, or a PHI with no uses. */
833
834static void
835eliminate_useless_phis (void)
836{
837 basic_block bb;
838 gphi_iterator gsi;
839 tree result;
840
841 FOR_EACH_BB_FN (bb, cfun)
842 {
843 for (gsi = gsi_start_phis (bb); !gsi_end_p (i: gsi); )
844 {
845 gphi *phi = gsi.phi ();
846 result = gimple_phi_result (gs: phi);
847 if (virtual_operand_p (op: result))
848 remove_phi_node (&gsi, true);
849 else
850 {
851 /* Also remove real PHIs with no uses. */
852 if (has_zero_uses (var: result))
853 {
854 remove_gimple_phi_args (phi);
855 remove_phi_node (&gsi, true);
856 }
857 else
858 gsi_next (i: &gsi);
859 }
860 }
861 }
862}
863
864
865/* This function will rewrite the current program using the variable mapping
866 found in MAP. If the replacement vector VALUES is provided, any
867 occurrences of partitions with non-null entries in the vector will be
868 replaced with the expression in the vector instead of its mapped
869 variable. */
870
871static void
872rewrite_trees (var_map map)
873{
874 if (!flag_checking)
875 return;
876
877 basic_block bb;
878 /* Search for PHIs where the destination has no partition, but one
879 or more arguments has a partition. This should not happen and can
880 create incorrect code. */
881 FOR_EACH_BB_FN (bb, cfun)
882 {
883 gphi_iterator gsi;
884 for (gsi = gsi_start_phis (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
885 {
886 gphi *phi = gsi.phi ();
887 tree T0 = var_to_partition_to_var (map, var: gimple_phi_result (gs: phi));
888 if (T0 == NULL_TREE)
889 {
890 size_t i;
891 for (i = 0; i < gimple_phi_num_args (gs: phi); i++)
892 {
893 tree arg = PHI_ARG_DEF (phi, i);
894
895 if (TREE_CODE (arg) == SSA_NAME
896 && var_to_partition (map, var: arg) != NO_PARTITION)
897 {
898 fprintf (stderr, format: "Argument of PHI is in a partition :(");
899 print_generic_expr (stderr, arg, TDF_SLIM);
900 fprintf (stderr, format: "), but the result is not :");
901 print_gimple_stmt (stderr, phi, 0, TDF_SLIM);
902 internal_error ("SSA corruption");
903 }
904 }
905 }
906 }
907 }
908}
909
910/* Create a default def for VAR. */
911
912static void
913create_default_def (tree var, void *arg ATTRIBUTE_UNUSED)
914{
915 if (!is_gimple_reg (var))
916 return;
917
918 tree ssa = get_or_create_ssa_default_def (cfun, var);
919 gcc_assert (ssa);
920}
921
922/* Call CALLBACK for all PARM_DECLs and RESULT_DECLs for which
923 assign_parms may ask for a default partition. */
924
925static void
926for_all_parms (void (*callback)(tree var, void *arg), void *arg)
927{
928 for (tree var = DECL_ARGUMENTS (current_function_decl); var;
929 var = DECL_CHAIN (var))
930 callback (var, arg);
931 if (!VOID_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
932 callback (DECL_RESULT (current_function_decl), arg);
933 if (cfun->static_chain_decl)
934 callback (cfun->static_chain_decl, arg);
935}
936
937/* We need to pass two arguments to set_parm_default_def_partition,
938 but for_all_parms only supports one. Use a pair. */
939
940typedef std::pair<var_map, bitmap> parm_default_def_partition_arg;
941
942/* Set in ARG's PARTS bitmap the bit corresponding to the partition in
943 ARG's MAP containing VAR's default def. */
944
945static void
946set_parm_default_def_partition (tree var, void *arg_)
947{
948 parm_default_def_partition_arg *arg = (parm_default_def_partition_arg *)arg_;
949 var_map map = arg->first;
950 bitmap parts = arg->second;
951
952 if (!is_gimple_reg (var))
953 return;
954
955 tree ssa = ssa_default_def (cfun, var);
956 gcc_assert (ssa);
957
958 int version = var_to_partition (map, var: ssa);
959 gcc_assert (version != NO_PARTITION);
960
961 bool changed = bitmap_set_bit (parts, version);
962 gcc_assert (changed);
963}
964
965/* Allocate and return a bitmap that has a bit set for each partition
966 that contains a default def for a parameter. */
967
968static bitmap
969get_parm_default_def_partitions (var_map map)
970{
971 bitmap parm_default_def_parts = BITMAP_ALLOC (NULL);
972
973 parm_default_def_partition_arg
974 arg = std::make_pair (x&: map, y&: parm_default_def_parts);
975
976 for_all_parms (callback: set_parm_default_def_partition, arg: &arg);
977
978 return parm_default_def_parts;
979}
980
981/* Allocate and return a bitmap that has a bit set for each partition
982 that contains an undefined value. */
983
984static bitmap
985get_undefined_value_partitions (var_map map)
986{
987 bitmap undefined_value_parts = BITMAP_ALLOC (NULL);
988
989 for (unsigned int i = 1; i < num_ssa_names; i++)
990 {
991 tree var = ssa_name (i);
992 if (var
993 && !virtual_operand_p (op: var)
994 && !has_zero_uses (var)
995 && ssa_undefined_value_p (var))
996 {
997 const int p = var_to_partition (map, var);
998 if (p != NO_PARTITION)
999 bitmap_set_bit (undefined_value_parts, p);
1000 }
1001 }
1002
1003 return undefined_value_parts;
1004}
1005
1006/* Given the out-of-ssa info object SA (with prepared partitions)
1007 eliminate all phi nodes in all basic blocks. Afterwards no
1008 basic block will have phi nodes anymore and there are possibly
1009 some RTL instructions inserted on edges. */
1010
1011void
1012expand_phi_nodes (struct ssaexpand *sa)
1013{
1014 basic_block bb;
1015 elim_graph g (sa->map);
1016
1017 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb,
1018 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
1019 if (!gimple_seq_empty_p (s: phi_nodes (bb)))
1020 {
1021 edge e;
1022 edge_iterator ei;
1023 FOR_EACH_EDGE (e, ei, bb->preds)
1024 eliminate_phi (e, g: &g);
1025 set_phi_nodes (bb, NULL);
1026 /* We can't redirect EH edges in RTL land, so we need to do this
1027 here. Redirection happens only when splitting is necessary,
1028 which it is only for critical edges, normally. For EH edges
1029 it might also be necessary when the successor has more than
1030 one predecessor. In that case the edge is either required to
1031 be fallthru (which EH edges aren't), or the predecessor needs
1032 to end with a jump (which again, isn't the case with EH edges).
1033 Hence, split all EH edges on which we inserted instructions
1034 and whose successor has multiple predecessors. */
1035 for (ei = ei_start (bb->preds); (e = ei_safe_edge (i: ei)); )
1036 {
1037 if (e->insns.r && (e->flags & EDGE_EH)
1038 && !single_pred_p (bb: e->dest))
1039 {
1040 rtx_insn *insns = e->insns.r;
1041 basic_block bb;
1042 e->insns.r = NULL;
1043 bb = split_edge (e);
1044 single_pred_edge (bb)->insns.r = insns;
1045 }
1046 else
1047 ei_next (i: &ei);
1048 }
1049 }
1050}
1051
1052
1053/* Remove the ssa-names in the current function and translate them into normal
1054 compiler variables. PERFORM_TER is true if Temporary Expression Replacement
1055 should also be used. */
1056
1057static void
1058remove_ssa_form (bool perform_ter, struct ssaexpand *sa)
1059{
1060 bitmap values = NULL;
1061 var_map map;
1062
1063 for_all_parms (callback: create_default_def, NULL);
1064 map = init_var_map (num_ssa_names);
1065 coalesce_ssa_name (map);
1066
1067 /* Return to viewing the variable list as just all reference variables after
1068 coalescing has been performed. */
1069 partition_view_normal (map);
1070
1071 if (dump_file && (dump_flags & TDF_DETAILS))
1072 {
1073 fprintf (stream: dump_file, format: "After Coalescing:\n");
1074 dump_var_map (dump_file, map);
1075 }
1076
1077 if (perform_ter)
1078 {
1079 values = find_replaceable_exprs (map);
1080 if (values && dump_file && (dump_flags & TDF_DETAILS))
1081 dump_replaceable_exprs (dump_file, values);
1082 }
1083
1084 rewrite_trees (map);
1085
1086 sa->map = map;
1087 sa->values = values;
1088 sa->partitions_for_parm_default_defs = get_parm_default_def_partitions (map);
1089 sa->partitions_for_undefined_values = get_undefined_value_partitions (map);
1090}
1091
1092
1093/* If not already done so for basic block BB, assign increasing uids
1094 to each of its instructions. */
1095
1096static void
1097maybe_renumber_stmts_bb (basic_block bb)
1098{
1099 unsigned i = 0;
1100 gimple_stmt_iterator gsi;
1101
1102 if (!bb->aux)
1103 return;
1104 bb->aux = NULL;
1105 for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
1106 {
1107 gimple *stmt = gsi_stmt (i: gsi);
1108 gimple_set_uid (g: stmt, uid: i);
1109 i++;
1110 }
1111}
1112
1113
1114/* Return true if we can determine that the SSA_NAMEs RESULT (a result
1115 of a PHI node) and ARG (one of its arguments) conflict. Return false
1116 otherwise, also when we simply aren't sure. */
1117
1118static bool
1119trivially_conflicts_p (basic_block bb, tree result, tree arg)
1120{
1121 use_operand_p use;
1122 imm_use_iterator imm_iter;
1123 gimple *defa = SSA_NAME_DEF_STMT (arg);
1124
1125 /* If ARG isn't defined in the same block it's too complicated for
1126 our little mind. */
1127 if (gimple_bb (g: defa) != bb)
1128 return false;
1129
1130 FOR_EACH_IMM_USE_FAST (use, imm_iter, result)
1131 {
1132 gimple *use_stmt = USE_STMT (use);
1133 if (is_gimple_debug (gs: use_stmt))
1134 continue;
1135 /* Now, if there's a use of RESULT that lies outside this basic block,
1136 then there surely is a conflict with ARG. */
1137 if (gimple_bb (g: use_stmt) != bb)
1138 return true;
1139 if (gimple_code (g: use_stmt) == GIMPLE_PHI)
1140 continue;
1141 /* The use now is in a real stmt of BB, so if ARG was defined
1142 in a PHI node (like RESULT) both conflict. */
1143 if (gimple_code (g: defa) == GIMPLE_PHI)
1144 return true;
1145 maybe_renumber_stmts_bb (bb);
1146 /* If the use of RESULT occurs after the definition of ARG,
1147 the two conflict too. */
1148 if (gimple_uid (g: defa) < gimple_uid (g: use_stmt))
1149 return true;
1150 }
1151
1152 return false;
1153}
1154
1155
1156/* Search every PHI node for arguments associated with backedges which
1157 we can trivially determine will need a copy (the argument is either
1158 not an SSA_NAME or the argument has a different underlying variable
1159 than the PHI result).
1160
1161 Insert a copy from the PHI argument to a new destination at the
1162 end of the block with the backedge to the top of the loop. Update
1163 the PHI argument to reference this new destination. */
1164
1165static void
1166insert_backedge_copies (void)
1167{
1168 basic_block bb;
1169 gphi_iterator gsi;
1170
1171 mark_dfs_back_edges ();
1172
1173 FOR_EACH_BB_FN (bb, cfun)
1174 {
1175 /* Mark block as possibly needing calculation of UIDs. */
1176 bb->aux = &bb->aux;
1177
1178 for (gsi = gsi_start_phis (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
1179 {
1180 gphi *phi = gsi.phi ();
1181 tree result = gimple_phi_result (gs: phi);
1182 size_t i;
1183
1184 if (virtual_operand_p (op: result))
1185 continue;
1186
1187 for (i = 0; i < gimple_phi_num_args (gs: phi); i++)
1188 {
1189 tree arg = gimple_phi_arg_def (gs: phi, index: i);
1190 edge e = gimple_phi_arg_edge (phi, i);
1191 /* We are only interested in copies emitted on critical
1192 backedges. */
1193 if (!(e->flags & EDGE_DFS_BACK)
1194 || !EDGE_CRITICAL_P (e))
1195 continue;
1196
1197 /* If the argument is not an SSA_NAME, then we will need a
1198 constant initialization. If the argument is an SSA_NAME then
1199 a copy statement may be needed. First handle the case
1200 where we cannot insert before the argument definition. */
1201 if (TREE_CODE (arg) != SSA_NAME
1202 || (gimple_code (SSA_NAME_DEF_STMT (arg)) == GIMPLE_PHI
1203 && trivially_conflicts_p (bb, result, arg)))
1204 {
1205 tree name;
1206 gassign *stmt;
1207 gimple *last = NULL;
1208 gimple_stmt_iterator gsi2;
1209
1210 gsi2 = gsi_last_bb (bb: gimple_phi_arg_edge (phi, i)->src);
1211 if (!gsi_end_p (i: gsi2))
1212 last = gsi_stmt (i: gsi2);
1213
1214 /* In theory the only way we ought to get back to the
1215 start of a loop should be with a COND_EXPR or GOTO_EXPR.
1216 However, better safe than sorry.
1217 If the block ends with a control statement or
1218 something that might throw, then we have to
1219 insert this assignment before the last
1220 statement. Else insert it after the last statement. */
1221 if (last && stmt_ends_bb_p (last))
1222 {
1223 /* If the last statement in the block is the definition
1224 site of the PHI argument, then we can't insert
1225 anything after it. */
1226 if (TREE_CODE (arg) == SSA_NAME
1227 && SSA_NAME_DEF_STMT (arg) == last)
1228 continue;
1229 }
1230
1231 /* Create a new instance of the underlying variable of the
1232 PHI result. */
1233 name = copy_ssa_name (var: result);
1234 stmt = gimple_build_assign (name,
1235 gimple_phi_arg_def (gs: phi, index: i));
1236
1237 /* copy location if present. */
1238 if (gimple_phi_arg_has_location (phi, i))
1239 gimple_set_location (g: stmt,
1240 location: gimple_phi_arg_location (phi, i));
1241
1242 /* Insert the new statement into the block and update
1243 the PHI node. */
1244 if (last && stmt_ends_bb_p (last))
1245 gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT);
1246 else
1247 gsi_insert_after (&gsi2, stmt, GSI_NEW_STMT);
1248 SET_PHI_ARG_DEF (phi, i, name);
1249 }
1250 /* Insert a copy before the definition of the backedge value
1251 and adjust all conflicting uses. */
1252 else if (trivially_conflicts_p (bb, result, arg))
1253 {
1254 gimple *def = SSA_NAME_DEF_STMT (arg);
1255 if (gimple_nop_p (g: def)
1256 || gimple_code (g: def) == GIMPLE_PHI)
1257 continue;
1258 tree name = copy_ssa_name (var: result);
1259 gimple *stmt = gimple_build_assign (name, result);
1260 imm_use_iterator imm_iter;
1261 gimple *use_stmt;
1262 /* The following matches trivially_conflicts_p. */
1263 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, result)
1264 {
1265 if (gimple_bb (g: use_stmt) != bb
1266 || (gimple_code (g: use_stmt) != GIMPLE_PHI
1267 && (maybe_renumber_stmts_bb (bb), true)
1268 && gimple_uid (g: use_stmt) > gimple_uid (g: def)))
1269 {
1270 use_operand_p use;
1271 FOR_EACH_IMM_USE_ON_STMT (use, imm_iter)
1272 SET_USE (use, name);
1273 }
1274 }
1275 gimple_stmt_iterator gsi = gsi_for_stmt (def);
1276 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1277 }
1278 }
1279 }
1280
1281 /* Unmark this block again. */
1282 bb->aux = NULL;
1283 }
1284}
1285
1286/* Remove indirect clobbers. */
1287
1288static void
1289remove_indirect_clobbers (void)
1290{
1291 basic_block bb;
1292
1293 FOR_EACH_BB_FN (bb, cfun)
1294 for (auto gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi);)
1295 {
1296 gimple *stmt = gsi_stmt (i: gsi);
1297 if (gimple_clobber_p (s: stmt))
1298 {
1299 tree lhs = gimple_assign_lhs (gs: stmt);
1300 if (TREE_CODE (lhs) == MEM_REF
1301 && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME)
1302 {
1303 unlink_stmt_vdef (stmt);
1304 gsi_remove (&gsi, true);
1305 release_defs (stmt);
1306 continue;
1307 }
1308 }
1309 gsi_next (i: &gsi);
1310 }
1311}
1312
1313/* Free all memory associated with going out of SSA form. SA is
1314 the outof-SSA info object. */
1315
1316void
1317finish_out_of_ssa (struct ssaexpand *sa)
1318{
1319 free (ptr: sa->partition_to_pseudo);
1320 if (sa->values)
1321 BITMAP_FREE (sa->values);
1322 delete_var_map (sa->map);
1323 BITMAP_FREE (sa->partitions_for_parm_default_defs);
1324 BITMAP_FREE (sa->partitions_for_undefined_values);
1325 memset (s: sa, c: 0, n: sizeof *sa);
1326}
1327
1328/* Take the current function out of SSA form, translating PHIs as described in
1329 R. Morgan, ``Building an Optimizing Compiler'',
1330 Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */
1331
1332unsigned int
1333rewrite_out_of_ssa (struct ssaexpand *sa)
1334{
1335 /* Remove remaining indirect clobbers as we do not need those anymore.
1336 Those might extend SSA lifetime and restrict coalescing. */
1337 remove_indirect_clobbers ();
1338
1339 /* If elimination of a PHI requires inserting a copy on a backedge,
1340 then we will have to split the backedge which has numerous
1341 undesirable performance effects.
1342
1343 A significant number of such cases can be handled here by inserting
1344 copies into the loop itself. */
1345 insert_backedge_copies ();
1346
1347 /* Eliminate PHIs which are of no use, such as virtual or dead phis. */
1348 eliminate_useless_phis ();
1349
1350 if (dump_file && (dump_flags & TDF_DETAILS))
1351 gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
1352
1353 remove_ssa_form (flag_tree_ter, sa);
1354
1355 if (dump_file && (dump_flags & TDF_DETAILS))
1356 gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
1357
1358 return 0;
1359}
1360

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