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 /* Used to hold all the components required to do SSA PHI elimination.
40 The node and pred/succ list is a simple linear list of nodes and
41 edges represented as pairs of nodes.
43 The predecessor and successor list: Nodes are entered in pairs, where
44 [0] ->PRED, [1]->SUCC. All the even indexes in the array represent
45 predecessors, all the odd elements are successors.
48 When implemented as bitmaps, very large programs SSA->Normal times were
49 being dominated by clearing the interference graph.
51 Typically this list of edges is extremely small since it only includes
52 PHI results and uses from a single edge which have not coalesced with
53 each other. This means that no virtual PHI nodes are included, and
54 empirical evidence suggests that the number of edges rarely exceed
55 3, and in a bootstrap of GCC, the maximum size encountered was 7.
56 This also limits the number of possible nodes that are involved to
57 rarely more than 6, and in the bootstrap of gcc, the maximum number
58 of nodes encountered was 12. */
60 typedef struct _elim_graph
{
61 /* Size of the elimination vectors. */
64 /* List of nodes in the elimination graph. */
67 /* The predecessor and successor edge list. */
68 VEC(int,heap
) *edge_list
;
73 /* Stack for visited nodes. */
76 /* The variable partition map. */
79 /* Edge being eliminated by this graph. */
82 /* List of constant copies to emit. These are pushed on in pairs. */
83 VEC(int,heap
) *const_dests
;
84 VEC(tree
,heap
) *const_copies
;
88 /* For an edge E find out a good source location to associate with
89 instructions inserted on edge E. If E has an implicit goto set,
90 use its location. Otherwise search instructions in predecessors
91 of E for a location, and use that one. That makes sense because
92 we insert on edges for PHI nodes, and effects of PHIs happen on
93 the end of the predecessor conceptually. */
96 set_location_for_edge (edge e
)
100 set_curr_insn_source_location (e
->goto_locus
);
101 set_curr_insn_block (e
->goto_block
);
105 basic_block bb
= e
->src
;
106 gimple_stmt_iterator gsi
;
110 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
112 gimple stmt
= gsi_stmt (gsi
);
113 if (gimple_has_location (stmt
) || gimple_block (stmt
))
115 set_curr_insn_source_location (gimple_location (stmt
));
116 set_curr_insn_block (gimple_block (stmt
));
120 /* Nothing found in this basic block. Make a half-assed attempt
121 to continue with another block. */
122 if (single_pred_p (bb
))
123 bb
= single_pred (bb
);
127 while (bb
!= e
->src
);
131 /* Emit insns to copy SRC into DEST converting SRC if necessary. */
134 emit_partition_copy (rtx dest
, rtx src
, int unsignedsrcp
)
140 if (GET_MODE (src
) != VOIDmode
&& GET_MODE (src
) != GET_MODE (dest
))
141 src
= convert_to_mode (GET_MODE (dest
), src
, unsignedsrcp
);
142 emit_move_insn (dest
, src
);
150 /* Insert a copy instruction from partition SRC to DEST onto edge E. */
153 insert_partition_copy_on_edge (edge e
, int dest
, int src
)
156 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
159 "Inserting a partition copy on edge BB%d->BB%d :"
162 e
->dest
->index
, dest
, src
);
163 fprintf (dump_file
, "\n");
166 gcc_assert (SA
.partition_to_pseudo
[dest
]);
167 gcc_assert (SA
.partition_to_pseudo
[src
]);
169 set_location_for_edge (e
);
171 seq
= emit_partition_copy (SA
.partition_to_pseudo
[dest
],
172 SA
.partition_to_pseudo
[src
],
173 TYPE_UNSIGNED (TREE_TYPE (
174 partition_to_var (SA
.map
, src
))));
176 insert_insn_on_edge (seq
, e
);
179 /* Insert a copy instruction from expression SRC to partition DEST
183 insert_value_copy_on_edge (edge e
, int dest
, tree src
)
186 enum machine_mode mode
;
187 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
190 "Inserting a value copy on edge BB%d->BB%d : PART.%d = ",
192 e
->dest
->index
, dest
);
193 print_generic_expr (dump_file
, src
, TDF_SLIM
);
194 fprintf (dump_file
, "\n");
197 gcc_assert (SA
.partition_to_pseudo
[dest
]);
199 set_location_for_edge (e
);
202 mode
= GET_MODE (SA
.partition_to_pseudo
[dest
]);
203 x
= expand_expr (src
, SA
.partition_to_pseudo
[dest
], mode
, EXPAND_NORMAL
);
204 if (GET_MODE (x
) != VOIDmode
&& GET_MODE (x
) != mode
)
205 x
= convert_to_mode (mode
, x
, TYPE_UNSIGNED (TREE_TYPE (src
)));
206 if (CONSTANT_P (x
) && GET_MODE (x
) == VOIDmode
207 && mode
!= TYPE_MODE (TREE_TYPE (src
)))
208 x
= convert_modes (mode
, TYPE_MODE (TREE_TYPE (src
)),
209 x
, TYPE_UNSIGNED (TREE_TYPE (src
)));
210 if (x
!= SA
.partition_to_pseudo
[dest
])
211 emit_move_insn (SA
.partition_to_pseudo
[dest
], x
);
215 insert_insn_on_edge (seq
, e
);
218 /* Insert a copy instruction from RTL expression SRC to partition DEST
222 insert_rtx_to_part_on_edge (edge e
, int dest
, rtx src
, int unsignedsrcp
)
225 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
228 "Inserting a temp copy on edge BB%d->BB%d : PART.%d = ",
230 e
->dest
->index
, dest
);
231 print_simple_rtl (dump_file
, src
);
232 fprintf (dump_file
, "\n");
235 gcc_assert (SA
.partition_to_pseudo
[dest
]);
236 set_location_for_edge (e
);
238 seq
= emit_partition_copy (SA
.partition_to_pseudo
[dest
],
242 insert_insn_on_edge (seq
, e
);
245 /* Insert a copy instruction from partition SRC to RTL lvalue DEST
249 insert_part_to_rtx_on_edge (edge e
, rtx dest
, int src
)
252 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
255 "Inserting a temp copy on edge BB%d->BB%d : ",
258 print_simple_rtl (dump_file
, dest
);
259 fprintf (dump_file
, "= PART.%d\n", src
);
262 gcc_assert (SA
.partition_to_pseudo
[src
]);
263 set_location_for_edge (e
);
265 seq
= emit_partition_copy (dest
,
266 SA
.partition_to_pseudo
[src
],
267 TYPE_UNSIGNED (TREE_TYPE (
268 partition_to_var (SA
.map
, src
))));
270 insert_insn_on_edge (seq
, e
);
274 /* Create an elimination graph with SIZE nodes and associated data
278 new_elim_graph (int size
)
280 elim_graph g
= (elim_graph
) xmalloc (sizeof (struct _elim_graph
));
282 g
->nodes
= VEC_alloc (int, heap
, 30);
283 g
->const_dests
= VEC_alloc (int, heap
, 20);
284 g
->const_copies
= VEC_alloc (tree
, heap
, 20);
285 g
->edge_list
= VEC_alloc (int, heap
, 20);
286 g
->stack
= VEC_alloc (int, heap
, 30);
288 g
->visited
= sbitmap_alloc (size
);
294 /* Empty elimination graph G. */
297 clear_elim_graph (elim_graph g
)
299 VEC_truncate (int, g
->nodes
, 0);
300 VEC_truncate (int, g
->edge_list
, 0);
304 /* Delete elimination graph G. */
307 delete_elim_graph (elim_graph g
)
309 sbitmap_free (g
->visited
);
310 VEC_free (int, heap
, g
->stack
);
311 VEC_free (int, heap
, g
->edge_list
);
312 VEC_free (tree
, heap
, g
->const_copies
);
313 VEC_free (int, heap
, g
->const_dests
);
314 VEC_free (int, heap
, g
->nodes
);
319 /* Return the number of nodes in graph G. */
322 elim_graph_size (elim_graph g
)
324 return VEC_length (int, g
->nodes
);
328 /* Add NODE to graph G, if it doesn't exist already. */
331 elim_graph_add_node (elim_graph g
, int node
)
336 for (x
= 0; VEC_iterate (int, g
->nodes
, x
, t
); x
++)
339 VEC_safe_push (int, heap
, g
->nodes
, node
);
343 /* Add the edge PRED->SUCC to graph G. */
346 elim_graph_add_edge (elim_graph g
, int pred
, int succ
)
348 VEC_safe_push (int, heap
, g
->edge_list
, pred
);
349 VEC_safe_push (int, heap
, g
->edge_list
, succ
);
353 /* Remove an edge from graph G for which NODE is the predecessor, and
354 return the successor node. -1 is returned if there is no such edge. */
357 elim_graph_remove_succ_edge (elim_graph g
, int node
)
361 for (x
= 0; x
< VEC_length (int, g
->edge_list
); x
+= 2)
362 if (VEC_index (int, g
->edge_list
, x
) == node
)
364 VEC_replace (int, g
->edge_list
, x
, -1);
365 y
= VEC_index (int, g
->edge_list
, x
+ 1);
366 VEC_replace (int, g
->edge_list
, x
+ 1, -1);
373 /* Find all the nodes in GRAPH which are successors to NODE in the
374 edge list. VAR will hold the partition number found. CODE is the
375 code fragment executed for every node found. */
377 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, CODE) \
381 for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2) \
383 y_ = VEC_index (int, (GRAPH)->edge_list, x_); \
386 (VAR) = VEC_index (int, (GRAPH)->edge_list, x_ + 1); \
392 /* Find all the nodes which are predecessors of NODE in the edge list for
393 GRAPH. VAR will hold the partition number found. CODE is the
394 code fragment executed for every node found. */
396 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, CODE) \
400 for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2) \
402 y_ = VEC_index (int, (GRAPH)->edge_list, x_ + 1); \
405 (VAR) = VEC_index (int, (GRAPH)->edge_list, x_); \
411 /* Add T to elimination graph G. */
414 eliminate_name (elim_graph g
, int T
)
416 elim_graph_add_node (g
, T
);
420 /* Build elimination graph G for basic block BB on incoming PHI edge
424 eliminate_build (elim_graph g
)
428 gimple_stmt_iterator gsi
;
430 clear_elim_graph (g
);
432 for (gsi
= gsi_start_phis (g
->e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
434 gimple phi
= gsi_stmt (gsi
);
436 p0
= var_to_partition (g
->map
, gimple_phi_result (phi
));
437 /* Ignore results which are not in partitions. */
438 if (p0
== NO_PARTITION
)
441 Ti
= PHI_ARG_DEF (phi
, g
->e
->dest_idx
);
443 /* If this argument is a constant, or a SSA_NAME which is being
444 left in SSA form, just queue a copy to be emitted on this
446 if (!phi_ssa_name_p (Ti
)
447 || (TREE_CODE (Ti
) == SSA_NAME
448 && var_to_partition (g
->map
, Ti
) == NO_PARTITION
))
450 /* Save constant copies until all other copies have been emitted
452 VEC_safe_push (int, heap
, g
->const_dests
, p0
);
453 VEC_safe_push (tree
, heap
, g
->const_copies
, Ti
);
457 pi
= var_to_partition (g
->map
, Ti
);
460 eliminate_name (g
, p0
);
461 eliminate_name (g
, pi
);
462 elim_graph_add_edge (g
, p0
, pi
);
469 /* Push successors of T onto the elimination stack for G. */
472 elim_forward (elim_graph g
, int T
)
475 SET_BIT (g
->visited
, T
);
476 FOR_EACH_ELIM_GRAPH_SUCC (g
, T
, S
,
478 if (!TEST_BIT (g
->visited
, S
))
481 VEC_safe_push (int, heap
, g
->stack
, T
);
485 /* Return 1 if there unvisited predecessors of T in graph G. */
488 elim_unvisited_predecessor (elim_graph g
, int T
)
491 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
,
493 if (!TEST_BIT (g
->visited
, P
))
499 /* Process predecessors first, and insert a copy. */
502 elim_backward (elim_graph g
, int T
)
505 SET_BIT (g
->visited
, T
);
506 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
,
508 if (!TEST_BIT (g
->visited
, P
))
510 elim_backward (g
, P
);
511 insert_partition_copy_on_edge (g
->e
, P
, T
);
516 /* Allocate a new pseudo register usable for storing values sitting
517 in NAME (a decl or SSA name), i.e. with matching mode and attributes. */
520 get_temp_reg (tree name
)
522 tree var
= TREE_CODE (name
) == SSA_NAME
? SSA_NAME_VAR (name
) : name
;
523 tree type
= TREE_TYPE (var
);
524 int unsignedp
= TYPE_UNSIGNED (type
);
525 enum machine_mode reg_mode
526 = promote_mode (type
, DECL_MODE (var
), &unsignedp
, 0);
527 rtx x
= gen_reg_rtx (reg_mode
);
528 if (POINTER_TYPE_P (type
))
529 mark_reg_pointer (x
, TYPE_ALIGN (TREE_TYPE (TREE_TYPE (var
))));
533 /* Insert required copies for T in graph G. Check for a strongly connected
534 region, and create a temporary to break the cycle if one is found. */
537 elim_create (elim_graph g
, int T
)
541 if (elim_unvisited_predecessor (g
, T
))
543 tree var
= partition_to_var (g
->map
, T
);
544 rtx U
= get_temp_reg (var
);
545 int unsignedsrcp
= TYPE_UNSIGNED (TREE_TYPE (var
));
547 insert_part_to_rtx_on_edge (g
->e
, U
, T
);
548 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
,
550 if (!TEST_BIT (g
->visited
, P
))
552 elim_backward (g
, P
);
553 insert_rtx_to_part_on_edge (g
->e
, P
, U
, unsignedsrcp
);
559 S
= elim_graph_remove_succ_edge (g
, T
);
562 SET_BIT (g
->visited
, T
);
563 insert_partition_copy_on_edge (g
->e
, T
, S
);
569 /* Eliminate all the phi nodes on edge E in graph G. */
572 eliminate_phi (edge e
, elim_graph g
)
576 gcc_assert (VEC_length (tree
, g
->const_copies
) == 0);
578 /* Abnormal edges already have everything coalesced. */
579 if (e
->flags
& EDGE_ABNORMAL
)
586 if (elim_graph_size (g
) != 0)
590 sbitmap_zero (g
->visited
);
591 VEC_truncate (int, g
->stack
, 0);
593 for (x
= 0; VEC_iterate (int, g
->nodes
, x
, part
); x
++)
595 if (!TEST_BIT (g
->visited
, part
))
596 elim_forward (g
, part
);
599 sbitmap_zero (g
->visited
);
600 while (VEC_length (int, g
->stack
) > 0)
602 x
= VEC_pop (int, g
->stack
);
603 if (!TEST_BIT (g
->visited
, x
))
608 /* If there are any pending constant copies, issue them now. */
609 while (VEC_length (tree
, g
->const_copies
) > 0)
613 src
= VEC_pop (tree
, g
->const_copies
);
614 dest
= VEC_pop (int, g
->const_dests
);
615 insert_value_copy_on_edge (e
, dest
, src
);
620 /* Remove each argument from PHI. If an arg was the last use of an SSA_NAME,
621 check to see if this allows another PHI node to be removed. */
624 remove_gimple_phi_args (gimple phi
)
629 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
631 fprintf (dump_file
, "Removing Dead PHI definition: ");
632 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
635 FOR_EACH_PHI_ARG (arg_p
, phi
, iter
, SSA_OP_USE
)
637 tree arg
= USE_FROM_PTR (arg_p
);
638 if (TREE_CODE (arg
) == SSA_NAME
)
640 /* Remove the reference to the existing argument. */
641 SET_USE (arg_p
, NULL_TREE
);
642 if (has_zero_uses (arg
))
645 gimple_stmt_iterator gsi
;
647 stmt
= SSA_NAME_DEF_STMT (arg
);
649 /* Also remove the def if it is a PHI node. */
650 if (gimple_code (stmt
) == GIMPLE_PHI
)
652 remove_gimple_phi_args (stmt
);
653 gsi
= gsi_for_stmt (stmt
);
654 remove_phi_node (&gsi
, true);
662 /* Remove any PHI node which is a virtual PHI, or a PHI with no uses. */
665 eliminate_useless_phis (void)
668 gimple_stmt_iterator gsi
;
673 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); )
675 gimple phi
= gsi_stmt (gsi
);
676 result
= gimple_phi_result (phi
);
677 if (!is_gimple_reg (SSA_NAME_VAR (result
)))
679 #ifdef ENABLE_CHECKING
681 /* There should be no arguments which are not virtual, or the
682 results will be incorrect. */
683 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
685 tree arg
= PHI_ARG_DEF (phi
, i
);
686 if (TREE_CODE (arg
) == SSA_NAME
687 && is_gimple_reg (SSA_NAME_VAR (arg
)))
689 fprintf (stderr
, "Argument of PHI is not virtual (");
690 print_generic_expr (stderr
, arg
, TDF_SLIM
);
691 fprintf (stderr
, "), but the result is :");
692 print_gimple_stmt (stderr
, phi
, 0, TDF_SLIM
);
693 internal_error ("SSA corruption");
697 remove_phi_node (&gsi
, true);
701 /* Also remove real PHIs with no uses. */
702 if (has_zero_uses (result
))
704 remove_gimple_phi_args (phi
);
705 remove_phi_node (&gsi
, true);
715 /* This function will rewrite the current program using the variable mapping
716 found in MAP. If the replacement vector VALUES is provided, any
717 occurrences of partitions with non-null entries in the vector will be
718 replaced with the expression in the vector instead of its mapped
722 rewrite_trees (var_map map ATTRIBUTE_UNUSED
)
724 #ifdef ENABLE_CHECKING
726 /* Search for PHIs where the destination has no partition, but one
727 or more arguments has a partition. This should not happen and can
728 create incorrect code. */
731 gimple_stmt_iterator gsi
;
732 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
734 gimple phi
= gsi_stmt (gsi
);
735 tree T0
= var_to_partition_to_var (map
, gimple_phi_result (phi
));
739 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
741 tree arg
= PHI_ARG_DEF (phi
, i
);
743 if (TREE_CODE (arg
) == SSA_NAME
744 && var_to_partition (map
, arg
) != NO_PARTITION
)
746 fprintf (stderr
, "Argument of PHI is in a partition :(");
747 print_generic_expr (stderr
, arg
, TDF_SLIM
);
748 fprintf (stderr
, "), but the result is not :");
749 print_gimple_stmt (stderr
, phi
, 0, TDF_SLIM
);
750 internal_error ("SSA corruption");
759 /* Given the out-of-ssa info object SA (with prepared partitions)
760 eliminate all phi nodes in all basic blocks. Afterwards no
761 basic block will have phi nodes anymore and there are possibly
762 some RTL instructions inserted on edges. */
765 expand_phi_nodes (struct ssaexpand
*sa
)
768 elim_graph g
= new_elim_graph (sa
->map
->num_partitions
);
771 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
, EXIT_BLOCK_PTR
, next_bb
)
772 if (!gimple_seq_empty_p (phi_nodes (bb
)))
776 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
777 eliminate_phi (e
, g
);
778 set_phi_nodes (bb
, NULL
);
779 /* We can't redirect EH edges in RTL land, so we need to do this
780 here. Redirection happens only when splitting is necessary,
781 which it is only for critical edges, normally. For EH edges
782 it might also be necessary when the successor has more than
783 one predecessor. In that case the edge is either required to
784 be fallthru (which EH edges aren't), or the predecessor needs
785 to end with a jump (which again, isn't the case with EH edges).
786 Hence, split all EH edges on which we inserted instructions
787 and whose successor has multiple predecessors. */
788 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
790 if (e
->insns
.r
&& (e
->flags
& EDGE_EH
)
791 && !single_pred_p (e
->dest
))
793 rtx insns
= e
->insns
.r
;
795 e
->insns
.r
= NULL_RTX
;
797 single_pred_edge (bb
)->insns
.r
= insns
;
804 delete_elim_graph (g
);
808 /* Remove the ssa-names in the current function and translate them into normal
809 compiler variables. PERFORM_TER is true if Temporary Expression Replacement
810 should also be used. */
813 remove_ssa_form (bool perform_ter
, struct ssaexpand
*sa
)
815 bitmap values
= NULL
;
819 map
= coalesce_ssa_name ();
821 /* Return to viewing the variable list as just all reference variables after
822 coalescing has been performed. */
823 partition_view_normal (map
, false);
825 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
827 fprintf (dump_file
, "After Coalescing:\n");
828 dump_var_map (dump_file
, map
);
833 values
= find_replaceable_exprs (map
);
834 if (values
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
835 dump_replaceable_exprs (dump_file
, values
);
842 sa
->partition_has_default_def
= BITMAP_ALLOC (NULL
);
843 for (i
= 1; i
< num_ssa_names
; i
++)
845 tree t
= ssa_name (i
);
846 if (t
&& SSA_NAME_IS_DEFAULT_DEF (t
))
848 int p
= var_to_partition (map
, t
);
849 if (p
!= NO_PARTITION
)
850 bitmap_set_bit (sa
->partition_has_default_def
, p
);
856 /* If not already done so for basic block BB, assign increasing uids
857 to each of its instructions. */
860 maybe_renumber_stmts_bb (basic_block bb
)
863 gimple_stmt_iterator gsi
;
868 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
870 gimple stmt
= gsi_stmt (gsi
);
871 gimple_set_uid (stmt
, i
);
877 /* Return true if we can determine that the SSA_NAMEs RESULT (a result
878 of a PHI node) and ARG (one of its arguments) conflict. Return false
879 otherwise, also when we simply aren't sure. */
882 trivially_conflicts_p (basic_block bb
, tree result
, tree arg
)
885 imm_use_iterator imm_iter
;
886 gimple defa
= SSA_NAME_DEF_STMT (arg
);
888 /* If ARG isn't defined in the same block it's too complicated for
890 if (gimple_bb (defa
) != bb
)
893 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, result
)
895 gimple use_stmt
= USE_STMT (use
);
896 /* Now, if there's a use of RESULT that lies outside this basic block,
897 then there surely is a conflict with ARG. */
898 if (gimple_bb (use_stmt
) != bb
)
900 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
902 /* The use now is in a real stmt of BB, so if ARG was defined
903 in a PHI node (like RESULT) both conflict. */
904 if (gimple_code (defa
) == GIMPLE_PHI
)
906 maybe_renumber_stmts_bb (bb
);
907 /* If the use of RESULT occurs after the definition of ARG,
908 the two conflict too. */
909 if (gimple_uid (defa
) < gimple_uid (use_stmt
))
917 /* Search every PHI node for arguments associated with backedges which
918 we can trivially determine will need a copy (the argument is either
919 not an SSA_NAME or the argument has a different underlying variable
920 than the PHI result).
922 Insert a copy from the PHI argument to a new destination at the
923 end of the block with the backedge to the top of the loop. Update
924 the PHI argument to reference this new destination. */
927 insert_backedge_copies (void)
930 gimple_stmt_iterator gsi
;
934 /* Mark block as possibly needing calculation of UIDs. */
937 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
939 gimple phi
= gsi_stmt (gsi
);
940 tree result
= gimple_phi_result (phi
);
944 if (!is_gimple_reg (result
))
947 result_var
= SSA_NAME_VAR (result
);
948 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
950 tree arg
= gimple_phi_arg_def (phi
, i
);
951 edge e
= gimple_phi_arg_edge (phi
, i
);
953 /* If the argument is not an SSA_NAME, then we will need a
954 constant initialization. If the argument is an SSA_NAME with
955 a different underlying variable then a copy statement will be
957 if ((e
->flags
& EDGE_DFS_BACK
)
958 && (TREE_CODE (arg
) != SSA_NAME
959 || SSA_NAME_VAR (arg
) != result_var
960 || trivially_conflicts_p (bb
, result
, arg
)))
963 gimple stmt
, last
= NULL
;
964 gimple_stmt_iterator gsi2
;
966 gsi2
= gsi_last_bb (gimple_phi_arg_edge (phi
, i
)->src
);
967 if (!gsi_end_p (gsi2
))
968 last
= gsi_stmt (gsi2
);
970 /* In theory the only way we ought to get back to the
971 start of a loop should be with a COND_EXPR or GOTO_EXPR.
972 However, better safe than sorry.
973 If the block ends with a control statement or
974 something that might throw, then we have to
975 insert this assignment before the last
976 statement. Else insert it after the last statement. */
977 if (last
&& stmt_ends_bb_p (last
))
979 /* If the last statement in the block is the definition
980 site of the PHI argument, then we can't insert
981 anything after it. */
982 if (TREE_CODE (arg
) == SSA_NAME
983 && SSA_NAME_DEF_STMT (arg
) == last
)
987 /* Create a new instance of the underlying variable of the
989 stmt
= gimple_build_assign (result_var
,
990 gimple_phi_arg_def (phi
, i
));
991 name
= make_ssa_name (result_var
, stmt
);
992 gimple_assign_set_lhs (stmt
, name
);
994 /* Insert the new statement into the block and update
996 if (last
&& stmt_ends_bb_p (last
))
997 gsi_insert_before (&gsi2
, stmt
, GSI_NEW_STMT
);
999 gsi_insert_after (&gsi2
, stmt
, GSI_NEW_STMT
);
1000 SET_PHI_ARG_DEF (phi
, i
, name
);
1005 /* Unmark this block again. */
1010 /* Free all memory associated with going out of SSA form. SA is
1011 the outof-SSA info object. */
1014 finish_out_of_ssa (struct ssaexpand
*sa
)
1016 free (sa
->partition_to_pseudo
);
1018 BITMAP_FREE (sa
->values
);
1019 delete_var_map (sa
->map
);
1020 BITMAP_FREE (sa
->partition_has_default_def
);
1021 memset (sa
, 0, sizeof *sa
);
1024 /* Take the current function out of SSA form, translating PHIs as described in
1025 R. Morgan, ``Building an Optimizing Compiler'',
1026 Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */
1029 rewrite_out_of_ssa (struct ssaexpand
*sa
)
1031 /* If elimination of a PHI requires inserting a copy on a backedge,
1032 then we will have to split the backedge which has numerous
1033 undesirable performance effects.
1035 A significant number of such cases can be handled here by inserting
1036 copies into the loop itself. */
1037 insert_backedge_copies ();
1040 /* Eliminate PHIs which are of no use, such as virtual or dead phis. */
1041 eliminate_useless_phis ();
1043 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1044 gimple_dump_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);
1046 remove_ssa_form (flag_tree_ter
, sa
);
1048 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1049 gimple_dump_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);