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