1 /* Convert a program in SSA form into Normal form.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008 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)
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/>. */
23 #include "coretypes.h"
27 #include "basic-block.h"
28 #include "diagnostic.h"
30 #include "tree-flow.h"
32 #include "tree-dump.h"
33 #include "tree-pass.h"
36 #include "ssaexpand.h"
39 DEF_VEC_I(source_location);
40 DEF_VEC_ALLOC_I(source_location,heap);
42 /* Used to hold all the components required to do SSA PHI elimination.
43 The node and pred/succ list is a simple linear list of nodes and
44 edges represented as pairs of nodes.
46 The predecessor and successor list: Nodes are entered in pairs, where
47 [0] ->PRED, [1]->SUCC. All the even indexes in the array represent
48 predecessors, all the odd elements are successors.
51 When implemented as bitmaps, very large programs SSA->Normal times were
52 being dominated by clearing the interference graph.
54 Typically this list of edges is extremely small since it only includes
55 PHI results and uses from a single edge which have not coalesced with
56 each other. This means that no virtual PHI nodes are included, and
57 empirical evidence suggests that the number of edges rarely exceed
58 3, and in a bootstrap of GCC, the maximum size encountered was 7.
59 This also limits the number of possible nodes that are involved to
60 rarely more than 6, and in the bootstrap of gcc, the maximum number
61 of nodes encountered was 12. */
63 typedef struct _elim_graph {
64 /* Size of the elimination vectors. */
67 /* List of nodes in the elimination graph. */
70 /* The predecessor and successor edge list. */
71 VEC(int,heap) *edge_list;
73 /* Source locus on each edge */
74 VEC(source_location,heap) *edge_locus;
79 /* Stack for visited nodes. */
82 /* The variable partition map. */
85 /* Edge being eliminated by this graph. */
88 /* List of constant copies to emit. These are pushed on in pairs. */
89 VEC(int,heap) *const_dests;
90 VEC(tree,heap) *const_copies;
92 /* Source locations for any constant copies. */
93 VEC(source_location,heap) *copy_locus;
97 /* For an edge E find out a good source location to associate with
98 instructions inserted on edge E. If E has an implicit goto set,
99 use its location. Otherwise search instructions in predecessors
100 of E for a location, and use that one. That makes sense because
101 we insert on edges for PHI nodes, and effects of PHIs happen on
102 the end of the predecessor conceptually. */
105 set_location_for_edge (edge e)
109 set_curr_insn_source_location (e->goto_locus);
110 set_curr_insn_block (e->goto_block);
114 basic_block bb = e->src;
115 gimple_stmt_iterator gsi;
119 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
121 gimple stmt = gsi_stmt (gsi);
122 if (gimple_has_location (stmt) || gimple_block (stmt))
124 set_curr_insn_source_location (gimple_location (stmt));
125 set_curr_insn_block (gimple_block (stmt));
129 /* Nothing found in this basic block. Make a half-assed attempt
130 to continue with another block. */
131 if (single_pred_p (bb))
132 bb = single_pred (bb);
136 while (bb != e->src);
140 /* Emit insns to copy SRC into DEST converting SRC if necessary. */
143 emit_partition_copy (rtx dest, rtx src, int unsignedsrcp)
149 if (GET_MODE (src) != VOIDmode && GET_MODE (src) != GET_MODE (dest))
150 src = convert_to_mode (GET_MODE (dest), src, unsignedsrcp);
151 emit_move_insn (dest, src);
159 /* Insert a copy instruction from partition SRC to DEST onto edge E. */
162 insert_partition_copy_on_edge (edge e, int dest, int src, source_location locus)
165 if (dump_file && (dump_flags & TDF_DETAILS))
168 "Inserting a partition copy on edge BB%d->BB%d :"
171 e->dest->index, dest, src);
172 fprintf (dump_file, "\n");
175 gcc_assert (SA.partition_to_pseudo[dest]);
176 gcc_assert (SA.partition_to_pseudo[src]);
178 set_location_for_edge (e);
179 /* If a locus is provided, override the default. */
181 set_curr_insn_source_location (locus);
183 seq = emit_partition_copy (SA.partition_to_pseudo[dest],
184 SA.partition_to_pseudo[src],
185 TYPE_UNSIGNED (TREE_TYPE (
186 partition_to_var (SA.map, src))));
188 insert_insn_on_edge (seq, e);
191 /* Insert a copy instruction from expression SRC to partition DEST
195 insert_value_copy_on_edge (edge e, int dest, tree src, source_location locus)
198 enum machine_mode mode;
199 if (dump_file && (dump_flags & TDF_DETAILS))
202 "Inserting a value copy on edge BB%d->BB%d : PART.%d = ",
204 e->dest->index, dest);
205 print_generic_expr (dump_file, src, TDF_SLIM);
206 fprintf (dump_file, "\n");
209 gcc_assert (SA.partition_to_pseudo[dest]);
211 set_location_for_edge (e);
212 /* If a locus is provided, override the default. */
214 set_curr_insn_source_location (locus);
217 mode = GET_MODE (SA.partition_to_pseudo[dest]);
218 x = expand_expr (src, SA.partition_to_pseudo[dest], mode, EXPAND_NORMAL);
219 if (GET_MODE (x) != VOIDmode && GET_MODE (x) != mode)
220 x = convert_to_mode (mode, x, TYPE_UNSIGNED (TREE_TYPE (src)));
221 if (CONSTANT_P (x) && GET_MODE (x) == VOIDmode
222 && mode != TYPE_MODE (TREE_TYPE (src)))
223 x = convert_modes (mode, TYPE_MODE (TREE_TYPE (src)),
224 x, TYPE_UNSIGNED (TREE_TYPE (src)));
225 if (x != SA.partition_to_pseudo[dest])
226 emit_move_insn (SA.partition_to_pseudo[dest], x);
230 insert_insn_on_edge (seq, e);
233 /* Insert a copy instruction from RTL expression SRC to partition DEST
237 insert_rtx_to_part_on_edge (edge e, int dest, rtx src, int unsignedsrcp,
238 source_location locus)
241 if (dump_file && (dump_flags & TDF_DETAILS))
244 "Inserting a temp copy on edge BB%d->BB%d : PART.%d = ",
246 e->dest->index, dest);
247 print_simple_rtl (dump_file, src);
248 fprintf (dump_file, "\n");
251 gcc_assert (SA.partition_to_pseudo[dest]);
253 set_location_for_edge (e);
254 /* If a locus is provided, override the default. */
256 set_curr_insn_source_location (locus);
258 seq = emit_partition_copy (SA.partition_to_pseudo[dest],
262 insert_insn_on_edge (seq, e);
265 /* Insert a copy instruction from partition SRC to RTL lvalue DEST
269 insert_part_to_rtx_on_edge (edge e, rtx dest, int src, source_location locus)
272 if (dump_file && (dump_flags & TDF_DETAILS))
275 "Inserting a temp copy on edge BB%d->BB%d : ",
278 print_simple_rtl (dump_file, dest);
279 fprintf (dump_file, "= PART.%d\n", src);
282 gcc_assert (SA.partition_to_pseudo[src]);
284 set_location_for_edge (e);
285 /* If a locus is provided, override the default. */
287 set_curr_insn_source_location (locus);
289 seq = emit_partition_copy (dest,
290 SA.partition_to_pseudo[src],
291 TYPE_UNSIGNED (TREE_TYPE (
292 partition_to_var (SA.map, src))));
294 insert_insn_on_edge (seq, e);
298 /* Create an elimination graph with SIZE nodes and associated data
302 new_elim_graph (int size)
304 elim_graph g = (elim_graph) xmalloc (sizeof (struct _elim_graph));
306 g->nodes = VEC_alloc (int, heap, 30);
307 g->const_dests = VEC_alloc (int, heap, 20);
308 g->const_copies = VEC_alloc (tree, heap, 20);
309 g->copy_locus = VEC_alloc (source_location, heap, 10);
310 g->edge_list = VEC_alloc (int, heap, 20);
311 g->edge_locus = VEC_alloc (source_location, heap, 10);
312 g->stack = VEC_alloc (int, heap, 30);
314 g->visited = sbitmap_alloc (size);
320 /* Empty elimination graph G. */
323 clear_elim_graph (elim_graph g)
325 VEC_truncate (int, g->nodes, 0);
326 VEC_truncate (int, g->edge_list, 0);
327 VEC_truncate (source_location, g->edge_locus, 0);
331 /* Delete elimination graph G. */
334 delete_elim_graph (elim_graph g)
336 sbitmap_free (g->visited);
337 VEC_free (int, heap, g->stack);
338 VEC_free (int, heap, g->edge_list);
339 VEC_free (tree, heap, g->const_copies);
340 VEC_free (int, heap, g->const_dests);
341 VEC_free (int, heap, g->nodes);
342 VEC_free (source_location, heap, g->copy_locus);
343 VEC_free (source_location, heap, g->edge_locus);
349 /* Return the number of nodes in graph G. */
352 elim_graph_size (elim_graph g)
354 return VEC_length (int, g->nodes);
358 /* Add NODE to graph G, if it doesn't exist already. */
361 elim_graph_add_node (elim_graph g, int node)
366 for (x = 0; VEC_iterate (int, g->nodes, x, t); x++)
369 VEC_safe_push (int, heap, g->nodes, node);
373 /* Add the edge PRED->SUCC to graph G. */
376 elim_graph_add_edge (elim_graph g, int pred, int succ, source_location locus)
378 VEC_safe_push (int, heap, g->edge_list, pred);
379 VEC_safe_push (int, heap, g->edge_list, succ);
380 VEC_safe_push (source_location, heap, g->edge_locus, locus);
384 /* Remove an edge from graph G for which NODE is the predecessor, and
385 return the successor node. -1 is returned if there is no such edge. */
388 elim_graph_remove_succ_edge (elim_graph g, int node, source_location *locus)
392 for (x = 0; x < VEC_length (int, g->edge_list); x += 2)
393 if (VEC_index (int, g->edge_list, x) == node)
395 VEC_replace (int, g->edge_list, x, -1);
396 y = VEC_index (int, g->edge_list, x + 1);
397 VEC_replace (int, g->edge_list, x + 1, -1);
398 *locus = VEC_index (source_location, g->edge_locus, x / 2);
399 VEC_replace (source_location, g->edge_locus, x / 2, UNKNOWN_LOCATION);
402 *locus = UNKNOWN_LOCATION;
407 /* Find all the nodes in GRAPH which are successors to NODE in the
408 edge list. VAR will hold the partition number found. CODE is the
409 code fragment executed for every node found. */
411 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, LOCUS, CODE) \
415 for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2) \
417 y_ = VEC_index (int, (GRAPH)->edge_list, x_); \
420 (VAR) = VEC_index (int, (GRAPH)->edge_list, x_ + 1); \
421 (LOCUS) = VEC_index (source_location, (GRAPH)->edge_locus, x_ / 2); \
427 /* Find all the nodes which are predecessors of NODE in the edge list for
428 GRAPH. VAR will hold the partition number found. CODE is the
429 code fragment executed for every node found. */
431 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, LOCUS, CODE) \
435 for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2) \
437 y_ = VEC_index (int, (GRAPH)->edge_list, x_ + 1); \
440 (VAR) = VEC_index (int, (GRAPH)->edge_list, x_); \
441 (LOCUS) = VEC_index (source_location, (GRAPH)->edge_locus, x_ / 2); \
447 /* Add T to elimination graph G. */
450 eliminate_name (elim_graph g, int T)
452 elim_graph_add_node (g, T);
456 /* Build elimination graph G for basic block BB on incoming PHI edge
460 eliminate_build (elim_graph g)
464 gimple_stmt_iterator gsi;
466 clear_elim_graph (g);
468 for (gsi = gsi_start_phis (g->e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
470 gimple phi = gsi_stmt (gsi);
471 source_location locus;
473 p0 = var_to_partition (g->map, gimple_phi_result (phi));
474 /* Ignore results which are not in partitions. */
475 if (p0 == NO_PARTITION)
478 Ti = PHI_ARG_DEF (phi, g->e->dest_idx);
479 locus = gimple_phi_arg_location_from_edge (phi, g->e);
481 /* If this argument is a constant, or a SSA_NAME which is being
482 left in SSA form, just queue a copy to be emitted on this
484 if (!phi_ssa_name_p (Ti)
485 || (TREE_CODE (Ti) == SSA_NAME
486 && var_to_partition (g->map, Ti) == NO_PARTITION))
488 /* Save constant copies until all other copies have been emitted
490 VEC_safe_push (int, heap, g->const_dests, p0);
491 VEC_safe_push (tree, heap, g->const_copies, Ti);
492 VEC_safe_push (source_location, heap, g->copy_locus, locus);
496 pi = var_to_partition (g->map, Ti);
499 eliminate_name (g, p0);
500 eliminate_name (g, pi);
501 elim_graph_add_edge (g, p0, pi, locus);
508 /* Push successors of T onto the elimination stack for G. */
511 elim_forward (elim_graph g, int T)
514 source_location locus;
516 SET_BIT (g->visited, T);
517 FOR_EACH_ELIM_GRAPH_SUCC (g, T, S, locus,
519 if (!TEST_BIT (g->visited, S))
522 VEC_safe_push (int, heap, g->stack, T);
526 /* Return 1 if there unvisited predecessors of T in graph G. */
529 elim_unvisited_predecessor (elim_graph g, int T)
532 source_location locus;
534 FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus,
536 if (!TEST_BIT (g->visited, P))
542 /* Process predecessors first, and insert a copy. */
545 elim_backward (elim_graph g, int T)
548 source_location locus;
550 SET_BIT (g->visited, T);
551 FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus,
553 if (!TEST_BIT (g->visited, P))
555 elim_backward (g, P);
556 insert_partition_copy_on_edge (g->e, P, T, locus);
561 /* Allocate a new pseudo register usable for storing values sitting
562 in NAME (a decl or SSA name), i.e. with matching mode and attributes. */
565 get_temp_reg (tree name)
567 tree var = TREE_CODE (name) == SSA_NAME ? SSA_NAME_VAR (name) : name;
568 tree type = TREE_TYPE (var);
569 int unsignedp = TYPE_UNSIGNED (type);
570 enum machine_mode reg_mode
571 = promote_mode (type, DECL_MODE (var), &unsignedp, 0);
572 rtx x = gen_reg_rtx (reg_mode);
573 if (POINTER_TYPE_P (type))
574 mark_reg_pointer (x, TYPE_ALIGN (TREE_TYPE (TREE_TYPE (var))));
578 /* Insert required copies for T in graph G. Check for a strongly connected
579 region, and create a temporary to break the cycle if one is found. */
582 elim_create (elim_graph g, int T)
585 source_location locus;
587 if (elim_unvisited_predecessor (g, T))
589 tree var = partition_to_var (g->map, T);
590 rtx U = get_temp_reg (var);
591 int unsignedsrcp = TYPE_UNSIGNED (TREE_TYPE (var));
593 insert_part_to_rtx_on_edge (g->e, U, T, UNKNOWN_LOCATION);
594 FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus,
596 if (!TEST_BIT (g->visited, P))
598 elim_backward (g, P);
599 insert_rtx_to_part_on_edge (g->e, P, U, unsignedsrcp, locus);
605 S = elim_graph_remove_succ_edge (g, T, &locus);
608 SET_BIT (g->visited, T);
609 insert_partition_copy_on_edge (g->e, T, S, locus);
615 /* Eliminate all the phi nodes on edge E in graph G. */
618 eliminate_phi (edge e, elim_graph g)
622 gcc_assert (VEC_length (tree, g->const_copies) == 0);
623 gcc_assert (VEC_length (source_location, g->copy_locus) == 0);
625 /* Abnormal edges already have everything coalesced. */
626 if (e->flags & EDGE_ABNORMAL)
633 if (elim_graph_size (g) != 0)
637 sbitmap_zero (g->visited);
638 VEC_truncate (int, g->stack, 0);
640 for (x = 0; VEC_iterate (int, g->nodes, x, part); x++)
642 if (!TEST_BIT (g->visited, part))
643 elim_forward (g, part);
646 sbitmap_zero (g->visited);
647 while (VEC_length (int, g->stack) > 0)
649 x = VEC_pop (int, g->stack);
650 if (!TEST_BIT (g->visited, x))
655 /* If there are any pending constant copies, issue them now. */
656 while (VEC_length (tree, g->const_copies) > 0)
660 source_location locus;
662 src = VEC_pop (tree, g->const_copies);
663 dest = VEC_pop (int, g->const_dests);
664 locus = VEC_pop (source_location, g->copy_locus);
665 insert_value_copy_on_edge (e, dest, src, locus);
670 /* Remove each argument from PHI. If an arg was the last use of an SSA_NAME,
671 check to see if this allows another PHI node to be removed. */
674 remove_gimple_phi_args (gimple phi)
679 if (dump_file && (dump_flags & TDF_DETAILS))
681 fprintf (dump_file, "Removing Dead PHI definition: ");
682 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
685 FOR_EACH_PHI_ARG (arg_p, phi, iter, SSA_OP_USE)
687 tree arg = USE_FROM_PTR (arg_p);
688 if (TREE_CODE (arg) == SSA_NAME)
690 /* Remove the reference to the existing argument. */
691 SET_USE (arg_p, NULL_TREE);
692 if (has_zero_uses (arg))
695 gimple_stmt_iterator gsi;
697 stmt = SSA_NAME_DEF_STMT (arg);
699 /* Also remove the def if it is a PHI node. */
700 if (gimple_code (stmt) == GIMPLE_PHI)
702 remove_gimple_phi_args (stmt);
703 gsi = gsi_for_stmt (stmt);
704 remove_phi_node (&gsi, true);
712 /* Remove any PHI node which is a virtual PHI, or a PHI with no uses. */
715 eliminate_useless_phis (void)
718 gimple_stmt_iterator gsi;
723 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
725 gimple phi = gsi_stmt (gsi);
726 result = gimple_phi_result (phi);
727 if (!is_gimple_reg (SSA_NAME_VAR (result)))
729 #ifdef ENABLE_CHECKING
731 /* There should be no arguments which are not virtual, or the
732 results will be incorrect. */
733 for (i = 0; i < gimple_phi_num_args (phi); i++)
735 tree arg = PHI_ARG_DEF (phi, i);
736 if (TREE_CODE (arg) == SSA_NAME
737 && is_gimple_reg (SSA_NAME_VAR (arg)))
739 fprintf (stderr, "Argument of PHI is not virtual (");
740 print_generic_expr (stderr, arg, TDF_SLIM);
741 fprintf (stderr, "), but the result is :");
742 print_gimple_stmt (stderr, phi, 0, TDF_SLIM);
743 internal_error ("SSA corruption");
747 remove_phi_node (&gsi, true);
751 /* Also remove real PHIs with no uses. */
752 if (has_zero_uses (result))
754 remove_gimple_phi_args (phi);
755 remove_phi_node (&gsi, true);
765 /* This function will rewrite the current program using the variable mapping
766 found in MAP. If the replacement vector VALUES is provided, any
767 occurrences of partitions with non-null entries in the vector will be
768 replaced with the expression in the vector instead of its mapped
772 rewrite_trees (var_map map ATTRIBUTE_UNUSED)
774 #ifdef ENABLE_CHECKING
776 /* Search for PHIs where the destination has no partition, but one
777 or more arguments has a partition. This should not happen and can
778 create incorrect code. */
781 gimple_stmt_iterator gsi;
782 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
784 gimple phi = gsi_stmt (gsi);
785 tree T0 = var_to_partition_to_var (map, gimple_phi_result (phi));
789 for (i = 0; i < gimple_phi_num_args (phi); i++)
791 tree arg = PHI_ARG_DEF (phi, i);
793 if (TREE_CODE (arg) == SSA_NAME
794 && var_to_partition (map, arg) != NO_PARTITION)
796 fprintf (stderr, "Argument of PHI is in a partition :(");
797 print_generic_expr (stderr, arg, TDF_SLIM);
798 fprintf (stderr, "), but the result is not :");
799 print_gimple_stmt (stderr, phi, 0, TDF_SLIM);
800 internal_error ("SSA corruption");
809 /* Given the out-of-ssa info object SA (with prepared partitions)
810 eliminate all phi nodes in all basic blocks. Afterwards no
811 basic block will have phi nodes anymore and there are possibly
812 some RTL instructions inserted on edges. */
815 expand_phi_nodes (struct ssaexpand *sa)
818 elim_graph g = new_elim_graph (sa->map->num_partitions);
821 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR, next_bb)
822 if (!gimple_seq_empty_p (phi_nodes (bb)))
826 FOR_EACH_EDGE (e, ei, bb->preds)
827 eliminate_phi (e, g);
828 set_phi_nodes (bb, NULL);
829 /* We can't redirect EH edges in RTL land, so we need to do this
830 here. Redirection happens only when splitting is necessary,
831 which it is only for critical edges, normally. For EH edges
832 it might also be necessary when the successor has more than
833 one predecessor. In that case the edge is either required to
834 be fallthru (which EH edges aren't), or the predecessor needs
835 to end with a jump (which again, isn't the case with EH edges).
836 Hence, split all EH edges on which we inserted instructions
837 and whose successor has multiple predecessors. */
838 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
840 if (e->insns.r && (e->flags & EDGE_EH)
841 && !single_pred_p (e->dest))
843 rtx insns = e->insns.r;
845 e->insns.r = NULL_RTX;
847 single_pred_edge (bb)->insns.r = insns;
854 delete_elim_graph (g);
858 /* Remove the ssa-names in the current function and translate them into normal
859 compiler variables. PERFORM_TER is true if Temporary Expression Replacement
860 should also be used. */
863 remove_ssa_form (bool perform_ter, struct ssaexpand *sa)
865 bitmap values = NULL;
869 map = coalesce_ssa_name ();
871 /* Return to viewing the variable list as just all reference variables after
872 coalescing has been performed. */
873 partition_view_normal (map, false);
875 if (dump_file && (dump_flags & TDF_DETAILS))
877 fprintf (dump_file, "After Coalescing:\n");
878 dump_var_map (dump_file, map);
883 values = find_replaceable_exprs (map);
884 if (values && dump_file && (dump_flags & TDF_DETAILS))
885 dump_replaceable_exprs (dump_file, values);
892 sa->partition_has_default_def = BITMAP_ALLOC (NULL);
893 for (i = 1; i < num_ssa_names; i++)
895 tree t = ssa_name (i);
896 if (t && SSA_NAME_IS_DEFAULT_DEF (t))
898 int p = var_to_partition (map, t);
899 if (p != NO_PARTITION)
900 bitmap_set_bit (sa->partition_has_default_def, p);
906 /* If not already done so for basic block BB, assign increasing uids
907 to each of its instructions. */
910 maybe_renumber_stmts_bb (basic_block bb)
913 gimple_stmt_iterator gsi;
918 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
920 gimple stmt = gsi_stmt (gsi);
921 gimple_set_uid (stmt, i);
927 /* Return true if we can determine that the SSA_NAMEs RESULT (a result
928 of a PHI node) and ARG (one of its arguments) conflict. Return false
929 otherwise, also when we simply aren't sure. */
932 trivially_conflicts_p (basic_block bb, tree result, tree arg)
935 imm_use_iterator imm_iter;
936 gimple defa = SSA_NAME_DEF_STMT (arg);
938 /* If ARG isn't defined in the same block it's too complicated for
940 if (gimple_bb (defa) != bb)
943 FOR_EACH_IMM_USE_FAST (use, imm_iter, result)
945 gimple use_stmt = USE_STMT (use);
946 /* Now, if there's a use of RESULT that lies outside this basic block,
947 then there surely is a conflict with ARG. */
948 if (gimple_bb (use_stmt) != bb)
950 if (gimple_code (use_stmt) == GIMPLE_PHI)
952 /* The use now is in a real stmt of BB, so if ARG was defined
953 in a PHI node (like RESULT) both conflict. */
954 if (gimple_code (defa) == GIMPLE_PHI)
956 maybe_renumber_stmts_bb (bb);
957 /* If the use of RESULT occurs after the definition of ARG,
958 the two conflict too. */
959 if (gimple_uid (defa) < gimple_uid (use_stmt))
967 /* Search every PHI node for arguments associated with backedges which
968 we can trivially determine will need a copy (the argument is either
969 not an SSA_NAME or the argument has a different underlying variable
970 than the PHI result).
972 Insert a copy from the PHI argument to a new destination at the
973 end of the block with the backedge to the top of the loop. Update
974 the PHI argument to reference this new destination. */
977 insert_backedge_copies (void)
980 gimple_stmt_iterator gsi;
984 /* Mark block as possibly needing calculation of UIDs. */
987 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
989 gimple phi = gsi_stmt (gsi);
990 tree result = gimple_phi_result (phi);
994 if (!is_gimple_reg (result))
997 result_var = SSA_NAME_VAR (result);
998 for (i = 0; i < gimple_phi_num_args (phi); i++)
1000 tree arg = gimple_phi_arg_def (phi, i);
1001 edge e = gimple_phi_arg_edge (phi, i);
1003 /* If the argument is not an SSA_NAME, then we will need a
1004 constant initialization. If the argument is an SSA_NAME with
1005 a different underlying variable then a copy statement will be
1007 if ((e->flags & EDGE_DFS_BACK)
1008 && (TREE_CODE (arg) != SSA_NAME
1009 || SSA_NAME_VAR (arg) != result_var
1010 || trivially_conflicts_p (bb, result, arg)))
1013 gimple stmt, last = NULL;
1014 gimple_stmt_iterator gsi2;
1016 gsi2 = gsi_last_bb (gimple_phi_arg_edge (phi, i)->src);
1017 if (!gsi_end_p (gsi2))
1018 last = gsi_stmt (gsi2);
1020 /* In theory the only way we ought to get back to the
1021 start of a loop should be with a COND_EXPR or GOTO_EXPR.
1022 However, better safe than sorry.
1023 If the block ends with a control statement or
1024 something that might throw, then we have to
1025 insert this assignment before the last
1026 statement. Else insert it after the last statement. */
1027 if (last && stmt_ends_bb_p (last))
1029 /* If the last statement in the block is the definition
1030 site of the PHI argument, then we can't insert
1031 anything after it. */
1032 if (TREE_CODE (arg) == SSA_NAME
1033 && SSA_NAME_DEF_STMT (arg) == last)
1037 /* Create a new instance of the underlying variable of the
1039 stmt = gimple_build_assign (result_var,
1040 gimple_phi_arg_def (phi, i));
1041 name = make_ssa_name (result_var, stmt);
1042 gimple_assign_set_lhs (stmt, name);
1044 /* copy location if present. */
1045 if (gimple_phi_arg_has_location (phi, i))
1046 gimple_set_location (stmt,
1047 gimple_phi_arg_location (phi, i));
1049 /* Insert the new statement into the block and update
1051 if (last && stmt_ends_bb_p (last))
1052 gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT);
1054 gsi_insert_after (&gsi2, stmt, GSI_NEW_STMT);
1055 SET_PHI_ARG_DEF (phi, i, name);
1060 /* Unmark this block again. */
1065 /* Free all memory associated with going out of SSA form. SA is
1066 the outof-SSA info object. */
1069 finish_out_of_ssa (struct ssaexpand *sa)
1071 free (sa->partition_to_pseudo);
1073 BITMAP_FREE (sa->values);
1074 delete_var_map (sa->map);
1075 BITMAP_FREE (sa->partition_has_default_def);
1076 memset (sa, 0, sizeof *sa);
1079 /* Take the current function out of SSA form, translating PHIs as described in
1080 R. Morgan, ``Building an Optimizing Compiler'',
1081 Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */
1084 rewrite_out_of_ssa (struct ssaexpand *sa)
1086 /* If elimination of a PHI requires inserting a copy on a backedge,
1087 then we will have to split the backedge which has numerous
1088 undesirable performance effects.
1090 A significant number of such cases can be handled here by inserting
1091 copies into the loop itself. */
1092 insert_backedge_copies ();
1095 /* Eliminate PHIs which are of no use, such as virtual or dead phis. */
1096 eliminate_useless_phis ();
1098 if (dump_file && (dump_flags & TDF_DETAILS))
1099 gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
1101 remove_ssa_form (flag_tree_ter, sa);
1103 if (dump_file && (dump_flags & TDF_DETAILS))
1104 gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);