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