1 /* Convert a program in SSA form into Normal form.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
3 Free Software Foundation, Inc.
4 Contributed by Andrew Macleod <amacleod@redhat.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
28 #include "basic-block.h"
29 #include "diagnostic.h"
31 #include "tree-flow.h"
33 #include "tree-dump.h"
34 #include "tree-pass.h"
37 #include "ssaexpand.h"
40 DEF_VEC_I(source_location
);
41 DEF_VEC_ALLOC_I(source_location
,heap
);
43 /* Used to hold all the components required to do SSA PHI elimination.
44 The node and pred/succ list is a simple linear list of nodes and
45 edges represented as pairs of nodes.
47 The predecessor and successor list: Nodes are entered in pairs, where
48 [0] ->PRED, [1]->SUCC. All the even indexes in the array represent
49 predecessors, all the odd elements are successors.
52 When implemented as bitmaps, very large programs SSA->Normal times were
53 being dominated by clearing the interference graph.
55 Typically this list of edges is extremely small since it only includes
56 PHI results and uses from a single edge which have not coalesced with
57 each other. This means that no virtual PHI nodes are included, and
58 empirical evidence suggests that the number of edges rarely exceed
59 3, and in a bootstrap of GCC, the maximum size encountered was 7.
60 This also limits the number of possible nodes that are involved to
61 rarely more than 6, and in the bootstrap of gcc, the maximum number
62 of nodes encountered was 12. */
64 typedef struct _elim_graph
{
65 /* Size of the elimination vectors. */
68 /* List of nodes in the elimination graph. */
71 /* The predecessor and successor edge list. */
72 VEC(int,heap
) *edge_list
;
74 /* Source locus on each edge */
75 VEC(source_location
,heap
) *edge_locus
;
80 /* Stack for visited nodes. */
83 /* The variable partition map. */
86 /* Edge being eliminated by this graph. */
89 /* List of constant copies to emit. These are pushed on in pairs. */
90 VEC(int,heap
) *const_dests
;
91 VEC(tree
,heap
) *const_copies
;
93 /* Source locations for any constant copies. */
94 VEC(source_location
,heap
) *copy_locus
;
98 /* For an edge E find out a good source location to associate with
99 instructions inserted on edge E. If E has an implicit goto set,
100 use its location. Otherwise search instructions in predecessors
101 of E for a location, and use that one. That makes sense because
102 we insert on edges for PHI nodes, and effects of PHIs happen on
103 the end of the predecessor conceptually. */
106 set_location_for_edge (edge e
)
110 set_curr_insn_source_location (e
->goto_locus
);
111 set_curr_insn_block (e
->goto_block
);
115 basic_block bb
= e
->src
;
116 gimple_stmt_iterator gsi
;
120 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
122 gimple stmt
= gsi_stmt (gsi
);
123 if (is_gimple_debug (stmt
))
125 if (gimple_has_location (stmt
) || gimple_block (stmt
))
127 set_curr_insn_source_location (gimple_location (stmt
));
128 set_curr_insn_block (gimple_block (stmt
));
132 /* Nothing found in this basic block. Make a half-assed attempt
133 to continue with another block. */
134 if (single_pred_p (bb
))
135 bb
= single_pred (bb
);
139 while (bb
!= e
->src
);
143 /* Emit insns to copy SRC into DEST converting SRC if necessary. */
146 emit_partition_copy (rtx dest
, rtx src
, int unsignedsrcp
)
152 if (GET_MODE (src
) != VOIDmode
&& GET_MODE (src
) != GET_MODE (dest
))
153 src
= convert_to_mode (GET_MODE (dest
), src
, unsignedsrcp
);
154 emit_move_insn (dest
, src
);
162 /* Insert a copy instruction from partition SRC to DEST onto edge E. */
165 insert_partition_copy_on_edge (edge e
, int dest
, int src
, source_location locus
)
168 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
171 "Inserting a partition copy on edge BB%d->BB%d :"
174 e
->dest
->index
, dest
, src
);
175 fprintf (dump_file
, "\n");
178 gcc_assert (SA
.partition_to_pseudo
[dest
]);
179 gcc_assert (SA
.partition_to_pseudo
[src
]);
181 set_location_for_edge (e
);
182 /* If a locus is provided, override the default. */
184 set_curr_insn_source_location (locus
);
186 seq
= emit_partition_copy (SA
.partition_to_pseudo
[dest
],
187 SA
.partition_to_pseudo
[src
],
188 TYPE_UNSIGNED (TREE_TYPE (
189 partition_to_var (SA
.map
, src
))));
191 insert_insn_on_edge (seq
, e
);
194 /* Insert a copy instruction from expression SRC to partition DEST
198 insert_value_copy_on_edge (edge e
, int dest
, tree src
, source_location locus
)
201 enum machine_mode dest_mode
, src_mode
;
205 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
208 "Inserting a value copy on edge BB%d->BB%d : PART.%d = ",
210 e
->dest
->index
, dest
);
211 print_generic_expr (dump_file
, src
, TDF_SLIM
);
212 fprintf (dump_file
, "\n");
215 gcc_assert (SA
.partition_to_pseudo
[dest
]);
217 set_location_for_edge (e
);
218 /* If a locus is provided, override the default. */
220 set_curr_insn_source_location (locus
);
224 var
= SSA_NAME_VAR (partition_to_var (SA
.map
, dest
));
225 src_mode
= TYPE_MODE (TREE_TYPE (src
));
226 dest_mode
= promote_decl_mode (var
, &unsignedp
);
227 gcc_assert (src_mode
== TYPE_MODE (TREE_TYPE (var
)));
228 gcc_assert (dest_mode
== GET_MODE (SA
.partition_to_pseudo
[dest
]));
230 if (src_mode
!= dest_mode
)
232 x
= expand_expr (src
, NULL
, src_mode
, EXPAND_NORMAL
);
233 x
= convert_modes (dest_mode
, src_mode
, x
, unsignedp
);
236 x
= expand_expr (src
, SA
.partition_to_pseudo
[dest
],
237 dest_mode
, EXPAND_NORMAL
);
239 if (x
!= SA
.partition_to_pseudo
[dest
])
240 emit_move_insn (SA
.partition_to_pseudo
[dest
], x
);
244 insert_insn_on_edge (seq
, e
);
247 /* Insert a copy instruction from RTL expression SRC to partition DEST
251 insert_rtx_to_part_on_edge (edge e
, int dest
, rtx src
, int unsignedsrcp
,
252 source_location locus
)
255 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
258 "Inserting a temp copy on edge BB%d->BB%d : PART.%d = ",
260 e
->dest
->index
, dest
);
261 print_simple_rtl (dump_file
, src
);
262 fprintf (dump_file
, "\n");
265 gcc_assert (SA
.partition_to_pseudo
[dest
]);
267 set_location_for_edge (e
);
268 /* If a locus is provided, override the default. */
270 set_curr_insn_source_location (locus
);
272 seq
= emit_partition_copy (SA
.partition_to_pseudo
[dest
],
276 insert_insn_on_edge (seq
, e
);
279 /* Insert a copy instruction from partition SRC to RTL lvalue DEST
283 insert_part_to_rtx_on_edge (edge e
, rtx dest
, int src
, source_location locus
)
286 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
289 "Inserting a temp copy on edge BB%d->BB%d : ",
292 print_simple_rtl (dump_file
, dest
);
293 fprintf (dump_file
, "= PART.%d\n", src
);
296 gcc_assert (SA
.partition_to_pseudo
[src
]);
298 set_location_for_edge (e
);
299 /* If a locus is provided, override the default. */
301 set_curr_insn_source_location (locus
);
303 seq
= emit_partition_copy (dest
,
304 SA
.partition_to_pseudo
[src
],
305 TYPE_UNSIGNED (TREE_TYPE (
306 partition_to_var (SA
.map
, src
))));
308 insert_insn_on_edge (seq
, e
);
312 /* Create an elimination graph with SIZE nodes and associated data
316 new_elim_graph (int size
)
318 elim_graph g
= (elim_graph
) xmalloc (sizeof (struct _elim_graph
));
320 g
->nodes
= VEC_alloc (int, heap
, 30);
321 g
->const_dests
= VEC_alloc (int, heap
, 20);
322 g
->const_copies
= VEC_alloc (tree
, heap
, 20);
323 g
->copy_locus
= VEC_alloc (source_location
, heap
, 10);
324 g
->edge_list
= VEC_alloc (int, heap
, 20);
325 g
->edge_locus
= VEC_alloc (source_location
, heap
, 10);
326 g
->stack
= VEC_alloc (int, heap
, 30);
328 g
->visited
= sbitmap_alloc (size
);
334 /* Empty elimination graph G. */
337 clear_elim_graph (elim_graph g
)
339 VEC_truncate (int, g
->nodes
, 0);
340 VEC_truncate (int, g
->edge_list
, 0);
341 VEC_truncate (source_location
, g
->edge_locus
, 0);
345 /* Delete elimination graph G. */
348 delete_elim_graph (elim_graph g
)
350 sbitmap_free (g
->visited
);
351 VEC_free (int, heap
, g
->stack
);
352 VEC_free (int, heap
, g
->edge_list
);
353 VEC_free (tree
, heap
, g
->const_copies
);
354 VEC_free (int, heap
, g
->const_dests
);
355 VEC_free (int, heap
, g
->nodes
);
356 VEC_free (source_location
, heap
, g
->copy_locus
);
357 VEC_free (source_location
, heap
, g
->edge_locus
);
363 /* Return the number of nodes in graph G. */
366 elim_graph_size (elim_graph g
)
368 return VEC_length (int, g
->nodes
);
372 /* Add NODE to graph G, if it doesn't exist already. */
375 elim_graph_add_node (elim_graph g
, int node
)
380 for (x
= 0; VEC_iterate (int, g
->nodes
, x
, t
); x
++)
383 VEC_safe_push (int, heap
, g
->nodes
, node
);
387 /* Add the edge PRED->SUCC to graph G. */
390 elim_graph_add_edge (elim_graph g
, int pred
, int succ
, source_location locus
)
392 VEC_safe_push (int, heap
, g
->edge_list
, pred
);
393 VEC_safe_push (int, heap
, g
->edge_list
, succ
);
394 VEC_safe_push (source_location
, heap
, g
->edge_locus
, locus
);
398 /* Remove an edge from graph G for which NODE is the predecessor, and
399 return the successor node. -1 is returned if there is no such edge. */
402 elim_graph_remove_succ_edge (elim_graph g
, int node
, source_location
*locus
)
406 for (x
= 0; x
< VEC_length (int, g
->edge_list
); x
+= 2)
407 if (VEC_index (int, g
->edge_list
, x
) == node
)
409 VEC_replace (int, g
->edge_list
, x
, -1);
410 y
= VEC_index (int, g
->edge_list
, x
+ 1);
411 VEC_replace (int, g
->edge_list
, x
+ 1, -1);
412 *locus
= VEC_index (source_location
, g
->edge_locus
, x
/ 2);
413 VEC_replace (source_location
, g
->edge_locus
, x
/ 2, UNKNOWN_LOCATION
);
416 *locus
= UNKNOWN_LOCATION
;
421 /* Find all the nodes in GRAPH which are successors to NODE in the
422 edge list. VAR will hold the partition number found. CODE is the
423 code fragment executed for every node found. */
425 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, LOCUS, CODE) \
429 for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2) \
431 y_ = VEC_index (int, (GRAPH)->edge_list, x_); \
434 (VAR) = VEC_index (int, (GRAPH)->edge_list, x_ + 1); \
435 (LOCUS) = VEC_index (source_location, (GRAPH)->edge_locus, x_ / 2); \
441 /* Find all the nodes which are predecessors of NODE in the edge list for
442 GRAPH. VAR will hold the partition number found. CODE is the
443 code fragment executed for every node found. */
445 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, LOCUS, CODE) \
449 for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2) \
451 y_ = VEC_index (int, (GRAPH)->edge_list, x_ + 1); \
454 (VAR) = VEC_index (int, (GRAPH)->edge_list, x_); \
455 (LOCUS) = VEC_index (source_location, (GRAPH)->edge_locus, x_ / 2); \
461 /* Add T to elimination graph G. */
464 eliminate_name (elim_graph g
, int T
)
466 elim_graph_add_node (g
, T
);
470 /* Build elimination graph G for basic block BB on incoming PHI edge
474 eliminate_build (elim_graph g
)
478 gimple_stmt_iterator gsi
;
480 clear_elim_graph (g
);
482 for (gsi
= gsi_start_phis (g
->e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
484 gimple phi
= gsi_stmt (gsi
);
485 source_location locus
;
487 p0
= var_to_partition (g
->map
, gimple_phi_result (phi
));
488 /* Ignore results which are not in partitions. */
489 if (p0
== NO_PARTITION
)
492 Ti
= PHI_ARG_DEF (phi
, g
->e
->dest_idx
);
493 locus
= gimple_phi_arg_location_from_edge (phi
, g
->e
);
495 /* If this argument is a constant, or a SSA_NAME which is being
496 left in SSA form, just queue a copy to be emitted on this
498 if (!phi_ssa_name_p (Ti
)
499 || (TREE_CODE (Ti
) == SSA_NAME
500 && var_to_partition (g
->map
, Ti
) == NO_PARTITION
))
502 /* Save constant copies until all other copies have been emitted
504 VEC_safe_push (int, heap
, g
->const_dests
, p0
);
505 VEC_safe_push (tree
, heap
, g
->const_copies
, Ti
);
506 VEC_safe_push (source_location
, heap
, g
->copy_locus
, locus
);
510 pi
= var_to_partition (g
->map
, Ti
);
513 eliminate_name (g
, p0
);
514 eliminate_name (g
, pi
);
515 elim_graph_add_edge (g
, p0
, pi
, locus
);
522 /* Push successors of T onto the elimination stack for G. */
525 elim_forward (elim_graph g
, int T
)
528 source_location locus
;
530 SET_BIT (g
->visited
, T
);
531 FOR_EACH_ELIM_GRAPH_SUCC (g
, T
, S
, locus
,
533 if (!TEST_BIT (g
->visited
, S
))
536 VEC_safe_push (int, heap
, g
->stack
, T
);
540 /* Return 1 if there unvisited predecessors of T in graph G. */
543 elim_unvisited_predecessor (elim_graph g
, int T
)
546 source_location locus
;
548 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
550 if (!TEST_BIT (g
->visited
, P
))
556 /* Process predecessors first, and insert a copy. */
559 elim_backward (elim_graph g
, int T
)
562 source_location locus
;
564 SET_BIT (g
->visited
, T
);
565 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
567 if (!TEST_BIT (g
->visited
, P
))
569 elim_backward (g
, P
);
570 insert_partition_copy_on_edge (g
->e
, P
, T
, locus
);
575 /* Allocate a new pseudo register usable for storing values sitting
576 in NAME (a decl or SSA name), i.e. with matching mode and attributes. */
579 get_temp_reg (tree name
)
581 tree var
= TREE_CODE (name
) == SSA_NAME
? SSA_NAME_VAR (name
) : name
;
582 tree type
= TREE_TYPE (var
);
584 enum machine_mode reg_mode
= promote_decl_mode (var
, &unsignedp
);
585 rtx x
= gen_reg_rtx (reg_mode
);
586 if (POINTER_TYPE_P (type
))
587 mark_reg_pointer (x
, TYPE_ALIGN (TREE_TYPE (TREE_TYPE (var
))));
591 /* Insert required copies for T in graph G. Check for a strongly connected
592 region, and create a temporary to break the cycle if one is found. */
595 elim_create (elim_graph g
, int T
)
598 source_location locus
;
600 if (elim_unvisited_predecessor (g
, T
))
602 tree var
= partition_to_var (g
->map
, T
);
603 rtx U
= get_temp_reg (var
);
604 int unsignedsrcp
= TYPE_UNSIGNED (TREE_TYPE (var
));
606 insert_part_to_rtx_on_edge (g
->e
, U
, T
, UNKNOWN_LOCATION
);
607 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
609 if (!TEST_BIT (g
->visited
, P
))
611 elim_backward (g
, P
);
612 insert_rtx_to_part_on_edge (g
->e
, P
, U
, unsignedsrcp
, locus
);
618 S
= elim_graph_remove_succ_edge (g
, T
, &locus
);
621 SET_BIT (g
->visited
, T
);
622 insert_partition_copy_on_edge (g
->e
, T
, S
, locus
);
628 /* Eliminate all the phi nodes on edge E in graph G. */
631 eliminate_phi (edge e
, elim_graph g
)
635 gcc_assert (VEC_length (tree
, g
->const_copies
) == 0);
636 gcc_assert (VEC_length (source_location
, g
->copy_locus
) == 0);
638 /* Abnormal edges already have everything coalesced. */
639 if (e
->flags
& EDGE_ABNORMAL
)
646 if (elim_graph_size (g
) != 0)
650 sbitmap_zero (g
->visited
);
651 VEC_truncate (int, g
->stack
, 0);
653 for (x
= 0; VEC_iterate (int, g
->nodes
, x
, part
); x
++)
655 if (!TEST_BIT (g
->visited
, part
))
656 elim_forward (g
, part
);
659 sbitmap_zero (g
->visited
);
660 while (VEC_length (int, g
->stack
) > 0)
662 x
= VEC_pop (int, g
->stack
);
663 if (!TEST_BIT (g
->visited
, x
))
668 /* If there are any pending constant copies, issue them now. */
669 while (VEC_length (tree
, g
->const_copies
) > 0)
673 source_location locus
;
675 src
= VEC_pop (tree
, g
->const_copies
);
676 dest
= VEC_pop (int, g
->const_dests
);
677 locus
= VEC_pop (source_location
, g
->copy_locus
);
678 insert_value_copy_on_edge (e
, dest
, src
, locus
);
683 /* Remove each argument from PHI. If an arg was the last use of an SSA_NAME,
684 check to see if this allows another PHI node to be removed. */
687 remove_gimple_phi_args (gimple phi
)
692 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
694 fprintf (dump_file
, "Removing Dead PHI definition: ");
695 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
698 FOR_EACH_PHI_ARG (arg_p
, phi
, iter
, SSA_OP_USE
)
700 tree arg
= USE_FROM_PTR (arg_p
);
701 if (TREE_CODE (arg
) == SSA_NAME
)
703 /* Remove the reference to the existing argument. */
704 SET_USE (arg_p
, NULL_TREE
);
705 if (has_zero_uses (arg
))
708 gimple_stmt_iterator gsi
;
710 stmt
= SSA_NAME_DEF_STMT (arg
);
712 /* Also remove the def if it is a PHI node. */
713 if (gimple_code (stmt
) == GIMPLE_PHI
)
715 remove_gimple_phi_args (stmt
);
716 gsi
= gsi_for_stmt (stmt
);
717 remove_phi_node (&gsi
, true);
725 /* Remove any PHI node which is a virtual PHI, or a PHI with no uses. */
728 eliminate_useless_phis (void)
731 gimple_stmt_iterator gsi
;
736 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); )
738 gimple phi
= gsi_stmt (gsi
);
739 result
= gimple_phi_result (phi
);
740 if (!is_gimple_reg (SSA_NAME_VAR (result
)))
742 #ifdef ENABLE_CHECKING
744 /* There should be no arguments which are not virtual, or the
745 results will be incorrect. */
746 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
748 tree arg
= PHI_ARG_DEF (phi
, i
);
749 if (TREE_CODE (arg
) == SSA_NAME
750 && is_gimple_reg (SSA_NAME_VAR (arg
)))
752 fprintf (stderr
, "Argument of PHI is not virtual (");
753 print_generic_expr (stderr
, arg
, TDF_SLIM
);
754 fprintf (stderr
, "), but the result is :");
755 print_gimple_stmt (stderr
, phi
, 0, TDF_SLIM
);
756 internal_error ("SSA corruption");
760 remove_phi_node (&gsi
, true);
764 /* Also remove real PHIs with no uses. */
765 if (has_zero_uses (result
))
767 remove_gimple_phi_args (phi
);
768 remove_phi_node (&gsi
, true);
778 /* This function will rewrite the current program using the variable mapping
779 found in MAP. If the replacement vector VALUES is provided, any
780 occurrences of partitions with non-null entries in the vector will be
781 replaced with the expression in the vector instead of its mapped
785 rewrite_trees (var_map map ATTRIBUTE_UNUSED
)
787 #ifdef ENABLE_CHECKING
789 /* Search for PHIs where the destination has no partition, but one
790 or more arguments has a partition. This should not happen and can
791 create incorrect code. */
794 gimple_stmt_iterator gsi
;
795 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
797 gimple phi
= gsi_stmt (gsi
);
798 tree T0
= var_to_partition_to_var (map
, gimple_phi_result (phi
));
802 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
804 tree arg
= PHI_ARG_DEF (phi
, i
);
806 if (TREE_CODE (arg
) == SSA_NAME
807 && var_to_partition (map
, arg
) != NO_PARTITION
)
809 fprintf (stderr
, "Argument of PHI is in a partition :(");
810 print_generic_expr (stderr
, arg
, TDF_SLIM
);
811 fprintf (stderr
, "), but the result is not :");
812 print_gimple_stmt (stderr
, phi
, 0, TDF_SLIM
);
813 internal_error ("SSA corruption");
822 /* Given the out-of-ssa info object SA (with prepared partitions)
823 eliminate all phi nodes in all basic blocks. Afterwards no
824 basic block will have phi nodes anymore and there are possibly
825 some RTL instructions inserted on edges. */
828 expand_phi_nodes (struct ssaexpand
*sa
)
831 elim_graph g
= new_elim_graph (sa
->map
->num_partitions
);
834 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
, EXIT_BLOCK_PTR
, next_bb
)
835 if (!gimple_seq_empty_p (phi_nodes (bb
)))
839 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
840 eliminate_phi (e
, g
);
841 set_phi_nodes (bb
, NULL
);
842 /* We can't redirect EH edges in RTL land, so we need to do this
843 here. Redirection happens only when splitting is necessary,
844 which it is only for critical edges, normally. For EH edges
845 it might also be necessary when the successor has more than
846 one predecessor. In that case the edge is either required to
847 be fallthru (which EH edges aren't), or the predecessor needs
848 to end with a jump (which again, isn't the case with EH edges).
849 Hence, split all EH edges on which we inserted instructions
850 and whose successor has multiple predecessors. */
851 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
853 if (e
->insns
.r
&& (e
->flags
& EDGE_EH
)
854 && !single_pred_p (e
->dest
))
856 rtx insns
= e
->insns
.r
;
858 e
->insns
.r
= NULL_RTX
;
860 single_pred_edge (bb
)->insns
.r
= insns
;
867 delete_elim_graph (g
);
871 /* Remove the ssa-names in the current function and translate them into normal
872 compiler variables. PERFORM_TER is true if Temporary Expression Replacement
873 should also be used. */
876 remove_ssa_form (bool perform_ter
, struct ssaexpand
*sa
)
878 bitmap values
= NULL
;
882 map
= coalesce_ssa_name ();
884 /* Return to viewing the variable list as just all reference variables after
885 coalescing has been performed. */
886 partition_view_normal (map
, false);
888 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
890 fprintf (dump_file
, "After Coalescing:\n");
891 dump_var_map (dump_file
, map
);
896 values
= find_replaceable_exprs (map
);
897 if (values
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
898 dump_replaceable_exprs (dump_file
, values
);
905 sa
->partition_has_default_def
= BITMAP_ALLOC (NULL
);
906 for (i
= 1; i
< num_ssa_names
; i
++)
908 tree t
= ssa_name (i
);
909 if (t
&& SSA_NAME_IS_DEFAULT_DEF (t
))
911 int p
= var_to_partition (map
, t
);
912 if (p
!= NO_PARTITION
)
913 bitmap_set_bit (sa
->partition_has_default_def
, p
);
919 /* If not already done so for basic block BB, assign increasing uids
920 to each of its instructions. */
923 maybe_renumber_stmts_bb (basic_block bb
)
926 gimple_stmt_iterator gsi
;
931 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
933 gimple stmt
= gsi_stmt (gsi
);
934 gimple_set_uid (stmt
, i
);
940 /* Return true if we can determine that the SSA_NAMEs RESULT (a result
941 of a PHI node) and ARG (one of its arguments) conflict. Return false
942 otherwise, also when we simply aren't sure. */
945 trivially_conflicts_p (basic_block bb
, tree result
, tree arg
)
948 imm_use_iterator imm_iter
;
949 gimple defa
= SSA_NAME_DEF_STMT (arg
);
951 /* If ARG isn't defined in the same block it's too complicated for
953 if (gimple_bb (defa
) != bb
)
956 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, result
)
958 gimple use_stmt
= USE_STMT (use
);
959 /* Now, if there's a use of RESULT that lies outside this basic block,
960 then there surely is a conflict with ARG. */
961 if (gimple_bb (use_stmt
) != bb
)
963 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
965 /* The use now is in a real stmt of BB, so if ARG was defined
966 in a PHI node (like RESULT) both conflict. */
967 if (gimple_code (defa
) == GIMPLE_PHI
)
969 maybe_renumber_stmts_bb (bb
);
970 /* If the use of RESULT occurs after the definition of ARG,
971 the two conflict too. */
972 if (gimple_uid (defa
) < gimple_uid (use_stmt
))
980 /* Search every PHI node for arguments associated with backedges which
981 we can trivially determine will need a copy (the argument is either
982 not an SSA_NAME or the argument has a different underlying variable
983 than the PHI result).
985 Insert a copy from the PHI argument to a new destination at the
986 end of the block with the backedge to the top of the loop. Update
987 the PHI argument to reference this new destination. */
990 insert_backedge_copies (void)
993 gimple_stmt_iterator gsi
;
997 /* Mark block as possibly needing calculation of UIDs. */
1000 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1002 gimple phi
= gsi_stmt (gsi
);
1003 tree result
= gimple_phi_result (phi
);
1007 if (!is_gimple_reg (result
))
1010 result_var
= SSA_NAME_VAR (result
);
1011 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1013 tree arg
= gimple_phi_arg_def (phi
, i
);
1014 edge e
= gimple_phi_arg_edge (phi
, i
);
1016 /* If the argument is not an SSA_NAME, then we will need a
1017 constant initialization. If the argument is an SSA_NAME with
1018 a different underlying variable then a copy statement will be
1020 if ((e
->flags
& EDGE_DFS_BACK
)
1021 && (TREE_CODE (arg
) != SSA_NAME
1022 || SSA_NAME_VAR (arg
) != result_var
1023 || trivially_conflicts_p (bb
, result
, arg
)))
1026 gimple stmt
, last
= NULL
;
1027 gimple_stmt_iterator gsi2
;
1029 gsi2
= gsi_last_bb (gimple_phi_arg_edge (phi
, i
)->src
);
1030 if (!gsi_end_p (gsi2
))
1031 last
= gsi_stmt (gsi2
);
1033 /* In theory the only way we ought to get back to the
1034 start of a loop should be with a COND_EXPR or GOTO_EXPR.
1035 However, better safe than sorry.
1036 If the block ends with a control statement or
1037 something that might throw, then we have to
1038 insert this assignment before the last
1039 statement. Else insert it after the last statement. */
1040 if (last
&& stmt_ends_bb_p (last
))
1042 /* If the last statement in the block is the definition
1043 site of the PHI argument, then we can't insert
1044 anything after it. */
1045 if (TREE_CODE (arg
) == SSA_NAME
1046 && SSA_NAME_DEF_STMT (arg
) == last
)
1050 /* Create a new instance of the underlying variable of the
1052 stmt
= gimple_build_assign (result_var
,
1053 gimple_phi_arg_def (phi
, i
));
1054 name
= make_ssa_name (result_var
, stmt
);
1055 gimple_assign_set_lhs (stmt
, name
);
1057 /* copy location if present. */
1058 if (gimple_phi_arg_has_location (phi
, i
))
1059 gimple_set_location (stmt
,
1060 gimple_phi_arg_location (phi
, i
));
1062 /* Insert the new statement into the block and update
1064 if (last
&& stmt_ends_bb_p (last
))
1065 gsi_insert_before (&gsi2
, stmt
, GSI_NEW_STMT
);
1067 gsi_insert_after (&gsi2
, stmt
, GSI_NEW_STMT
);
1068 SET_PHI_ARG_DEF (phi
, i
, name
);
1073 /* Unmark this block again. */
1078 /* Free all memory associated with going out of SSA form. SA is
1079 the outof-SSA info object. */
1082 finish_out_of_ssa (struct ssaexpand
*sa
)
1084 free (sa
->partition_to_pseudo
);
1086 BITMAP_FREE (sa
->values
);
1087 delete_var_map (sa
->map
);
1088 BITMAP_FREE (sa
->partition_has_default_def
);
1089 memset (sa
, 0, sizeof *sa
);
1092 /* Take the current function out of SSA form, translating PHIs as described in
1093 R. Morgan, ``Building an Optimizing Compiler'',
1094 Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */
1097 rewrite_out_of_ssa (struct ssaexpand
*sa
)
1099 /* If elimination of a PHI requires inserting a copy on a backedge,
1100 then we will have to split the backedge which has numerous
1101 undesirable performance effects.
1103 A significant number of such cases can be handled here by inserting
1104 copies into the loop itself. */
1105 insert_backedge_copies ();
1108 /* Eliminate PHIs which are of no use, such as virtual or dead phis. */
1109 eliminate_useless_phis ();
1111 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1112 gimple_dump_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);
1114 remove_ssa_form (flag_tree_ter
, sa
);
1116 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1117 gimple_dump_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);