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