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 44439080 : ssa_is_replaceable_p (gimple *stmt)
62 : {
63 44439080 : use_operand_p use_p;
64 44439080 : tree def;
65 44439080 : gimple *use_stmt;
66 :
67 : /* Only consider modify stmts and direct internal fn calls that are
68 : not also tail-calls. */
69 44439080 : gcall *call;
70 44439080 : if (!is_gimple_assign (stmt)
71 49989677 : && (!(call = dyn_cast <gcall *> (stmt))
72 5550597 : || gimple_call_tail_p (call)
73 5370223 : || !gimple_call_internal_p (call)
74 213065 : || !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 33038087 : if (stmt_could_throw_p (cfun, stmt))
79 : return false;
80 :
81 : /* Punt if there is more than 1 def. */
82 32006743 : def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
83 32006743 : if (!def)
84 : return false;
85 :
86 : /* Only consider definitions which have a single use. */
87 25039824 : 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 21253304 : if (gimple_code (use_stmt) == GIMPLE_PHI)
92 : return false;
93 :
94 : /* There must be no VDEFs. */
95 39747778 : if (gimple_vdef (stmt))
96 : return false;
97 :
98 : /* Float expressions must go through memory if float-store is on. */
99 19873889 : if (flag_float_store
100 19873889 : && 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 19873438 : if (is_gimple_assign (stmt)
106 19792009 : && gimple_assign_rhs_code (stmt) == VAR_DECL
107 20869878 : && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt)))
108 : return false;
109 :
110 : /* Leave any stmt with volatile operands alone as well. */
111 39745194 : if (gimple_has_volatile_ops (stmt))
112 259831 : 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 1784088 : set_location_for_edge (edge e)
190 : {
191 1784088 : if (e->goto_locus)
192 131594 : set_curr_insn_location (e->goto_locus);
193 1652494 : else if (e->flags & EDGE_EH)
194 : {
195 8613 : basic_block bb = e->dest;
196 8775 : gimple_stmt_iterator gsi;
197 :
198 8775 : do
199 : {
200 174369 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
201 : {
202 165423 : gimple *stmt = gsi_stmt (gsi);
203 165423 : if (is_gimple_debug (stmt))
204 132391 : continue;
205 33032 : if (gimple_has_location (stmt) || gimple_block (stmt))
206 : {
207 8604 : set_curr_insn_location (gimple_location (stmt));
208 8604 : 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 1643881 : basic_block bb = e->src;
223 2005386 : gimple_stmt_iterator gsi;
224 :
225 2005386 : do
226 : {
227 7642186 : for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
228 : {
229 4680043 : gimple *stmt = gsi_stmt (gsi);
230 4680043 : if (is_gimple_debug (stmt))
231 1644219 : continue;
232 3035824 : if (gimple_has_location (stmt) || gimple_block (stmt))
233 : {
234 1393607 : set_curr_insn_location (gimple_location (stmt));
235 1393607 : return;
236 : }
237 : }
238 : /* Nothing found in this basic block. Make a half-assed attempt
239 : to continue with another block. */
240 611779 : if (single_pred_p (bb))
241 361505 : bb = single_pred (bb);
242 : else
243 250274 : bb = e->src;
244 : }
245 611779 : 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 503441 : emit_partition_copy (rtx dest, rtx src, int unsignedsrcp, tree sizeexp)
255 : {
256 503441 : start_sequence ();
257 :
258 503441 : if (GET_MODE (src) != VOIDmode && GET_MODE (src) != GET_MODE (dest))
259 0 : src = convert_to_mode (GET_MODE (dest), src, unsignedsrcp);
260 503441 : 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 503421 : emit_move_insn (dest, src);
267 503441 : do_pending_stack_adjust ();
268 :
269 503441 : return end_sequence ();
270 : }
271 :
272 : /* Insert a copy instruction from partition SRC to DEST onto edge E. */
273 :
274 : static void
275 494997 : insert_partition_copy_on_edge (edge e, int dest, int src, location_t locus)
276 : {
277 494997 : tree var;
278 494997 : 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 494997 : gcc_assert (SA.partition_to_pseudo[dest]);
289 494997 : gcc_assert (SA.partition_to_pseudo[src]);
290 :
291 494997 : set_location_for_edge (e);
292 : /* If a locus is provided, override the default. */
293 494997 : if (locus)
294 215725 : set_curr_insn_location (locus);
295 :
296 494997 : var = partition_to_var (SA.map, src);
297 494997 : rtx_insn *seq = emit_partition_copy (copy_rtx (SA.partition_to_pseudo[dest]),
298 494997 : copy_rtx (SA.partition_to_pseudo[src]),
299 494997 : TYPE_UNSIGNED (TREE_TYPE (var)),
300 : var);
301 :
302 494997 : insert_insn_on_edge (seq, e);
303 494997 : }
304 :
305 : /* Insert a copy instruction from expression SRC to partition DEST
306 : onto edge E. */
307 :
308 : static void
309 1280647 : insert_value_copy_on_edge (edge e, int dest, tree src, location_t locus)
310 : {
311 1280647 : rtx dest_rtx, seq, x;
312 1280647 : machine_mode dest_mode, src_mode;
313 1280647 : int unsignedp;
314 :
315 1280647 : 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 1280647 : dest_rtx = copy_rtx (SA.partition_to_pseudo[dest]);
326 1280647 : gcc_assert (dest_rtx);
327 :
328 1280647 : set_location_for_edge (e);
329 : /* If a locus is provided, override the default. */
330 1280647 : if (locus)
331 697230 : set_curr_insn_location (locus);
332 :
333 1280647 : start_sequence ();
334 :
335 1280647 : tree name = partition_to_var (SA.map, dest);
336 1280647 : src_mode = TYPE_MODE (TREE_TYPE (src));
337 1280647 : dest_mode = GET_MODE (dest_rtx);
338 1280647 : gcc_assert (src_mode == TYPE_MODE (TREE_TYPE (name)));
339 1280647 : gcc_assert (!REG_P (dest_rtx)
340 : || dest_mode == promote_ssa_mode (name, &unsignedp));
341 :
342 1280647 : 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 1280647 : else if (src_mode == BLKmode)
348 : {
349 25 : x = dest_rtx;
350 25 : store_expr (src, x, 0, false, false);
351 : }
352 : else
353 1280622 : x = expand_expr (src, dest_rtx, dest_mode, EXPAND_NORMAL);
354 :
355 1280647 : if (x != dest_rtx)
356 1227639 : emit_move_insn (dest_rtx, x);
357 1280647 : do_pending_stack_adjust ();
358 :
359 1280647 : seq = end_sequence ();
360 :
361 1280647 : insert_insn_on_edge (seq, e);
362 1280647 : }
363 :
364 : /* Insert a copy instruction from RTL expression SRC to partition DEST
365 : onto edge E. */
366 :
367 : static void
368 4222 : insert_rtx_to_part_on_edge (edge e, int dest, rtx src, int unsignedsrcp,
369 : location_t locus)
370 : {
371 4222 : 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 4222 : gcc_assert (SA.partition_to_pseudo[dest]);
382 :
383 4222 : set_location_for_edge (e);
384 : /* If a locus is provided, override the default. */
385 4222 : if (locus)
386 1884 : 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 4222 : 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 4222 : insert_insn_on_edge (seq, e);
397 4222 : }
398 :
399 : /* Insert a copy instruction from partition SRC to RTL lvalue DEST
400 : onto edge E. */
401 :
402 : static void
403 4222 : insert_part_to_rtx_on_edge (edge e, rtx dest, int src, location_t locus)
404 : {
405 4222 : tree var;
406 4222 : 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 4222 : gcc_assert (SA.partition_to_pseudo[src]);
417 :
418 4222 : set_location_for_edge (e);
419 : /* If a locus is provided, override the default. */
420 4222 : if (locus)
421 0 : set_curr_insn_location (locus);
422 :
423 4222 : var = partition_to_var (SA.map, src);
424 4222 : rtx_insn *seq = emit_partition_copy (dest,
425 4222 : copy_rtx (SA.partition_to_pseudo[src]),
426 4222 : TYPE_UNSIGNED (TREE_TYPE (var)),
427 : var);
428 :
429 4222 : insert_insn_on_edge (seq, e);
430 4222 : }
431 :
432 :
433 : /* Create an elimination graph for map. */
434 :
435 1515899 : elim_graph::elim_graph (var_map map) :
436 1515899 : nodes (30), edge_list (20), edge_locus (10), visited (map->num_partitions),
437 1515899 : stack (30), map (map), const_dests (20), const_copies (20), copy_locus (10)
438 : {
439 1515899 : }
440 :
441 :
442 : /* Empty elimination graph G. */
443 :
444 : static inline void
445 3748180 : clear_elim_graph (elim_graph *g)
446 : {
447 3748180 : g->nodes.truncate (0);
448 3748180 : g->edge_list.truncate (0);
449 3748180 : g->edge_locus.truncate (0);
450 3748180 : }
451 :
452 :
453 : /* Return the number of nodes in graph G. */
454 :
455 : static inline int
456 3748180 : elim_graph_size (elim_graph *g)
457 : {
458 11244540 : 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 998438 : elim_graph_add_node (elim_graph *g, int node)
466 : {
467 998438 : int x;
468 998438 : int t;
469 :
470 2293596 : FOR_EACH_VEC_ELT (g->nodes, x, t)
471 1336463 : if (t == node)
472 998438 : return;
473 957133 : g->nodes.safe_push (node);
474 : }
475 :
476 :
477 : /* Add the edge PRED->SUCC to graph G. */
478 :
479 : static inline void
480 499219 : elim_graph_add_edge (elim_graph *g, int pred, int succ, location_t locus)
481 : {
482 499219 : g->edge_list.safe_push (pred);
483 499219 : g->edge_list.safe_push (succ);
484 499219 : g->edge_locus.safe_push (locus);
485 499219 : }
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 948179 : elim_graph_remove_succ_edge (elim_graph *g, int node, location_t *locus)
493 : {
494 948179 : int y;
495 948179 : unsigned x;
496 2016407 : for (x = 0; x < g->edge_list.length (); x += 2)
497 1558493 : if (g->edge_list[x] == node)
498 : {
499 490265 : g->edge_list[x] = -1;
500 490265 : y = g->edge_list[x + 1];
501 490265 : g->edge_list[x + 1] = -1;
502 490265 : *locus = g->edge_locus[x / 2];
503 490265 : g->edge_locus[x / 2] = UNKNOWN_LOCATION;
504 490265 : return y;
505 : }
506 457914 : *locus = UNKNOWN_LOCATION;
507 457914 : 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 998438 : eliminate_name (elim_graph *g, int T)
555 : {
556 998438 : 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 7064287 : queue_phi_copy_p (var_map map, tree t)
566 : {
567 7064287 : if (TREE_CODE (t) == SSA_NAME)
568 : {
569 5783640 : if (var_to_partition (map, t) == NO_PARTITION)
570 : return true;
571 5783640 : return false;
572 : }
573 1280647 : 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 3748180 : eliminate_build (elim_graph *g)
582 : {
583 3748180 : tree Ti;
584 3748180 : int p0, pi;
585 3748180 : gphi_iterator gsi;
586 :
587 3748180 : clear_elim_graph (g);
588 :
589 10812467 : for (gsi = gsi_start_phis (g->e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
590 : {
591 7064287 : gphi *phi = gsi.phi ();
592 7064287 : location_t locus;
593 :
594 7064287 : p0 = var_to_partition (g->map, gimple_phi_result (phi));
595 : /* Ignore results which are not in partitions. */
596 7064287 : if (p0 == NO_PARTITION)
597 0 : continue;
598 :
599 7064287 : Ti = PHI_ARG_DEF (phi, g->e->dest_idx);
600 : /* See set_location_for_edge for the rationale. */
601 7064287 : if (g->e->flags & EDGE_EH)
602 : locus = UNKNOWN_LOCATION;
603 : else
604 7018551 : 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 7064287 : 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 1280647 : g->const_dests.safe_push (p0);
614 1280647 : g->const_copies.safe_push (Ti);
615 1280647 : g->copy_locus.safe_push (locus);
616 : }
617 : else
618 : {
619 5783640 : pi = var_to_partition (g->map, Ti);
620 5783640 : if (p0 != pi)
621 : {
622 499219 : eliminate_name (g, p0);
623 499219 : eliminate_name (g, pi);
624 499219 : elim_graph_add_edge (g, p0, pi, locus);
625 : }
626 : }
627 : }
628 3748180 : }
629 :
630 :
631 : /* Push successors of T onto the elimination stack for G. */
632 :
633 : static void
634 957133 : elim_forward (elim_graph *g, int T)
635 : {
636 957133 : int S;
637 957133 : location_t locus;
638 :
639 957133 : bitmap_set_bit (g->visited, T);
640 3752991 : 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 957133 : g->stack.safe_push (T);
646 957133 : }
647 :
648 :
649 : /* Return 1 if there unvisited predecessors of T in graph G. */
650 :
651 : static int
652 952401 : elim_unvisited_predecessor (elim_graph *g, int T)
653 : {
654 952401 : int P;
655 952401 : location_t locus;
656 :
657 2760004 : 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 8954 : elim_backward (elim_graph *g, int T)
669 : {
670 8954 : int P;
671 8954 : location_t locus;
672 :
673 8954 : bitmap_set_bit (g->visited, T);
674 61234 : 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 8954 : }
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 4222 : get_temp_reg (tree name)
689 : {
690 4222 : tree type = TREE_TYPE (name);
691 4222 : int unsignedp;
692 4222 : machine_mode reg_mode = promote_ssa_mode (name, &unsignedp);
693 4222 : if (reg_mode == BLKmode)
694 1 : return assign_temp (type, 0, 0);
695 4221 : rtx x = gen_reg_rtx (reg_mode);
696 4221 : if (POINTER_TYPE_P (type))
697 788 : 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 952401 : elim_create (elim_graph *g, int T)
706 : {
707 952401 : int P, S;
708 952401 : location_t locus;
709 :
710 952401 : if (elim_unvisited_predecessor (g, T))
711 : {
712 4222 : tree var = partition_to_var (g->map, T);
713 4222 : rtx U = get_temp_reg (var);
714 4222 : int unsignedsrcp = TYPE_UNSIGNED (TREE_TYPE (var));
715 :
716 4222 : insert_part_to_rtx_on_edge (g->e, U, T, UNKNOWN_LOCATION);
717 27870 : 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 948179 : S = elim_graph_remove_succ_edge (g, T, &locus);
729 948179 : if (S != -1)
730 : {
731 490265 : bitmap_set_bit (g->visited, T);
732 490265 : insert_partition_copy_on_edge (g->e, T, S, locus);
733 : }
734 : }
735 952401 : }
736 :
737 :
738 : /* Eliminate all the phi nodes on edge E in graph G. */
739 :
740 : static void
741 3752624 : eliminate_phi (edge e, elim_graph *g)
742 : {
743 3752624 : int x;
744 :
745 3752624 : gcc_assert (g->const_copies.length () == 0);
746 3752624 : gcc_assert (g->copy_locus.length () == 0);
747 :
748 : /* Abnormal edges already have everything coalesced. */
749 3752624 : if (e->flags & EDGE_ABNORMAL)
750 : return;
751 :
752 3748180 : g->e = e;
753 :
754 3748180 : eliminate_build (g);
755 :
756 3748180 : if (elim_graph_size (g) != 0)
757 : {
758 382932 : int part;
759 :
760 382932 : bitmap_clear (g->visited);
761 382932 : g->stack.truncate (0);
762 :
763 1722997 : FOR_EACH_VEC_ELT (g->nodes, x, part)
764 : {
765 957133 : if (!bitmap_bit_p (g->visited, part))
766 488697 : elim_forward (g, part);
767 : }
768 :
769 382932 : bitmap_clear (g->visited);
770 5088245 : while (g->stack.length () > 0)
771 : {
772 957133 : x = g->stack.pop ();
773 957133 : if (!bitmap_bit_p (g->visited, x))
774 952401 : elim_create (g, x);
775 : }
776 : }
777 :
778 : /* If there are any pending constant copies, issue them now. */
779 5028827 : while (g->const_copies.length () > 0)
780 : {
781 1280647 : int dest;
782 1280647 : tree src;
783 1280647 : location_t locus;
784 :
785 1280647 : src = g->const_copies.pop ();
786 1280647 : dest = g->const_dests.pop ();
787 1280647 : locus = g->copy_locus.pop ();
788 1280647 : 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 243 : remove_gimple_phi_args (gphi *phi)
798 : {
799 243 : use_operand_p arg_p;
800 243 : ssa_op_iter iter;
801 :
802 243 : 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 732 : FOR_EACH_PHI_ARG (arg_p, phi, iter, SSA_OP_USE)
809 : {
810 489 : tree arg = USE_FROM_PTR (arg_p);
811 489 : if (TREE_CODE (arg) == SSA_NAME)
812 : {
813 : /* Remove the reference to the existing argument. */
814 331 : SET_USE (arg_p, NULL_TREE);
815 331 : if (has_zero_uses (arg))
816 : {
817 221 : gimple *stmt;
818 221 : gimple_stmt_iterator gsi;
819 :
820 221 : stmt = SSA_NAME_DEF_STMT (arg);
821 :
822 : /* Also remove the def if it is a PHI node. */
823 221 : 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 243 : }
834 :
835 : /* Remove any PHI node which is a virtual PHI, or a PHI with no uses. */
836 :
837 : static void
838 1515899 : eliminate_useless_phis (void)
839 : {
840 1515899 : basic_block bb;
841 1515899 : gphi_iterator gsi;
842 1515899 : tree result;
843 :
844 14416832 : FOR_EACH_BB_FN (bb, cfun)
845 : {
846 18523235 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
847 : {
848 5622302 : gphi *phi = gsi.phi ();
849 5622302 : result = gimple_phi_result (phi);
850 11244604 : if (virtual_operand_p (result))
851 2665749 : remove_phi_node (&gsi, true);
852 : else
853 : {
854 : /* Also remove real PHIs with no uses. */
855 2956553 : if (has_zero_uses (result))
856 : {
857 240 : remove_gimple_phi_args (phi);
858 240 : remove_phi_node (&gsi, true);
859 : }
860 : else
861 2956313 : gsi_next (&gsi);
862 : }
863 : }
864 : }
865 1515899 : }
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 1515899 : rewrite_trees (var_map map)
876 : {
877 1515899 : if (!flag_checking)
878 : return;
879 :
880 1515879 : 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 14416733 : FOR_EACH_BB_FN (bb, cfun)
885 : {
886 12900854 : gphi_iterator gsi;
887 15857141 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
888 : {
889 2956287 : gphi *phi = gsi.phi ();
890 2956287 : tree T0 = var_to_partition_to_var (map, gimple_phi_result (phi));
891 2956287 : 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 3991846 : create_default_def (tree var, void *arg ATTRIBUTE_UNUSED)
917 : {
918 3991846 : if (!is_gimple_reg (var))
919 : return;
920 :
921 3683352 : tree ssa = get_or_create_ssa_default_def (cfun, var);
922 3683352 : 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 3031798 : for_all_parms (void (*callback)(tree var, void *arg), void *arg)
930 : {
931 9367552 : for (tree var = DECL_ARGUMENTS (current_function_decl); var;
932 6335754 : var = DECL_CHAIN (var))
933 6335754 : callback (var, arg);
934 3031798 : if (!VOID_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
935 1609024 : callback (DECL_RESULT (current_function_decl), arg);
936 3031798 : if (cfun->static_chain_decl)
937 38914 : callback (cfun->static_chain_decl, arg);
938 3031798 : }
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 3991846 : set_parm_default_def_partition (tree var, void *arg_)
950 : {
951 3991846 : parm_default_def_partition_arg *arg = (parm_default_def_partition_arg *)arg_;
952 3991846 : var_map map = arg->first;
953 3991846 : bitmap parts = arg->second;
954 :
955 3991846 : if (!is_gimple_reg (var))
956 : return;
957 :
958 3683352 : tree ssa = ssa_default_def (cfun, var);
959 3683352 : gcc_assert (ssa);
960 :
961 3683352 : int version = var_to_partition (map, ssa);
962 3683352 : gcc_assert (version != NO_PARTITION);
963 :
964 3683352 : bool changed = bitmap_set_bit (parts, version);
965 3683352 : 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 1515899 : get_parm_default_def_partitions (var_map map)
973 : {
974 1515899 : bitmap parm_default_def_parts = BITMAP_ALLOC (NULL);
975 :
976 1515899 : parm_default_def_partition_arg
977 1515899 : arg = std::make_pair (map, parm_default_def_parts);
978 :
979 1515899 : for_all_parms (set_parm_default_def_partition, &arg);
980 :
981 1515899 : 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 1515899 : get_undefined_value_partitions (var_map map)
989 : {
990 1515899 : bitmap undefined_value_parts = BITMAP_ALLOC (NULL);
991 :
992 76635271 : for (unsigned int i = 1; i < num_ssa_names; i++)
993 : {
994 73603473 : tree var = ssa_name (i);
995 73603473 : if (var
996 49915066 : && !virtual_operand_p (var)
997 32394458 : && !has_zero_uses (var)
998 103714403 : && ssa_undefined_value_p (var))
999 : {
1000 71036 : const int p = var_to_partition (map, var);
1001 71036 : if (p != NO_PARTITION)
1002 71036 : bitmap_set_bit (undefined_value_parts, p);
1003 : }
1004 : }
1005 :
1006 1515899 : 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 1515899 : expand_phi_nodes (struct ssaexpand *sa)
1015 : {
1016 1515899 : basic_block bb;
1017 1515899 : elim_graph g (sa->map);
1018 :
1019 14416837 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb,
1020 : EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
1021 12900938 : if (!gimple_seq_empty_p (phi_nodes (bb)))
1022 : {
1023 1608169 : edge e;
1024 1608169 : edge_iterator ei;
1025 5360793 : FOR_EACH_EDGE (e, ei, bb->preds)
1026 3752624 : 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 5364027 : for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
1037 : {
1038 1242774 : if (e->insns.r && (e->flags & EDGE_EH)
1039 3759092 : && !single_pred_p (e->dest))
1040 : {
1041 3234 : rtx_insn *insns = e->insns.r;
1042 3234 : basic_block bb;
1043 3234 : e->insns.r = NULL;
1044 3234 : bb = split_edge (e);
1045 3234 : single_pred_edge (bb)->insns.r = insns;
1046 : }
1047 : else
1048 3752624 : ei_next (&ei);
1049 : }
1050 : }
1051 1515899 : }
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 1515899 : split_overlapping_partition_decls (var_map map)
1071 : {
1072 1515899 : unsigned n = num_var_partitions (map);
1073 1515899 : hash_set<tree> seen;
1074 1515899 : auto_vec<tree> new_decl;
1075 1515899 : new_decl.safe_grow_cleared (n);
1076 1515899 : bool any = false;
1077 1515899 : unsigned ver;
1078 1515899 : 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 1515899 : auto_vec<tree> part_var;
1086 1515899 : part_var.safe_grow_cleared (n);
1087 76635271 : FOR_EACH_SSA_NAME (ver, name, cfun)
1088 : {
1089 49915066 : int p = var_to_partition (map, name);
1090 49915066 : if (p == NO_PARTITION)
1091 17774266 : continue;
1092 32140800 : tree var = SSA_NAME_VAR (name);
1093 32140800 : if (!var)
1094 21524961 : continue;
1095 10615839 : part_var[p] = expand_leader_merge (part_var[p], var);
1096 : }
1097 :
1098 28152753 : for (unsigned i = 0; i < n; i++)
1099 : {
1100 26636854 : tree repr = partition_to_var (map, i);
1101 26636854 : if (!repr)
1102 26636602 : 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 26636854 : tree var = SSA_NAME_VAR (repr);
1112 26636854 : if (part_var[i])
1113 7743827 : var = expand_leader_merge (var, part_var[i]);
1114 26636854 : if (!var)
1115 18893027 : 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 7743827 : if (use_register_for_decl (repr))
1120 6501232 : 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 1242595 : tree ddef = ssa_default_def (cfun, var);
1126 1242595 : int keep = ddef ? var_to_partition (map, ddef) : NO_PARTITION;
1127 801170 : if (keep == NO_PARTITION)
1128 : {
1129 441475 : if (!seen.add (var))
1130 441433 : continue;
1131 : }
1132 801120 : else if (keep >= 0 && (unsigned) keep == i)
1133 800910 : continue;
1134 :
1135 252 : 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 252 : if (use_register_for_decl (nvar))
1139 180 : DECL_IGNORED_P (nvar) = DECL_IGNORED_P (var);
1140 252 : gcc_checking_assert (!use_register_for_decl (nvar));
1141 252 : DECL_CONTEXT (nvar) = DECL_CONTEXT (var);
1142 252 : DECL_SOURCE_LOCATION (nvar) = DECL_SOURCE_LOCATION (var);
1143 252 : SET_DECL_ALIGN (nvar, DECL_ALIGN (var));
1144 252 : 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 252 : copy_warning (nvar, var);
1150 252 : add_local_decl (cfun, nvar);
1151 252 : new_decl[i] = nvar;
1152 252 : any = true;
1153 : }
1154 :
1155 1515899 : if (!any)
1156 1515714 : return;
1157 :
1158 10200 : FOR_EACH_SSA_NAME (ver, name, cfun)
1159 : {
1160 8499 : if (SSA_NAME_IS_DEFAULT_DEF (name))
1161 942 : continue;
1162 7557 : int p = var_to_partition (map, name);
1163 7557 : if (p != NO_PARTITION && new_decl[p])
1164 642 : SET_SSA_NAME_VAR_OR_IDENTIFIER (name, new_decl[p]);
1165 : }
1166 1515899 : }
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 1515899 : remove_ssa_form (bool perform_ter, struct ssaexpand *sa)
1174 : {
1175 1515899 : bitmap values = NULL;
1176 1515899 : var_map map;
1177 :
1178 1515899 : for_all_parms (create_default_def, NULL);
1179 3031798 : map = init_var_map (num_ssa_names);
1180 1515899 : coalesce_ssa_name (map);
1181 :
1182 : /* Return to viewing the variable list as just all reference variables after
1183 : coalescing has been performed. */
1184 1515899 : partition_view_normal (map);
1185 :
1186 1515899 : if (dump_file && (dump_flags & TDF_DETAILS))
1187 : {
1188 111 : fprintf (dump_file, "After Coalescing:\n");
1189 111 : dump_var_map (dump_file, map);
1190 : }
1191 :
1192 1515899 : if (perform_ter)
1193 : {
1194 1062651 : values = find_replaceable_exprs (map);
1195 1062651 : 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 1515899 : split_overlapping_partition_decls (map);
1203 :
1204 1515899 : rewrite_trees (map);
1205 :
1206 1515899 : sa->map = map;
1207 1515899 : sa->values = values;
1208 1515899 : sa->partitions_for_parm_default_defs = get_parm_default_def_partitions (map);
1209 1515899 : sa->partitions_for_undefined_values = get_undefined_value_partitions (map);
1210 1515899 : }
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 980610 : maybe_renumber_stmts_bb (basic_block bb)
1218 : {
1219 980610 : unsigned i = 0;
1220 980610 : gimple_stmt_iterator gsi;
1221 :
1222 980610 : if (!bb->aux)
1223 980610 : return;
1224 280579 : bb->aux = NULL;
1225 4084139 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1226 : {
1227 3522981 : gimple *stmt = gsi_stmt (gsi);
1228 3522981 : gimple_set_uid (stmt, i);
1229 3522981 : 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 1278609 : trivially_conflicts_p (basic_block bb, tree result, tree arg)
1240 : {
1241 1278609 : use_operand_p use;
1242 1278609 : imm_use_iterator imm_iter;
1243 1278609 : 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 1278609 : if (gimple_bb (defa) != bb)
1248 : return false;
1249 :
1250 1438536 : FOR_EACH_IMM_USE_FAST (use, imm_iter, result)
1251 : {
1252 1017627 : gimple *use_stmt = USE_STMT (use);
1253 1017627 : if (is_gimple_debug (use_stmt))
1254 130149 : 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 887478 : if (gimple_bb (use_stmt) != bb)
1258 : return true;
1259 836767 : if (gimple_code (use_stmt) == GIMPLE_PHI)
1260 844 : 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 835923 : if (gimple_code (defa) == GIMPLE_PHI)
1264 : return true;
1265 833831 : maybe_renumber_stmts_bb (bb);
1266 : /* If the use of RESULT occurs after the definition of ARG,
1267 : the two conflict too. */
1268 833831 : if (gimple_uid (defa) < gimple_uid (use_stmt))
1269 : return true;
1270 68927 : }
1271 :
1272 420909 : 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 1515899 : insert_backedge_copies (void)
1287 : {
1288 1515899 : basic_block bb;
1289 1515899 : gphi_iterator gsi;
1290 :
1291 1515899 : mark_dfs_back_edges ();
1292 :
1293 14416832 : FOR_EACH_BB_FN (bb, cfun)
1294 : {
1295 : /* Mark block as possibly needing calculation of UIDs. */
1296 12900933 : bb->aux = &bb->aux;
1297 :
1298 18523236 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1299 : {
1300 5622303 : gphi *phi = gsi.phi ();
1301 5622303 : tree result = gimple_phi_result (phi);
1302 5622303 : size_t i;
1303 :
1304 11244606 : if (virtual_operand_p (result))
1305 2665749 : continue;
1306 :
1307 10215901 : for (i = 0; i < gimple_phi_num_args (phi); i++)
1308 : {
1309 7259347 : tree arg = gimple_phi_arg_def (phi, i);
1310 7259347 : edge e = gimple_phi_arg_edge (phi, i);
1311 : /* We are only interested in copies emitted on critical
1312 : backedges. */
1313 13386105 : if (!(e->flags & EDGE_DFS_BACK)
1314 7259347 : || !EDGE_CRITICAL_P (e))
1315 6126758 : 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 1132589 : if (TREE_CODE (arg) != SSA_NAME
1322 1132589 : || (gimple_code (SSA_NAME_DEF_STMT (arg)) == GIMPLE_PHI
1323 195098 : && trivially_conflicts_p (bb, result, arg)))
1324 : {
1325 49078 : tree name;
1326 49078 : gassign *stmt;
1327 49078 : gimple *last = NULL;
1328 49078 : gimple_stmt_iterator gsi2;
1329 :
1330 49078 : gsi2 = gsi_last_bb (gimple_phi_arg_edge (phi, i)->src);
1331 49078 : if (!gsi_end_p (gsi2))
1332 49078 : 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 49078 : 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 49078 : if (TREE_CODE (arg) == SSA_NAME
1347 49078 : && 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 49078 : name = copy_ssa_name (result);
1354 49078 : stmt = gimple_build_assign (name,
1355 : gimple_phi_arg_def (phi, i));
1356 :
1357 : /* copy location if present. */
1358 49078 : if (gimple_phi_arg_has_location (phi, i))
1359 5199 : 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 49078 : if (last && stmt_ends_bb_p (last))
1365 49078 : gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT);
1366 : else
1367 0 : gsi_insert_after (&gsi2, stmt, GSI_NEW_STMT);
1368 49078 : 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 1083511 : else if (trivially_conflicts_p (bb, result, arg))
1373 : {
1374 32740 : gimple *def = SSA_NAME_DEF_STMT (arg);
1375 32740 : if (gimple_nop_p (def)
1376 32740 : || gimple_code (def) == GIMPLE_PHI)
1377 0 : continue;
1378 32740 : imm_use_iterator imm_iter;
1379 32740 : gimple *use_stmt;
1380 32740 : auto_vec<use_operand_p, 8> uses;
1381 32740 : int idx = -1;
1382 : /* The following matches trivially_conflicts_p. */
1383 231297 : FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, result)
1384 : {
1385 198557 : if (gimple_bb (use_stmt) != bb
1386 198557 : || (gimple_code (use_stmt) != GIMPLE_PHI
1387 146779 : && (maybe_renumber_stmts_bb (bb), true)
1388 146779 : && gimple_uid (use_stmt) > gimple_uid (def)))
1389 : {
1390 116907 : use_operand_p use;
1391 234242 : FOR_EACH_IMM_USE_ON_STMT (use, imm_iter)
1392 : {
1393 117121 : uses.safe_push (use);
1394 117121 : if (!is_gimple_debug (use_stmt))
1395 : {
1396 54696 : if (idx == -1)
1397 65480 : idx = uses.length () - 1;
1398 : else
1399 : idx = -2;
1400 : }
1401 : }
1402 : }
1403 32740 : }
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 32740 : if (idx >= 0
1411 23913 : && is_a <gcond *> (USE_STMT (uses[idx]))
1412 7935 : && (gimple_cond_code (USE_STMT (uses[idx])) == NE_EXPR
1413 2242 : || gimple_cond_code (USE_STMT (uses[idx])) == EQ_EXPR)
1414 6887 : && is_gimple_assign (def)
1415 6833 : && gimple_assign_rhs1 (def) == result
1416 4160 : && (gimple_assign_rhs_code (def) == PLUS_EXPR
1417 24 : || gimple_assign_rhs_code (def) == MINUS_EXPR
1418 24 : || gimple_assign_rhs_code (def) == POINTER_PLUS_EXPR)
1419 36881 : && TREE_CODE (gimple_assign_rhs2 (def)) == INTEGER_CST)
1420 : {
1421 4141 : gcond *cond = as_a <gcond *> (USE_STMT (uses[idx]));
1422 4141 : tree *adj;
1423 4141 : if (gimple_cond_lhs (cond) == result)
1424 2314 : adj = gimple_cond_rhs_ptr (cond);
1425 : else
1426 1827 : adj = gimple_cond_lhs_ptr (cond);
1427 4141 : gimple_stmt_iterator gsi = gsi_for_stmt (cond);
1428 4141 : tree newval
1429 8282 : = gimple_build (&gsi, true, GSI_SAME_STMT,
1430 : UNKNOWN_LOCATION,
1431 : gimple_assign_rhs_code (def),
1432 4141 : TREE_TYPE (*adj),
1433 : *adj, gimple_assign_rhs2 (def));
1434 4141 : *adj = newval;
1435 4141 : SET_USE (uses[idx], arg);
1436 4141 : update_stmt (cond);
1437 : }
1438 : else
1439 : {
1440 28599 : tree name = copy_ssa_name (result);
1441 28599 : gimple *stmt = gimple_build_assign (name, result);
1442 28599 : gimple_stmt_iterator gsi = gsi_for_stmt (def);
1443 28599 : gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1444 198740 : for (auto use : uses)
1445 112943 : SET_USE (use, name);
1446 : }
1447 32740 : }
1448 : }
1449 : }
1450 :
1451 : /* Unmark this block again. */
1452 12900933 : bb->aux = NULL;
1453 : }
1454 1515899 : }
1455 :
1456 : /* Remove indirect clobbers. */
1457 :
1458 : static void
1459 1515899 : remove_indirect_clobbers (void)
1460 : {
1461 1515899 : basic_block bb;
1462 :
1463 14416832 : FOR_EACH_BB_FN (bb, cfun)
1464 127616531 : for (auto gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
1465 : {
1466 101814665 : gimple *stmt = gsi_stmt (gsi);
1467 101814665 : if (gimple_clobber_p (stmt))
1468 : {
1469 1519788 : tree lhs = gimple_assign_lhs (stmt);
1470 1636459 : if (TREE_CODE (lhs) == MEM_REF
1471 1519788 : && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME)
1472 : {
1473 116671 : unlink_stmt_vdef (stmt);
1474 116671 : gsi_remove (&gsi, true);
1475 116671 : release_defs (stmt);
1476 116671 : continue;
1477 : }
1478 : }
1479 101697994 : gsi_next (&gsi);
1480 : }
1481 1515899 : }
1482 :
1483 : /* Free all memory associated with going out of SSA form. SA is
1484 : the outof-SSA info object. */
1485 :
1486 : void
1487 1515897 : finish_out_of_ssa (struct ssaexpand *sa)
1488 : {
1489 1515897 : free (sa->partition_to_pseudo);
1490 1515897 : if (sa->values)
1491 672951 : BITMAP_FREE (sa->values);
1492 1515897 : delete_var_map (sa->map);
1493 1515897 : BITMAP_FREE (sa->partitions_for_parm_default_defs);
1494 1515897 : BITMAP_FREE (sa->partitions_for_undefined_values);
1495 1515897 : memset (sa, 0, sizeof *sa);
1496 1515897 : }
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 1515899 : 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 1515899 : 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 1515899 : insert_backedge_copies ();
1516 :
1517 : /* Eliminate PHIs which are of no use, such as virtual or dead phis. */
1518 1515899 : eliminate_useless_phis ();
1519 :
1520 1515899 : if (dump_file && (dump_flags & TDF_DETAILS))
1521 111 : gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
1522 :
1523 1515899 : remove_ssa_form (flag_tree_ter, sa);
1524 :
1525 1515899 : return 0;
1526 : }
|
