* de.po: Update.
[official-gcc.git] / gcc / tree-outof-ssa.c
blobff3e058a9784ce6e3a40e1a8c1a7b4b59fc181ba
1 /* Convert a program in SSA form into Normal form.
2 Copyright (C) 2004-2013 Free Software Foundation, Inc.
3 Contributed by Andrew Macleod <amacleod@redhat.com>
5 This file is part of GCC.
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.
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.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "ggc.h"
27 #include "basic-block.h"
28 #include "gimple-pretty-print.h"
29 #include "bitmap.h"
30 #include "tree-flow.h"
31 #include "dumpfile.h"
32 #include "diagnostic-core.h"
33 #include "ssaexpand.h"
35 /* FIXME: A lot of code here deals with expanding to RTL. All that code
36 should be in cfgexpand.c. */
37 #include "expr.h"
41 /* Used to hold all the components required to do SSA PHI elimination.
42 The node and pred/succ list is a simple linear list of nodes and
43 edges represented as pairs of nodes.
45 The predecessor and successor list: Nodes are entered in pairs, where
46 [0] ->PRED, [1]->SUCC. All the even indexes in the array represent
47 predecessors, all the odd elements are successors.
49 Rationale:
50 When implemented as bitmaps, very large programs SSA->Normal times were
51 being dominated by clearing the interference graph.
53 Typically this list of edges is extremely small since it only includes
54 PHI results and uses from a single edge which have not coalesced with
55 each other. This means that no virtual PHI nodes are included, and
56 empirical evidence suggests that the number of edges rarely exceed
57 3, and in a bootstrap of GCC, the maximum size encountered was 7.
58 This also limits the number of possible nodes that are involved to
59 rarely more than 6, and in the bootstrap of gcc, the maximum number
60 of nodes encountered was 12. */
62 typedef struct _elim_graph {
63 /* Size of the elimination vectors. */
64 int size;
66 /* List of nodes in the elimination graph. */
67 vec<int> nodes;
69 /* The predecessor and successor edge list. */
70 vec<int> edge_list;
72 /* Source locus on each edge */
73 vec<source_location> edge_locus;
75 /* Visited vector. */
76 sbitmap visited;
78 /* Stack for visited nodes. */
79 vec<int> stack;
81 /* The variable partition map. */
82 var_map map;
84 /* Edge being eliminated by this graph. */
85 edge e;
87 /* List of constant copies to emit. These are pushed on in pairs. */
88 vec<int> const_dests;
89 vec<tree> const_copies;
91 /* Source locations for any constant copies. */
92 vec<source_location> copy_locus;
93 } *elim_graph;
96 /* For an edge E find out a good source location to associate with
97 instructions inserted on edge E. If E has an implicit goto set,
98 use its location. Otherwise search instructions in predecessors
99 of E for a location, and use that one. That makes sense because
100 we insert on edges for PHI nodes, and effects of PHIs happen on
101 the end of the predecessor conceptually. */
103 static void
104 set_location_for_edge (edge e)
106 if (e->goto_locus)
108 set_curr_insn_location (e->goto_locus);
110 else
112 basic_block bb = e->src;
113 gimple_stmt_iterator gsi;
117 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
119 gimple stmt = gsi_stmt (gsi);
120 if (is_gimple_debug (stmt))
121 continue;
122 if (gimple_has_location (stmt) || gimple_block (stmt))
124 set_curr_insn_location (gimple_location (stmt));
125 return;
128 /* Nothing found in this basic block. Make a half-assed attempt
129 to continue with another block. */
130 if (single_pred_p (bb))
131 bb = single_pred (bb);
132 else
133 bb = e->src;
135 while (bb != e->src);
139 /* Emit insns to copy SRC into DEST converting SRC if necessary. As
140 SRC/DEST might be BLKmode memory locations SIZEEXP is a tree from
141 which we deduce the size to copy in that case. */
143 static inline rtx
144 emit_partition_copy (rtx dest, rtx src, int unsignedsrcp, tree sizeexp)
146 rtx seq;
148 start_sequence ();
150 if (GET_MODE (src) != VOIDmode && GET_MODE (src) != GET_MODE (dest))
151 src = convert_to_mode (GET_MODE (dest), src, unsignedsrcp);
152 if (GET_MODE (src) == BLKmode)
154 gcc_assert (GET_MODE (dest) == BLKmode);
155 emit_block_move (dest, src, expr_size (sizeexp), BLOCK_OP_NORMAL);
157 else
158 emit_move_insn (dest, src);
160 seq = get_insns ();
161 end_sequence ();
163 return seq;
166 /* Insert a copy instruction from partition SRC to DEST onto edge E. */
168 static void
169 insert_partition_copy_on_edge (edge e, int dest, int src, source_location locus)
171 tree var;
172 rtx seq;
173 if (dump_file && (dump_flags & TDF_DETAILS))
175 fprintf (dump_file,
176 "Inserting a partition copy on edge BB%d->BB%d :"
177 "PART.%d = PART.%d",
178 e->src->index,
179 e->dest->index, dest, src);
180 fprintf (dump_file, "\n");
183 gcc_assert (SA.partition_to_pseudo[dest]);
184 gcc_assert (SA.partition_to_pseudo[src]);
186 set_location_for_edge (e);
187 /* If a locus is provided, override the default. */
188 if (locus)
189 set_curr_insn_location (locus);
191 var = partition_to_var (SA.map, src);
192 seq = emit_partition_copy (SA.partition_to_pseudo[dest],
193 SA.partition_to_pseudo[src],
194 TYPE_UNSIGNED (TREE_TYPE (var)),
195 var);
197 insert_insn_on_edge (seq, e);
200 /* Insert a copy instruction from expression SRC to partition DEST
201 onto edge E. */
203 static void
204 insert_value_copy_on_edge (edge e, int dest, tree src, source_location locus)
206 rtx seq, x;
207 enum machine_mode dest_mode, src_mode;
208 int unsignedp;
209 tree var;
211 if (dump_file && (dump_flags & TDF_DETAILS))
213 fprintf (dump_file,
214 "Inserting a value copy on edge BB%d->BB%d : PART.%d = ",
215 e->src->index,
216 e->dest->index, dest);
217 print_generic_expr (dump_file, src, TDF_SLIM);
218 fprintf (dump_file, "\n");
221 gcc_assert (SA.partition_to_pseudo[dest]);
223 set_location_for_edge (e);
224 /* If a locus is provided, override the default. */
225 if (locus)
226 set_curr_insn_location (locus);
228 start_sequence ();
230 var = SSA_NAME_VAR (partition_to_var (SA.map, dest));
231 src_mode = TYPE_MODE (TREE_TYPE (src));
232 dest_mode = GET_MODE (SA.partition_to_pseudo[dest]);
233 gcc_assert (src_mode == TYPE_MODE (TREE_TYPE (var)));
234 gcc_assert (!REG_P (SA.partition_to_pseudo[dest])
235 || dest_mode == promote_decl_mode (var, &unsignedp));
237 if (src_mode != dest_mode)
239 x = expand_expr (src, NULL, src_mode, EXPAND_NORMAL);
240 x = convert_modes (dest_mode, src_mode, x, unsignedp);
242 else if (src_mode == BLKmode)
244 x = SA.partition_to_pseudo[dest];
245 store_expr (src, x, 0, false);
247 else
248 x = expand_expr (src, SA.partition_to_pseudo[dest],
249 dest_mode, EXPAND_NORMAL);
251 if (x != SA.partition_to_pseudo[dest])
252 emit_move_insn (SA.partition_to_pseudo[dest], x);
253 seq = get_insns ();
254 end_sequence ();
256 insert_insn_on_edge (seq, e);
259 /* Insert a copy instruction from RTL expression SRC to partition DEST
260 onto edge E. */
262 static void
263 insert_rtx_to_part_on_edge (edge e, int dest, rtx src, int unsignedsrcp,
264 source_location locus)
266 rtx seq;
267 if (dump_file && (dump_flags & TDF_DETAILS))
269 fprintf (dump_file,
270 "Inserting a temp copy on edge BB%d->BB%d : PART.%d = ",
271 e->src->index,
272 e->dest->index, dest);
273 print_simple_rtl (dump_file, src);
274 fprintf (dump_file, "\n");
277 gcc_assert (SA.partition_to_pseudo[dest]);
279 set_location_for_edge (e);
280 /* If a locus is provided, override the default. */
281 if (locus)
282 set_curr_insn_location (locus);
284 /* We give the destination as sizeexp in case src/dest are BLKmode
285 mems. Usually we give the source. As we result from SSA names
286 the left and right size should be the same (and no WITH_SIZE_EXPR
287 involved), so it doesn't matter. */
288 seq = emit_partition_copy (SA.partition_to_pseudo[dest],
289 src, unsignedsrcp,
290 partition_to_var (SA.map, dest));
292 insert_insn_on_edge (seq, e);
295 /* Insert a copy instruction from partition SRC to RTL lvalue DEST
296 onto edge E. */
298 static void
299 insert_part_to_rtx_on_edge (edge e, rtx dest, int src, source_location locus)
301 tree var;
302 rtx seq;
303 if (dump_file && (dump_flags & TDF_DETAILS))
305 fprintf (dump_file,
306 "Inserting a temp copy on edge BB%d->BB%d : ",
307 e->src->index,
308 e->dest->index);
309 print_simple_rtl (dump_file, dest);
310 fprintf (dump_file, "= PART.%d\n", src);
313 gcc_assert (SA.partition_to_pseudo[src]);
315 set_location_for_edge (e);
316 /* If a locus is provided, override the default. */
317 if (locus)
318 set_curr_insn_location (locus);
320 var = partition_to_var (SA.map, src);
321 seq = emit_partition_copy (dest,
322 SA.partition_to_pseudo[src],
323 TYPE_UNSIGNED (TREE_TYPE (var)),
324 var);
326 insert_insn_on_edge (seq, e);
330 /* Create an elimination graph with SIZE nodes and associated data
331 structures. */
333 static elim_graph
334 new_elim_graph (int size)
336 elim_graph g = (elim_graph) xmalloc (sizeof (struct _elim_graph));
338 g->nodes.create (30);
339 g->const_dests.create (20);
340 g->const_copies.create (20);
341 g->copy_locus.create (10);
342 g->edge_list.create (20);
343 g->edge_locus.create (10);
344 g->stack.create (30);
346 g->visited = sbitmap_alloc (size);
348 return g;
352 /* Empty elimination graph G. */
354 static inline void
355 clear_elim_graph (elim_graph g)
357 g->nodes.truncate (0);
358 g->edge_list.truncate (0);
359 g->edge_locus.truncate (0);
363 /* Delete elimination graph G. */
365 static inline void
366 delete_elim_graph (elim_graph g)
368 sbitmap_free (g->visited);
369 g->stack.release ();
370 g->edge_list.release ();
371 g->const_copies.release ();
372 g->const_dests.release ();
373 g->nodes.release ();
374 g->copy_locus.release ();
375 g->edge_locus.release ();
377 free (g);
381 /* Return the number of nodes in graph G. */
383 static inline int
384 elim_graph_size (elim_graph g)
386 return g->nodes.length ();
390 /* Add NODE to graph G, if it doesn't exist already. */
392 static inline void
393 elim_graph_add_node (elim_graph g, int node)
395 int x;
396 int t;
398 FOR_EACH_VEC_ELT (g->nodes, x, t)
399 if (t == node)
400 return;
401 g->nodes.safe_push (node);
405 /* Add the edge PRED->SUCC to graph G. */
407 static inline void
408 elim_graph_add_edge (elim_graph g, int pred, int succ, source_location locus)
410 g->edge_list.safe_push (pred);
411 g->edge_list.safe_push (succ);
412 g->edge_locus.safe_push (locus);
416 /* Remove an edge from graph G for which NODE is the predecessor, and
417 return the successor node. -1 is returned if there is no such edge. */
419 static inline int
420 elim_graph_remove_succ_edge (elim_graph g, int node, source_location *locus)
422 int y;
423 unsigned x;
424 for (x = 0; x < g->edge_list.length (); x += 2)
425 if (g->edge_list[x] == node)
427 g->edge_list[x] = -1;
428 y = g->edge_list[x + 1];
429 g->edge_list[x + 1] = -1;
430 *locus = g->edge_locus[x / 2];
431 g->edge_locus[x / 2] = UNKNOWN_LOCATION;
432 return y;
434 *locus = UNKNOWN_LOCATION;
435 return -1;
439 /* Find all the nodes in GRAPH which are successors to NODE in the
440 edge list. VAR will hold the partition number found. CODE is the
441 code fragment executed for every node found. */
443 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, LOCUS, CODE) \
444 do { \
445 unsigned x_; \
446 int y_; \
447 for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \
449 y_ = (GRAPH)->edge_list[x_]; \
450 if (y_ != (NODE)) \
451 continue; \
452 (void) ((VAR) = (GRAPH)->edge_list[x_ + 1]); \
453 (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \
454 CODE; \
456 } while (0)
459 /* Find all the nodes which are predecessors of NODE in the edge list for
460 GRAPH. VAR will hold the partition number found. CODE is the
461 code fragment executed for every node found. */
463 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, LOCUS, CODE) \
464 do { \
465 unsigned x_; \
466 int y_; \
467 for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \
469 y_ = (GRAPH)->edge_list[x_ + 1]; \
470 if (y_ != (NODE)) \
471 continue; \
472 (void) ((VAR) = (GRAPH)->edge_list[x_]); \
473 (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \
474 CODE; \
476 } while (0)
479 /* Add T to elimination graph G. */
481 static inline void
482 eliminate_name (elim_graph g, int T)
484 elim_graph_add_node (g, T);
488 /* Build elimination graph G for basic block BB on incoming PHI edge
489 G->e. */
491 static void
492 eliminate_build (elim_graph g)
494 tree Ti;
495 int p0, pi;
496 gimple_stmt_iterator gsi;
498 clear_elim_graph (g);
500 for (gsi = gsi_start_phis (g->e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
502 gimple phi = gsi_stmt (gsi);
503 source_location locus;
505 p0 = var_to_partition (g->map, gimple_phi_result (phi));
506 /* Ignore results which are not in partitions. */
507 if (p0 == NO_PARTITION)
508 continue;
510 Ti = PHI_ARG_DEF (phi, g->e->dest_idx);
511 locus = gimple_phi_arg_location_from_edge (phi, g->e);
513 /* If this argument is a constant, or a SSA_NAME which is being
514 left in SSA form, just queue a copy to be emitted on this
515 edge. */
516 if (!phi_ssa_name_p (Ti)
517 || (TREE_CODE (Ti) == SSA_NAME
518 && var_to_partition (g->map, Ti) == NO_PARTITION))
520 /* Save constant copies until all other copies have been emitted
521 on this edge. */
522 g->const_dests.safe_push (p0);
523 g->const_copies.safe_push (Ti);
524 g->copy_locus.safe_push (locus);
526 else
528 pi = var_to_partition (g->map, Ti);
529 if (p0 != pi)
531 eliminate_name (g, p0);
532 eliminate_name (g, pi);
533 elim_graph_add_edge (g, p0, pi, locus);
540 /* Push successors of T onto the elimination stack for G. */
542 static void
543 elim_forward (elim_graph g, int T)
545 int S;
546 source_location locus;
548 bitmap_set_bit (g->visited, T);
549 FOR_EACH_ELIM_GRAPH_SUCC (g, T, S, locus,
551 if (!bitmap_bit_p (g->visited, S))
552 elim_forward (g, S);
554 g->stack.safe_push (T);
558 /* Return 1 if there unvisited predecessors of T in graph G. */
560 static int
561 elim_unvisited_predecessor (elim_graph g, int T)
563 int P;
564 source_location locus;
566 FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus,
568 if (!bitmap_bit_p (g->visited, P))
569 return 1;
571 return 0;
574 /* Process predecessors first, and insert a copy. */
576 static void
577 elim_backward (elim_graph g, int T)
579 int P;
580 source_location locus;
582 bitmap_set_bit (g->visited, T);
583 FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus,
585 if (!bitmap_bit_p (g->visited, P))
587 elim_backward (g, P);
588 insert_partition_copy_on_edge (g->e, P, T, locus);
593 /* Allocate a new pseudo register usable for storing values sitting
594 in NAME (a decl or SSA name), i.e. with matching mode and attributes. */
596 static rtx
597 get_temp_reg (tree name)
599 tree var = TREE_CODE (name) == SSA_NAME ? SSA_NAME_VAR (name) : name;
600 tree type = TREE_TYPE (var);
601 int unsignedp;
602 enum machine_mode reg_mode = promote_decl_mode (var, &unsignedp);
603 rtx x = gen_reg_rtx (reg_mode);
604 if (POINTER_TYPE_P (type))
605 mark_reg_pointer (x, TYPE_ALIGN (TREE_TYPE (TREE_TYPE (var))));
606 return x;
609 /* Insert required copies for T in graph G. Check for a strongly connected
610 region, and create a temporary to break the cycle if one is found. */
612 static void
613 elim_create (elim_graph g, int T)
615 int P, S;
616 source_location locus;
618 if (elim_unvisited_predecessor (g, T))
620 tree var = partition_to_var (g->map, T);
621 rtx U = get_temp_reg (var);
622 int unsignedsrcp = TYPE_UNSIGNED (TREE_TYPE (var));
624 insert_part_to_rtx_on_edge (g->e, U, T, UNKNOWN_LOCATION);
625 FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus,
627 if (!bitmap_bit_p (g->visited, P))
629 elim_backward (g, P);
630 insert_rtx_to_part_on_edge (g->e, P, U, unsignedsrcp, locus);
634 else
636 S = elim_graph_remove_succ_edge (g, T, &locus);
637 if (S != -1)
639 bitmap_set_bit (g->visited, T);
640 insert_partition_copy_on_edge (g->e, T, S, locus);
646 /* Eliminate all the phi nodes on edge E in graph G. */
648 static void
649 eliminate_phi (edge e, elim_graph g)
651 int x;
653 gcc_assert (g->const_copies.length () == 0);
654 gcc_assert (g->copy_locus.length () == 0);
656 /* Abnormal edges already have everything coalesced. */
657 if (e->flags & EDGE_ABNORMAL)
658 return;
660 g->e = e;
662 eliminate_build (g);
664 if (elim_graph_size (g) != 0)
666 int part;
668 bitmap_clear (g->visited);
669 g->stack.truncate (0);
671 FOR_EACH_VEC_ELT (g->nodes, x, part)
673 if (!bitmap_bit_p (g->visited, part))
674 elim_forward (g, part);
677 bitmap_clear (g->visited);
678 while (g->stack.length () > 0)
680 x = g->stack.pop ();
681 if (!bitmap_bit_p (g->visited, x))
682 elim_create (g, x);
686 /* If there are any pending constant copies, issue them now. */
687 while (g->const_copies.length () > 0)
689 int dest;
690 tree src;
691 source_location locus;
693 src = g->const_copies.pop ();
694 dest = g->const_dests.pop ();
695 locus = g->copy_locus.pop ();
696 insert_value_copy_on_edge (e, dest, src, locus);
701 /* Remove each argument from PHI. If an arg was the last use of an SSA_NAME,
702 check to see if this allows another PHI node to be removed. */
704 static void
705 remove_gimple_phi_args (gimple phi)
707 use_operand_p arg_p;
708 ssa_op_iter iter;
710 if (dump_file && (dump_flags & TDF_DETAILS))
712 fprintf (dump_file, "Removing Dead PHI definition: ");
713 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
716 FOR_EACH_PHI_ARG (arg_p, phi, iter, SSA_OP_USE)
718 tree arg = USE_FROM_PTR (arg_p);
719 if (TREE_CODE (arg) == SSA_NAME)
721 /* Remove the reference to the existing argument. */
722 SET_USE (arg_p, NULL_TREE);
723 if (has_zero_uses (arg))
725 gimple stmt;
726 gimple_stmt_iterator gsi;
728 stmt = SSA_NAME_DEF_STMT (arg);
730 /* Also remove the def if it is a PHI node. */
731 if (gimple_code (stmt) == GIMPLE_PHI)
733 remove_gimple_phi_args (stmt);
734 gsi = gsi_for_stmt (stmt);
735 remove_phi_node (&gsi, true);
743 /* Remove any PHI node which is a virtual PHI, or a PHI with no uses. */
745 static void
746 eliminate_useless_phis (void)
748 basic_block bb;
749 gimple_stmt_iterator gsi;
750 tree result;
752 FOR_EACH_BB (bb)
754 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
756 gimple phi = gsi_stmt (gsi);
757 result = gimple_phi_result (phi);
758 if (virtual_operand_p (result))
760 #ifdef ENABLE_CHECKING
761 size_t i;
762 /* There should be no arguments which are not virtual, or the
763 results will be incorrect. */
764 for (i = 0; i < gimple_phi_num_args (phi); i++)
766 tree arg = PHI_ARG_DEF (phi, i);
767 if (TREE_CODE (arg) == SSA_NAME
768 && !virtual_operand_p (arg))
770 fprintf (stderr, "Argument of PHI is not virtual (");
771 print_generic_expr (stderr, arg, TDF_SLIM);
772 fprintf (stderr, "), but the result is :");
773 print_gimple_stmt (stderr, phi, 0, TDF_SLIM);
774 internal_error ("SSA corruption");
777 #endif
778 remove_phi_node (&gsi, true);
780 else
782 /* Also remove real PHIs with no uses. */
783 if (has_zero_uses (result))
785 remove_gimple_phi_args (phi);
786 remove_phi_node (&gsi, true);
788 else
789 gsi_next (&gsi);
796 /* This function will rewrite the current program using the variable mapping
797 found in MAP. If the replacement vector VALUES is provided, any
798 occurrences of partitions with non-null entries in the vector will be
799 replaced with the expression in the vector instead of its mapped
800 variable. */
802 static void
803 rewrite_trees (var_map map ATTRIBUTE_UNUSED)
805 #ifdef ENABLE_CHECKING
806 basic_block bb;
807 /* Search for PHIs where the destination has no partition, but one
808 or more arguments has a partition. This should not happen and can
809 create incorrect code. */
810 FOR_EACH_BB (bb)
812 gimple_stmt_iterator gsi;
813 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
815 gimple phi = gsi_stmt (gsi);
816 tree T0 = var_to_partition_to_var (map, gimple_phi_result (phi));
817 if (T0 == NULL_TREE)
819 size_t i;
820 for (i = 0; i < gimple_phi_num_args (phi); i++)
822 tree arg = PHI_ARG_DEF (phi, i);
824 if (TREE_CODE (arg) == SSA_NAME
825 && var_to_partition (map, arg) != NO_PARTITION)
827 fprintf (stderr, "Argument of PHI is in a partition :(");
828 print_generic_expr (stderr, arg, TDF_SLIM);
829 fprintf (stderr, "), but the result is not :");
830 print_gimple_stmt (stderr, phi, 0, TDF_SLIM);
831 internal_error ("SSA corruption");
837 #endif
840 /* Given the out-of-ssa info object SA (with prepared partitions)
841 eliminate all phi nodes in all basic blocks. Afterwards no
842 basic block will have phi nodes anymore and there are possibly
843 some RTL instructions inserted on edges. */
845 void
846 expand_phi_nodes (struct ssaexpand *sa)
848 basic_block bb;
849 elim_graph g = new_elim_graph (sa->map->num_partitions);
850 g->map = sa->map;
852 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR, next_bb)
853 if (!gimple_seq_empty_p (phi_nodes (bb)))
855 edge e;
856 edge_iterator ei;
857 FOR_EACH_EDGE (e, ei, bb->preds)
858 eliminate_phi (e, g);
859 set_phi_nodes (bb, NULL);
860 /* We can't redirect EH edges in RTL land, so we need to do this
861 here. Redirection happens only when splitting is necessary,
862 which it is only for critical edges, normally. For EH edges
863 it might also be necessary when the successor has more than
864 one predecessor. In that case the edge is either required to
865 be fallthru (which EH edges aren't), or the predecessor needs
866 to end with a jump (which again, isn't the case with EH edges).
867 Hence, split all EH edges on which we inserted instructions
868 and whose successor has multiple predecessors. */
869 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
871 if (e->insns.r && (e->flags & EDGE_EH)
872 && !single_pred_p (e->dest))
874 rtx insns = e->insns.r;
875 basic_block bb;
876 e->insns.r = NULL_RTX;
877 bb = split_edge (e);
878 single_pred_edge (bb)->insns.r = insns;
880 else
881 ei_next (&ei);
885 delete_elim_graph (g);
889 /* Remove the ssa-names in the current function and translate them into normal
890 compiler variables. PERFORM_TER is true if Temporary Expression Replacement
891 should also be used. */
893 static void
894 remove_ssa_form (bool perform_ter, struct ssaexpand *sa)
896 bitmap values = NULL;
897 var_map map;
898 unsigned i;
900 map = coalesce_ssa_name ();
902 /* Return to viewing the variable list as just all reference variables after
903 coalescing has been performed. */
904 partition_view_normal (map, false);
906 if (dump_file && (dump_flags & TDF_DETAILS))
908 fprintf (dump_file, "After Coalescing:\n");
909 dump_var_map (dump_file, map);
912 if (perform_ter)
914 values = find_replaceable_exprs (map);
915 if (values && dump_file && (dump_flags & TDF_DETAILS))
916 dump_replaceable_exprs (dump_file, values);
919 rewrite_trees (map);
921 sa->map = map;
922 sa->values = values;
923 sa->partition_has_default_def = BITMAP_ALLOC (NULL);
924 for (i = 1; i < num_ssa_names; i++)
926 tree t = ssa_name (i);
927 if (t && SSA_NAME_IS_DEFAULT_DEF (t))
929 int p = var_to_partition (map, t);
930 if (p != NO_PARTITION)
931 bitmap_set_bit (sa->partition_has_default_def, p);
937 /* If not already done so for basic block BB, assign increasing uids
938 to each of its instructions. */
940 static void
941 maybe_renumber_stmts_bb (basic_block bb)
943 unsigned i = 0;
944 gimple_stmt_iterator gsi;
946 if (!bb->aux)
947 return;
948 bb->aux = NULL;
949 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
951 gimple stmt = gsi_stmt (gsi);
952 gimple_set_uid (stmt, i);
953 i++;
958 /* Return true if we can determine that the SSA_NAMEs RESULT (a result
959 of a PHI node) and ARG (one of its arguments) conflict. Return false
960 otherwise, also when we simply aren't sure. */
962 static bool
963 trivially_conflicts_p (basic_block bb, tree result, tree arg)
965 use_operand_p use;
966 imm_use_iterator imm_iter;
967 gimple defa = SSA_NAME_DEF_STMT (arg);
969 /* If ARG isn't defined in the same block it's too complicated for
970 our little mind. */
971 if (gimple_bb (defa) != bb)
972 return false;
974 FOR_EACH_IMM_USE_FAST (use, imm_iter, result)
976 gimple use_stmt = USE_STMT (use);
977 if (is_gimple_debug (use_stmt))
978 continue;
979 /* Now, if there's a use of RESULT that lies outside this basic block,
980 then there surely is a conflict with ARG. */
981 if (gimple_bb (use_stmt) != bb)
982 return true;
983 if (gimple_code (use_stmt) == GIMPLE_PHI)
984 continue;
985 /* The use now is in a real stmt of BB, so if ARG was defined
986 in a PHI node (like RESULT) both conflict. */
987 if (gimple_code (defa) == GIMPLE_PHI)
988 return true;
989 maybe_renumber_stmts_bb (bb);
990 /* If the use of RESULT occurs after the definition of ARG,
991 the two conflict too. */
992 if (gimple_uid (defa) < gimple_uid (use_stmt))
993 return true;
996 return false;
1000 /* Search every PHI node for arguments associated with backedges which
1001 we can trivially determine will need a copy (the argument is either
1002 not an SSA_NAME or the argument has a different underlying variable
1003 than the PHI result).
1005 Insert a copy from the PHI argument to a new destination at the
1006 end of the block with the backedge to the top of the loop. Update
1007 the PHI argument to reference this new destination. */
1009 static void
1010 insert_backedge_copies (void)
1012 basic_block bb;
1013 gimple_stmt_iterator gsi;
1015 mark_dfs_back_edges ();
1017 FOR_EACH_BB (bb)
1019 /* Mark block as possibly needing calculation of UIDs. */
1020 bb->aux = &bb->aux;
1022 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1024 gimple phi = gsi_stmt (gsi);
1025 tree result = gimple_phi_result (phi);
1026 size_t i;
1028 if (virtual_operand_p (result))
1029 continue;
1031 for (i = 0; i < gimple_phi_num_args (phi); i++)
1033 tree arg = gimple_phi_arg_def (phi, i);
1034 edge e = gimple_phi_arg_edge (phi, i);
1036 /* If the argument is not an SSA_NAME, then we will need a
1037 constant initialization. If the argument is an SSA_NAME with
1038 a different underlying variable then a copy statement will be
1039 needed. */
1040 if ((e->flags & EDGE_DFS_BACK)
1041 && (TREE_CODE (arg) != SSA_NAME
1042 || SSA_NAME_VAR (arg) != SSA_NAME_VAR (result)
1043 || trivially_conflicts_p (bb, result, arg)))
1045 tree name;
1046 gimple stmt, last = NULL;
1047 gimple_stmt_iterator gsi2;
1049 gsi2 = gsi_last_bb (gimple_phi_arg_edge (phi, i)->src);
1050 if (!gsi_end_p (gsi2))
1051 last = gsi_stmt (gsi2);
1053 /* In theory the only way we ought to get back to the
1054 start of a loop should be with a COND_EXPR or GOTO_EXPR.
1055 However, better safe than sorry.
1056 If the block ends with a control statement or
1057 something that might throw, then we have to
1058 insert this assignment before the last
1059 statement. Else insert it after the last statement. */
1060 if (last && stmt_ends_bb_p (last))
1062 /* If the last statement in the block is the definition
1063 site of the PHI argument, then we can't insert
1064 anything after it. */
1065 if (TREE_CODE (arg) == SSA_NAME
1066 && SSA_NAME_DEF_STMT (arg) == last)
1067 continue;
1070 /* Create a new instance of the underlying variable of the
1071 PHI result. */
1072 name = copy_ssa_name (result, NULL);
1073 stmt = gimple_build_assign (name,
1074 gimple_phi_arg_def (phi, i));
1076 /* copy location if present. */
1077 if (gimple_phi_arg_has_location (phi, i))
1078 gimple_set_location (stmt,
1079 gimple_phi_arg_location (phi, i));
1081 /* Insert the new statement into the block and update
1082 the PHI node. */
1083 if (last && stmt_ends_bb_p (last))
1084 gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT);
1085 else
1086 gsi_insert_after (&gsi2, stmt, GSI_NEW_STMT);
1087 SET_PHI_ARG_DEF (phi, i, name);
1092 /* Unmark this block again. */
1093 bb->aux = NULL;
1097 /* Free all memory associated with going out of SSA form. SA is
1098 the outof-SSA info object. */
1100 void
1101 finish_out_of_ssa (struct ssaexpand *sa)
1103 free (sa->partition_to_pseudo);
1104 if (sa->values)
1105 BITMAP_FREE (sa->values);
1106 delete_var_map (sa->map);
1107 BITMAP_FREE (sa->partition_has_default_def);
1108 memset (sa, 0, sizeof *sa);
1111 /* Take the current function out of SSA form, translating PHIs as described in
1112 R. Morgan, ``Building an Optimizing Compiler'',
1113 Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */
1115 unsigned int
1116 rewrite_out_of_ssa (struct ssaexpand *sa)
1118 /* If elimination of a PHI requires inserting a copy on a backedge,
1119 then we will have to split the backedge which has numerous
1120 undesirable performance effects.
1122 A significant number of such cases can be handled here by inserting
1123 copies into the loop itself. */
1124 insert_backedge_copies ();
1127 /* Eliminate PHIs which are of no use, such as virtual or dead phis. */
1128 eliminate_useless_phis ();
1130 if (dump_file && (dump_flags & TDF_DETAILS))
1131 gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
1133 remove_ssa_form (flag_tree_ter, sa);
1135 if (dump_file && (dump_flags & TDF_DETAILS))
1136 gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
1138 return 0;