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