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);
570 enum machine_mode reg_mode = promote_decl_mode (var, &unsignedp);
571 rtx x = gen_reg_rtx (reg_mode);
572 if (POINTER_TYPE_P (type))
573 mark_reg_pointer (x, TYPE_ALIGN (TREE_TYPE (TREE_TYPE (var))));
577 /* Insert required copies for T in graph G. Check for a strongly connected
578 region, and create a temporary to break the cycle if one is found. */
581 elim_create (elim_graph g, int T)
584 source_location locus;
586 if (elim_unvisited_predecessor (g, T))
588 tree var = partition_to_var (g->map, T);
589 rtx U = get_temp_reg (var);
590 int unsignedsrcp = TYPE_UNSIGNED (TREE_TYPE (var));
592 insert_part_to_rtx_on_edge (g->e, U, T, UNKNOWN_LOCATION);
593 FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus,
595 if (!TEST_BIT (g->visited, P))
597 elim_backward (g, P);
598 insert_rtx_to_part_on_edge (g->e, P, U, unsignedsrcp, locus);
604 S = elim_graph_remove_succ_edge (g, T, &locus);
607 SET_BIT (g->visited, T);
608 insert_partition_copy_on_edge (g->e, T, S, locus);
614 /* Eliminate all the phi nodes on edge E in graph G. */
617 eliminate_phi (edge e, elim_graph g)
621 gcc_assert (VEC_length (tree, g->const_copies) == 0);
622 gcc_assert (VEC_length (source_location, g->copy_locus) == 0);
624 /* Abnormal edges already have everything coalesced. */
625 if (e->flags & EDGE_ABNORMAL)
632 if (elim_graph_size (g) != 0)
636 sbitmap_zero (g->visited);
637 VEC_truncate (int, g->stack, 0);
639 for (x = 0; VEC_iterate (int, g->nodes, x, part); x++)
641 if (!TEST_BIT (g->visited, part))
642 elim_forward (g, part);
645 sbitmap_zero (g->visited);
646 while (VEC_length (int, g->stack) > 0)
648 x = VEC_pop (int, g->stack);
649 if (!TEST_BIT (g->visited, x))
654 /* If there are any pending constant copies, issue them now. */
655 while (VEC_length (tree, g->const_copies) > 0)
659 source_location locus;
661 src = VEC_pop (tree, g->const_copies);
662 dest = VEC_pop (int, g->const_dests);
663 locus = VEC_pop (source_location, g->copy_locus);
664 insert_value_copy_on_edge (e, dest, src, locus);
669 /* Remove each argument from PHI. If an arg was the last use of an SSA_NAME,
670 check to see if this allows another PHI node to be removed. */
673 remove_gimple_phi_args (gimple phi)
678 if (dump_file && (dump_flags & TDF_DETAILS))
680 fprintf (dump_file, "Removing Dead PHI definition: ");
681 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
684 FOR_EACH_PHI_ARG (arg_p, phi, iter, SSA_OP_USE)
686 tree arg = USE_FROM_PTR (arg_p);
687 if (TREE_CODE (arg) == SSA_NAME)
689 /* Remove the reference to the existing argument. */
690 SET_USE (arg_p, NULL_TREE);
691 if (has_zero_uses (arg))
694 gimple_stmt_iterator gsi;
696 stmt = SSA_NAME_DEF_STMT (arg);
698 /* Also remove the def if it is a PHI node. */
699 if (gimple_code (stmt) == GIMPLE_PHI)
701 remove_gimple_phi_args (stmt);
702 gsi = gsi_for_stmt (stmt);
703 remove_phi_node (&gsi, true);
711 /* Remove any PHI node which is a virtual PHI, or a PHI with no uses. */
714 eliminate_useless_phis (void)
717 gimple_stmt_iterator gsi;
722 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
724 gimple phi = gsi_stmt (gsi);
725 result = gimple_phi_result (phi);
726 if (!is_gimple_reg (SSA_NAME_VAR (result)))
728 #ifdef ENABLE_CHECKING
730 /* There should be no arguments which are not virtual, or the
731 results will be incorrect. */
732 for (i = 0; i < gimple_phi_num_args (phi); i++)
734 tree arg = PHI_ARG_DEF (phi, i);
735 if (TREE_CODE (arg) == SSA_NAME
736 && is_gimple_reg (SSA_NAME_VAR (arg)))
738 fprintf (stderr, "Argument of PHI is not virtual (");
739 print_generic_expr (stderr, arg, TDF_SLIM);
740 fprintf (stderr, "), but the result is :");
741 print_gimple_stmt (stderr, phi, 0, TDF_SLIM);
742 internal_error ("SSA corruption");
746 remove_phi_node (&gsi, true);
750 /* Also remove real PHIs with no uses. */
751 if (has_zero_uses (result))
753 remove_gimple_phi_args (phi);
754 remove_phi_node (&gsi, true);
764 /* This function will rewrite the current program using the variable mapping
765 found in MAP. If the replacement vector VALUES is provided, any
766 occurrences of partitions with non-null entries in the vector will be
767 replaced with the expression in the vector instead of its mapped
771 rewrite_trees (var_map map ATTRIBUTE_UNUSED)
773 #ifdef ENABLE_CHECKING
775 /* Search for PHIs where the destination has no partition, but one
776 or more arguments has a partition. This should not happen and can
777 create incorrect code. */
780 gimple_stmt_iterator gsi;
781 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
783 gimple phi = gsi_stmt (gsi);
784 tree T0 = var_to_partition_to_var (map, gimple_phi_result (phi));
788 for (i = 0; i < gimple_phi_num_args (phi); i++)
790 tree arg = PHI_ARG_DEF (phi, i);
792 if (TREE_CODE (arg) == SSA_NAME
793 && var_to_partition (map, arg) != NO_PARTITION)
795 fprintf (stderr, "Argument of PHI is in a partition :(");
796 print_generic_expr (stderr, arg, TDF_SLIM);
797 fprintf (stderr, "), but the result is not :");
798 print_gimple_stmt (stderr, phi, 0, TDF_SLIM);
799 internal_error ("SSA corruption");
808 /* Given the out-of-ssa info object SA (with prepared partitions)
809 eliminate all phi nodes in all basic blocks. Afterwards no
810 basic block will have phi nodes anymore and there are possibly
811 some RTL instructions inserted on edges. */
814 expand_phi_nodes (struct ssaexpand *sa)
817 elim_graph g = new_elim_graph (sa->map->num_partitions);
820 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR, next_bb)
821 if (!gimple_seq_empty_p (phi_nodes (bb)))
825 FOR_EACH_EDGE (e, ei, bb->preds)
826 eliminate_phi (e, g);
827 set_phi_nodes (bb, NULL);
828 /* We can't redirect EH edges in RTL land, so we need to do this
829 here. Redirection happens only when splitting is necessary,
830 which it is only for critical edges, normally. For EH edges
831 it might also be necessary when the successor has more than
832 one predecessor. In that case the edge is either required to
833 be fallthru (which EH edges aren't), or the predecessor needs
834 to end with a jump (which again, isn't the case with EH edges).
835 Hence, split all EH edges on which we inserted instructions
836 and whose successor has multiple predecessors. */
837 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
839 if (e->insns.r && (e->flags & EDGE_EH)
840 && !single_pred_p (e->dest))
842 rtx insns = e->insns.r;
844 e->insns.r = NULL_RTX;
846 single_pred_edge (bb)->insns.r = insns;
853 delete_elim_graph (g);
857 /* Remove the ssa-names in the current function and translate them into normal
858 compiler variables. PERFORM_TER is true if Temporary Expression Replacement
859 should also be used. */
862 remove_ssa_form (bool perform_ter, struct ssaexpand *sa)
864 bitmap values = NULL;
868 map = coalesce_ssa_name ();
870 /* Return to viewing the variable list as just all reference variables after
871 coalescing has been performed. */
872 partition_view_normal (map, false);
874 if (dump_file && (dump_flags & TDF_DETAILS))
876 fprintf (dump_file, "After Coalescing:\n");
877 dump_var_map (dump_file, map);
882 values = find_replaceable_exprs (map);
883 if (values && dump_file && (dump_flags & TDF_DETAILS))
884 dump_replaceable_exprs (dump_file, values);
891 sa->partition_has_default_def = BITMAP_ALLOC (NULL);
892 for (i = 1; i < num_ssa_names; i++)
894 tree t = ssa_name (i);
895 if (t && SSA_NAME_IS_DEFAULT_DEF (t))
897 int p = var_to_partition (map, t);
898 if (p != NO_PARTITION)
899 bitmap_set_bit (sa->partition_has_default_def, p);
905 /* If not already done so for basic block BB, assign increasing uids
906 to each of its instructions. */
909 maybe_renumber_stmts_bb (basic_block bb)
912 gimple_stmt_iterator gsi;
917 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
919 gimple stmt = gsi_stmt (gsi);
920 gimple_set_uid (stmt, i);
926 /* Return true if we can determine that the SSA_NAMEs RESULT (a result
927 of a PHI node) and ARG (one of its arguments) conflict. Return false
928 otherwise, also when we simply aren't sure. */
931 trivially_conflicts_p (basic_block bb, tree result, tree arg)
934 imm_use_iterator imm_iter;
935 gimple defa = SSA_NAME_DEF_STMT (arg);
937 /* If ARG isn't defined in the same block it's too complicated for
939 if (gimple_bb (defa) != bb)
942 FOR_EACH_IMM_USE_FAST (use, imm_iter, result)
944 gimple use_stmt = USE_STMT (use);
945 /* Now, if there's a use of RESULT that lies outside this basic block,
946 then there surely is a conflict with ARG. */
947 if (gimple_bb (use_stmt) != bb)
949 if (gimple_code (use_stmt) == GIMPLE_PHI)
951 /* The use now is in a real stmt of BB, so if ARG was defined
952 in a PHI node (like RESULT) both conflict. */
953 if (gimple_code (defa) == GIMPLE_PHI)
955 maybe_renumber_stmts_bb (bb);
956 /* If the use of RESULT occurs after the definition of ARG,
957 the two conflict too. */
958 if (gimple_uid (defa) < gimple_uid (use_stmt))
966 /* Search every PHI node for arguments associated with backedges which
967 we can trivially determine will need a copy (the argument is either
968 not an SSA_NAME or the argument has a different underlying variable
969 than the PHI result).
971 Insert a copy from the PHI argument to a new destination at the
972 end of the block with the backedge to the top of the loop. Update
973 the PHI argument to reference this new destination. */
976 insert_backedge_copies (void)
979 gimple_stmt_iterator gsi;
983 /* Mark block as possibly needing calculation of UIDs. */
986 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
988 gimple phi = gsi_stmt (gsi);
989 tree result = gimple_phi_result (phi);
993 if (!is_gimple_reg (result))
996 result_var = SSA_NAME_VAR (result);
997 for (i = 0; i < gimple_phi_num_args (phi); i++)
999 tree arg = gimple_phi_arg_def (phi, i);
1000 edge e = gimple_phi_arg_edge (phi, i);
1002 /* If the argument is not an SSA_NAME, then we will need a
1003 constant initialization. If the argument is an SSA_NAME with
1004 a different underlying variable then a copy statement will be
1006 if ((e->flags & EDGE_DFS_BACK)
1007 && (TREE_CODE (arg) != SSA_NAME
1008 || SSA_NAME_VAR (arg) != result_var
1009 || trivially_conflicts_p (bb, result, arg)))
1012 gimple stmt, last = NULL;
1013 gimple_stmt_iterator gsi2;
1015 gsi2 = gsi_last_bb (gimple_phi_arg_edge (phi, i)->src);
1016 if (!gsi_end_p (gsi2))
1017 last = gsi_stmt (gsi2);
1019 /* In theory the only way we ought to get back to the
1020 start of a loop should be with a COND_EXPR or GOTO_EXPR.
1021 However, better safe than sorry.
1022 If the block ends with a control statement or
1023 something that might throw, then we have to
1024 insert this assignment before the last
1025 statement. Else insert it after the last statement. */
1026 if (last && stmt_ends_bb_p (last))
1028 /* If the last statement in the block is the definition
1029 site of the PHI argument, then we can't insert
1030 anything after it. */
1031 if (TREE_CODE (arg) == SSA_NAME
1032 && SSA_NAME_DEF_STMT (arg) == last)
1036 /* Create a new instance of the underlying variable of the
1038 stmt = gimple_build_assign (result_var,
1039 gimple_phi_arg_def (phi, i));
1040 name = make_ssa_name (result_var, stmt);
1041 gimple_assign_set_lhs (stmt, name);
1043 /* copy location if present. */
1044 if (gimple_phi_arg_has_location (phi, i))
1045 gimple_set_location (stmt,
1046 gimple_phi_arg_location (phi, i));
1048 /* Insert the new statement into the block and update
1050 if (last && stmt_ends_bb_p (last))
1051 gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT);
1053 gsi_insert_after (&gsi2, stmt, GSI_NEW_STMT);
1054 SET_PHI_ARG_DEF (phi, i, name);
1059 /* Unmark this block again. */
1064 /* Free all memory associated with going out of SSA form. SA is
1065 the outof-SSA info object. */
1068 finish_out_of_ssa (struct ssaexpand *sa)
1070 free (sa->partition_to_pseudo);
1072 BITMAP_FREE (sa->values);
1073 delete_var_map (sa->map);
1074 BITMAP_FREE (sa->partition_has_default_def);
1075 memset (sa, 0, sizeof *sa);
1078 /* Take the current function out of SSA form, translating PHIs as described in
1079 R. Morgan, ``Building an Optimizing Compiler'',
1080 Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */
1083 rewrite_out_of_ssa (struct ssaexpand *sa)
1085 /* If elimination of a PHI requires inserting a copy on a backedge,
1086 then we will have to split the backedge which has numerous
1087 undesirable performance effects.
1089 A significant number of such cases can be handled here by inserting
1090 copies into the loop itself. */
1091 insert_backedge_copies ();
1094 /* Eliminate PHIs which are of no use, such as virtual or dead phis. */
1095 eliminate_useless_phis ();
1097 if (dump_file && (dump_flags & TDF_DETAILS))
1098 gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
1100 remove_ssa_form (flag_tree_ter, sa);
1102 if (dump_file && (dump_flags & TDF_DETAILS))
1103 gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);