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 dest_mode
, src_mode
;
202 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
205 "Inserting a value copy on edge BB%d->BB%d : PART.%d = ",
207 e
->dest
->index
, dest
);
208 print_generic_expr (dump_file
, src
, TDF_SLIM
);
209 fprintf (dump_file
, "\n");
212 gcc_assert (SA
.partition_to_pseudo
[dest
]);
214 set_location_for_edge (e
);
215 /* If a locus is provided, override the default. */
217 set_curr_insn_source_location (locus
);
221 var
= SSA_NAME_VAR (partition_to_var (SA
.map
, dest
));
222 src_mode
= TYPE_MODE (TREE_TYPE (src
));
223 dest_mode
= promote_decl_mode (var
, &unsignedp
);
224 gcc_assert (src_mode
== TYPE_MODE (TREE_TYPE (var
)));
225 gcc_assert (dest_mode
== GET_MODE (SA
.partition_to_pseudo
[dest
]));
227 if (src_mode
!= dest_mode
)
229 x
= expand_expr (src
, NULL
, src_mode
, EXPAND_NORMAL
);
230 x
= convert_modes (dest_mode
, src_mode
, x
, unsignedp
);
233 x
= expand_expr (src
, SA
.partition_to_pseudo
[dest
],
234 dest_mode
, EXPAND_NORMAL
);
236 if (x
!= SA
.partition_to_pseudo
[dest
])
237 emit_move_insn (SA
.partition_to_pseudo
[dest
], x
);
241 insert_insn_on_edge (seq
, e
);
244 /* Insert a copy instruction from RTL expression SRC to partition DEST
248 insert_rtx_to_part_on_edge (edge e
, int dest
, rtx src
, int unsignedsrcp
,
249 source_location locus
)
252 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
255 "Inserting a temp copy on edge BB%d->BB%d : PART.%d = ",
257 e
->dest
->index
, dest
);
258 print_simple_rtl (dump_file
, src
);
259 fprintf (dump_file
, "\n");
262 gcc_assert (SA
.partition_to_pseudo
[dest
]);
264 set_location_for_edge (e
);
265 /* If a locus is provided, override the default. */
267 set_curr_insn_source_location (locus
);
269 seq
= emit_partition_copy (SA
.partition_to_pseudo
[dest
],
273 insert_insn_on_edge (seq
, e
);
276 /* Insert a copy instruction from partition SRC to RTL lvalue DEST
280 insert_part_to_rtx_on_edge (edge e
, rtx dest
, int src
, source_location locus
)
283 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
286 "Inserting a temp copy on edge BB%d->BB%d : ",
289 print_simple_rtl (dump_file
, dest
);
290 fprintf (dump_file
, "= PART.%d\n", src
);
293 gcc_assert (SA
.partition_to_pseudo
[src
]);
295 set_location_for_edge (e
);
296 /* If a locus is provided, override the default. */
298 set_curr_insn_source_location (locus
);
300 seq
= emit_partition_copy (dest
,
301 SA
.partition_to_pseudo
[src
],
302 TYPE_UNSIGNED (TREE_TYPE (
303 partition_to_var (SA
.map
, src
))));
305 insert_insn_on_edge (seq
, e
);
309 /* Create an elimination graph with SIZE nodes and associated data
313 new_elim_graph (int size
)
315 elim_graph g
= (elim_graph
) xmalloc (sizeof (struct _elim_graph
));
317 g
->nodes
= VEC_alloc (int, heap
, 30);
318 g
->const_dests
= VEC_alloc (int, heap
, 20);
319 g
->const_copies
= VEC_alloc (tree
, heap
, 20);
320 g
->copy_locus
= VEC_alloc (source_location
, heap
, 10);
321 g
->edge_list
= VEC_alloc (int, heap
, 20);
322 g
->edge_locus
= VEC_alloc (source_location
, heap
, 10);
323 g
->stack
= VEC_alloc (int, heap
, 30);
325 g
->visited
= sbitmap_alloc (size
);
331 /* Empty elimination graph G. */
334 clear_elim_graph (elim_graph g
)
336 VEC_truncate (int, g
->nodes
, 0);
337 VEC_truncate (int, g
->edge_list
, 0);
338 VEC_truncate (source_location
, g
->edge_locus
, 0);
342 /* Delete elimination graph G. */
345 delete_elim_graph (elim_graph g
)
347 sbitmap_free (g
->visited
);
348 VEC_free (int, heap
, g
->stack
);
349 VEC_free (int, heap
, g
->edge_list
);
350 VEC_free (tree
, heap
, g
->const_copies
);
351 VEC_free (int, heap
, g
->const_dests
);
352 VEC_free (int, heap
, g
->nodes
);
353 VEC_free (source_location
, heap
, g
->copy_locus
);
354 VEC_free (source_location
, heap
, g
->edge_locus
);
360 /* Return the number of nodes in graph G. */
363 elim_graph_size (elim_graph g
)
365 return VEC_length (int, g
->nodes
);
369 /* Add NODE to graph G, if it doesn't exist already. */
372 elim_graph_add_node (elim_graph g
, int node
)
377 for (x
= 0; VEC_iterate (int, g
->nodes
, x
, t
); x
++)
380 VEC_safe_push (int, heap
, g
->nodes
, node
);
384 /* Add the edge PRED->SUCC to graph G. */
387 elim_graph_add_edge (elim_graph g
, int pred
, int succ
, source_location locus
)
389 VEC_safe_push (int, heap
, g
->edge_list
, pred
);
390 VEC_safe_push (int, heap
, g
->edge_list
, succ
);
391 VEC_safe_push (source_location
, heap
, g
->edge_locus
, locus
);
395 /* Remove an edge from graph G for which NODE is the predecessor, and
396 return the successor node. -1 is returned if there is no such edge. */
399 elim_graph_remove_succ_edge (elim_graph g
, int node
, source_location
*locus
)
403 for (x
= 0; x
< VEC_length (int, g
->edge_list
); x
+= 2)
404 if (VEC_index (int, g
->edge_list
, x
) == node
)
406 VEC_replace (int, g
->edge_list
, x
, -1);
407 y
= VEC_index (int, g
->edge_list
, x
+ 1);
408 VEC_replace (int, g
->edge_list
, x
+ 1, -1);
409 *locus
= VEC_index (source_location
, g
->edge_locus
, x
/ 2);
410 VEC_replace (source_location
, g
->edge_locus
, x
/ 2, UNKNOWN_LOCATION
);
413 *locus
= UNKNOWN_LOCATION
;
418 /* Find all the nodes in GRAPH which are successors to NODE in the
419 edge list. VAR will hold the partition number found. CODE is the
420 code fragment executed for every node found. */
422 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, LOCUS, CODE) \
426 for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2) \
428 y_ = VEC_index (int, (GRAPH)->edge_list, x_); \
431 (VAR) = VEC_index (int, (GRAPH)->edge_list, x_ + 1); \
432 (LOCUS) = VEC_index (source_location, (GRAPH)->edge_locus, x_ / 2); \
438 /* Find all the nodes which are predecessors of NODE in the edge list for
439 GRAPH. VAR will hold the partition number found. CODE is the
440 code fragment executed for every node found. */
442 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, LOCUS, CODE) \
446 for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2) \
448 y_ = VEC_index (int, (GRAPH)->edge_list, x_ + 1); \
451 (VAR) = VEC_index (int, (GRAPH)->edge_list, x_); \
452 (LOCUS) = VEC_index (source_location, (GRAPH)->edge_locus, x_ / 2); \
458 /* Add T to elimination graph G. */
461 eliminate_name (elim_graph g
, int T
)
463 elim_graph_add_node (g
, T
);
467 /* Build elimination graph G for basic block BB on incoming PHI edge
471 eliminate_build (elim_graph g
)
475 gimple_stmt_iterator gsi
;
477 clear_elim_graph (g
);
479 for (gsi
= gsi_start_phis (g
->e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
481 gimple phi
= gsi_stmt (gsi
);
482 source_location locus
;
484 p0
= var_to_partition (g
->map
, gimple_phi_result (phi
));
485 /* Ignore results which are not in partitions. */
486 if (p0
== NO_PARTITION
)
489 Ti
= PHI_ARG_DEF (phi
, g
->e
->dest_idx
);
490 locus
= gimple_phi_arg_location_from_edge (phi
, g
->e
);
492 /* If this argument is a constant, or a SSA_NAME which is being
493 left in SSA form, just queue a copy to be emitted on this
495 if (!phi_ssa_name_p (Ti
)
496 || (TREE_CODE (Ti
) == SSA_NAME
497 && var_to_partition (g
->map
, Ti
) == NO_PARTITION
))
499 /* Save constant copies until all other copies have been emitted
501 VEC_safe_push (int, heap
, g
->const_dests
, p0
);
502 VEC_safe_push (tree
, heap
, g
->const_copies
, Ti
);
503 VEC_safe_push (source_location
, heap
, g
->copy_locus
, locus
);
507 pi
= var_to_partition (g
->map
, Ti
);
510 eliminate_name (g
, p0
);
511 eliminate_name (g
, pi
);
512 elim_graph_add_edge (g
, p0
, pi
, locus
);
519 /* Push successors of T onto the elimination stack for G. */
522 elim_forward (elim_graph g
, int T
)
525 source_location locus
;
527 SET_BIT (g
->visited
, T
);
528 FOR_EACH_ELIM_GRAPH_SUCC (g
, T
, S
, locus
,
530 if (!TEST_BIT (g
->visited
, S
))
533 VEC_safe_push (int, heap
, g
->stack
, T
);
537 /* Return 1 if there unvisited predecessors of T in graph G. */
540 elim_unvisited_predecessor (elim_graph g
, int T
)
543 source_location locus
;
545 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
547 if (!TEST_BIT (g
->visited
, P
))
553 /* Process predecessors first, and insert a copy. */
556 elim_backward (elim_graph g
, int T
)
559 source_location locus
;
561 SET_BIT (g
->visited
, T
);
562 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
564 if (!TEST_BIT (g
->visited
, P
))
566 elim_backward (g
, P
);
567 insert_partition_copy_on_edge (g
->e
, P
, T
, locus
);
572 /* Allocate a new pseudo register usable for storing values sitting
573 in NAME (a decl or SSA name), i.e. with matching mode and attributes. */
576 get_temp_reg (tree name
)
578 tree var
= TREE_CODE (name
) == SSA_NAME
? SSA_NAME_VAR (name
) : name
;
579 tree type
= TREE_TYPE (var
);
581 enum machine_mode reg_mode
= promote_decl_mode (var
, &unsignedp
);
582 rtx x
= gen_reg_rtx (reg_mode
);
583 if (POINTER_TYPE_P (type
))
584 mark_reg_pointer (x
, TYPE_ALIGN (TREE_TYPE (TREE_TYPE (var
))));
588 /* Insert required copies for T in graph G. Check for a strongly connected
589 region, and create a temporary to break the cycle if one is found. */
592 elim_create (elim_graph g
, int T
)
595 source_location locus
;
597 if (elim_unvisited_predecessor (g
, T
))
599 tree var
= partition_to_var (g
->map
, T
);
600 rtx U
= get_temp_reg (var
);
601 int unsignedsrcp
= TYPE_UNSIGNED (TREE_TYPE (var
));
603 insert_part_to_rtx_on_edge (g
->e
, U
, T
, UNKNOWN_LOCATION
);
604 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
606 if (!TEST_BIT (g
->visited
, P
))
608 elim_backward (g
, P
);
609 insert_rtx_to_part_on_edge (g
->e
, P
, U
, unsignedsrcp
, locus
);
615 S
= elim_graph_remove_succ_edge (g
, T
, &locus
);
618 SET_BIT (g
->visited
, T
);
619 insert_partition_copy_on_edge (g
->e
, T
, S
, locus
);
625 /* Eliminate all the phi nodes on edge E in graph G. */
628 eliminate_phi (edge e
, elim_graph g
)
632 gcc_assert (VEC_length (tree
, g
->const_copies
) == 0);
633 gcc_assert (VEC_length (source_location
, g
->copy_locus
) == 0);
635 /* Abnormal edges already have everything coalesced. */
636 if (e
->flags
& EDGE_ABNORMAL
)
643 if (elim_graph_size (g
) != 0)
647 sbitmap_zero (g
->visited
);
648 VEC_truncate (int, g
->stack
, 0);
650 for (x
= 0; VEC_iterate (int, g
->nodes
, x
, part
); x
++)
652 if (!TEST_BIT (g
->visited
, part
))
653 elim_forward (g
, part
);
656 sbitmap_zero (g
->visited
);
657 while (VEC_length (int, g
->stack
) > 0)
659 x
= VEC_pop (int, g
->stack
);
660 if (!TEST_BIT (g
->visited
, x
))
665 /* If there are any pending constant copies, issue them now. */
666 while (VEC_length (tree
, g
->const_copies
) > 0)
670 source_location locus
;
672 src
= VEC_pop (tree
, g
->const_copies
);
673 dest
= VEC_pop (int, g
->const_dests
);
674 locus
= VEC_pop (source_location
, g
->copy_locus
);
675 insert_value_copy_on_edge (e
, dest
, src
, locus
);
680 /* Remove each argument from PHI. If an arg was the last use of an SSA_NAME,
681 check to see if this allows another PHI node to be removed. */
684 remove_gimple_phi_args (gimple phi
)
689 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
691 fprintf (dump_file
, "Removing Dead PHI definition: ");
692 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
695 FOR_EACH_PHI_ARG (arg_p
, phi
, iter
, SSA_OP_USE
)
697 tree arg
= USE_FROM_PTR (arg_p
);
698 if (TREE_CODE (arg
) == SSA_NAME
)
700 /* Remove the reference to the existing argument. */
701 SET_USE (arg_p
, NULL_TREE
);
702 if (has_zero_uses (arg
))
705 gimple_stmt_iterator gsi
;
707 stmt
= SSA_NAME_DEF_STMT (arg
);
709 /* Also remove the def if it is a PHI node. */
710 if (gimple_code (stmt
) == GIMPLE_PHI
)
712 remove_gimple_phi_args (stmt
);
713 gsi
= gsi_for_stmt (stmt
);
714 remove_phi_node (&gsi
, true);
722 /* Remove any PHI node which is a virtual PHI, or a PHI with no uses. */
725 eliminate_useless_phis (void)
728 gimple_stmt_iterator gsi
;
733 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); )
735 gimple phi
= gsi_stmt (gsi
);
736 result
= gimple_phi_result (phi
);
737 if (!is_gimple_reg (SSA_NAME_VAR (result
)))
739 #ifdef ENABLE_CHECKING
741 /* There should be no arguments which are not virtual, or the
742 results will be incorrect. */
743 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
745 tree arg
= PHI_ARG_DEF (phi
, i
);
746 if (TREE_CODE (arg
) == SSA_NAME
747 && is_gimple_reg (SSA_NAME_VAR (arg
)))
749 fprintf (stderr
, "Argument of PHI is not virtual (");
750 print_generic_expr (stderr
, arg
, TDF_SLIM
);
751 fprintf (stderr
, "), but the result is :");
752 print_gimple_stmt (stderr
, phi
, 0, TDF_SLIM
);
753 internal_error ("SSA corruption");
757 remove_phi_node (&gsi
, true);
761 /* Also remove real PHIs with no uses. */
762 if (has_zero_uses (result
))
764 remove_gimple_phi_args (phi
);
765 remove_phi_node (&gsi
, true);
775 /* This function will rewrite the current program using the variable mapping
776 found in MAP. If the replacement vector VALUES is provided, any
777 occurrences of partitions with non-null entries in the vector will be
778 replaced with the expression in the vector instead of its mapped
782 rewrite_trees (var_map map ATTRIBUTE_UNUSED
)
784 #ifdef ENABLE_CHECKING
786 /* Search for PHIs where the destination has no partition, but one
787 or more arguments has a partition. This should not happen and can
788 create incorrect code. */
791 gimple_stmt_iterator gsi
;
792 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
794 gimple phi
= gsi_stmt (gsi
);
795 tree T0
= var_to_partition_to_var (map
, gimple_phi_result (phi
));
799 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
801 tree arg
= PHI_ARG_DEF (phi
, i
);
803 if (TREE_CODE (arg
) == SSA_NAME
804 && var_to_partition (map
, arg
) != NO_PARTITION
)
806 fprintf (stderr
, "Argument of PHI is in a partition :(");
807 print_generic_expr (stderr
, arg
, TDF_SLIM
);
808 fprintf (stderr
, "), but the result is not :");
809 print_gimple_stmt (stderr
, phi
, 0, TDF_SLIM
);
810 internal_error ("SSA corruption");
819 /* Given the out-of-ssa info object SA (with prepared partitions)
820 eliminate all phi nodes in all basic blocks. Afterwards no
821 basic block will have phi nodes anymore and there are possibly
822 some RTL instructions inserted on edges. */
825 expand_phi_nodes (struct ssaexpand
*sa
)
828 elim_graph g
= new_elim_graph (sa
->map
->num_partitions
);
831 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
, EXIT_BLOCK_PTR
, next_bb
)
832 if (!gimple_seq_empty_p (phi_nodes (bb
)))
836 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
837 eliminate_phi (e
, g
);
838 set_phi_nodes (bb
, NULL
);
839 /* We can't redirect EH edges in RTL land, so we need to do this
840 here. Redirection happens only when splitting is necessary,
841 which it is only for critical edges, normally. For EH edges
842 it might also be necessary when the successor has more than
843 one predecessor. In that case the edge is either required to
844 be fallthru (which EH edges aren't), or the predecessor needs
845 to end with a jump (which again, isn't the case with EH edges).
846 Hence, split all EH edges on which we inserted instructions
847 and whose successor has multiple predecessors. */
848 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
850 if (e
->insns
.r
&& (e
->flags
& EDGE_EH
)
851 && !single_pred_p (e
->dest
))
853 rtx insns
= e
->insns
.r
;
855 e
->insns
.r
= NULL_RTX
;
857 single_pred_edge (bb
)->insns
.r
= insns
;
864 delete_elim_graph (g
);
868 /* Remove the ssa-names in the current function and translate them into normal
869 compiler variables. PERFORM_TER is true if Temporary Expression Replacement
870 should also be used. */
873 remove_ssa_form (bool perform_ter
, struct ssaexpand
*sa
)
875 bitmap values
= NULL
;
879 map
= coalesce_ssa_name ();
881 /* Return to viewing the variable list as just all reference variables after
882 coalescing has been performed. */
883 partition_view_normal (map
, false);
885 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
887 fprintf (dump_file
, "After Coalescing:\n");
888 dump_var_map (dump_file
, map
);
893 values
= find_replaceable_exprs (map
);
894 if (values
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
895 dump_replaceable_exprs (dump_file
, values
);
902 sa
->partition_has_default_def
= BITMAP_ALLOC (NULL
);
903 for (i
= 1; i
< num_ssa_names
; i
++)
905 tree t
= ssa_name (i
);
906 if (t
&& SSA_NAME_IS_DEFAULT_DEF (t
))
908 int p
= var_to_partition (map
, t
);
909 if (p
!= NO_PARTITION
)
910 bitmap_set_bit (sa
->partition_has_default_def
, p
);
916 /* If not already done so for basic block BB, assign increasing uids
917 to each of its instructions. */
920 maybe_renumber_stmts_bb (basic_block bb
)
923 gimple_stmt_iterator gsi
;
928 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
930 gimple stmt
= gsi_stmt (gsi
);
931 gimple_set_uid (stmt
, i
);
937 /* Return true if we can determine that the SSA_NAMEs RESULT (a result
938 of a PHI node) and ARG (one of its arguments) conflict. Return false
939 otherwise, also when we simply aren't sure. */
942 trivially_conflicts_p (basic_block bb
, tree result
, tree arg
)
945 imm_use_iterator imm_iter
;
946 gimple defa
= SSA_NAME_DEF_STMT (arg
);
948 /* If ARG isn't defined in the same block it's too complicated for
950 if (gimple_bb (defa
) != bb
)
953 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, result
)
955 gimple use_stmt
= USE_STMT (use
);
956 /* Now, if there's a use of RESULT that lies outside this basic block,
957 then there surely is a conflict with ARG. */
958 if (gimple_bb (use_stmt
) != bb
)
960 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
962 /* The use now is in a real stmt of BB, so if ARG was defined
963 in a PHI node (like RESULT) both conflict. */
964 if (gimple_code (defa
) == GIMPLE_PHI
)
966 maybe_renumber_stmts_bb (bb
);
967 /* If the use of RESULT occurs after the definition of ARG,
968 the two conflict too. */
969 if (gimple_uid (defa
) < gimple_uid (use_stmt
))
977 /* Search every PHI node for arguments associated with backedges which
978 we can trivially determine will need a copy (the argument is either
979 not an SSA_NAME or the argument has a different underlying variable
980 than the PHI result).
982 Insert a copy from the PHI argument to a new destination at the
983 end of the block with the backedge to the top of the loop. Update
984 the PHI argument to reference this new destination. */
987 insert_backedge_copies (void)
990 gimple_stmt_iterator gsi
;
994 /* Mark block as possibly needing calculation of UIDs. */
997 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
999 gimple phi
= gsi_stmt (gsi
);
1000 tree result
= gimple_phi_result (phi
);
1004 if (!is_gimple_reg (result
))
1007 result_var
= SSA_NAME_VAR (result
);
1008 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1010 tree arg
= gimple_phi_arg_def (phi
, i
);
1011 edge e
= gimple_phi_arg_edge (phi
, i
);
1013 /* If the argument is not an SSA_NAME, then we will need a
1014 constant initialization. If the argument is an SSA_NAME with
1015 a different underlying variable then a copy statement will be
1017 if ((e
->flags
& EDGE_DFS_BACK
)
1018 && (TREE_CODE (arg
) != SSA_NAME
1019 || SSA_NAME_VAR (arg
) != result_var
1020 || trivially_conflicts_p (bb
, result
, arg
)))
1023 gimple stmt
, last
= NULL
;
1024 gimple_stmt_iterator gsi2
;
1026 gsi2
= gsi_last_bb (gimple_phi_arg_edge (phi
, i
)->src
);
1027 if (!gsi_end_p (gsi2
))
1028 last
= gsi_stmt (gsi2
);
1030 /* In theory the only way we ought to get back to the
1031 start of a loop should be with a COND_EXPR or GOTO_EXPR.
1032 However, better safe than sorry.
1033 If the block ends with a control statement or
1034 something that might throw, then we have to
1035 insert this assignment before the last
1036 statement. Else insert it after the last statement. */
1037 if (last
&& stmt_ends_bb_p (last
))
1039 /* If the last statement in the block is the definition
1040 site of the PHI argument, then we can't insert
1041 anything after it. */
1042 if (TREE_CODE (arg
) == SSA_NAME
1043 && SSA_NAME_DEF_STMT (arg
) == last
)
1047 /* Create a new instance of the underlying variable of the
1049 stmt
= gimple_build_assign (result_var
,
1050 gimple_phi_arg_def (phi
, i
));
1051 name
= make_ssa_name (result_var
, stmt
);
1052 gimple_assign_set_lhs (stmt
, name
);
1054 /* copy location if present. */
1055 if (gimple_phi_arg_has_location (phi
, i
))
1056 gimple_set_location (stmt
,
1057 gimple_phi_arg_location (phi
, i
));
1059 /* Insert the new statement into the block and update
1061 if (last
&& stmt_ends_bb_p (last
))
1062 gsi_insert_before (&gsi2
, stmt
, GSI_NEW_STMT
);
1064 gsi_insert_after (&gsi2
, stmt
, GSI_NEW_STMT
);
1065 SET_PHI_ARG_DEF (phi
, i
, name
);
1070 /* Unmark this block again. */
1075 /* Free all memory associated with going out of SSA form. SA is
1076 the outof-SSA info object. */
1079 finish_out_of_ssa (struct ssaexpand
*sa
)
1081 free (sa
->partition_to_pseudo
);
1083 BITMAP_FREE (sa
->values
);
1084 delete_var_map (sa
->map
);
1085 BITMAP_FREE (sa
->partition_has_default_def
);
1086 memset (sa
, 0, sizeof *sa
);
1089 /* Take the current function out of SSA form, translating PHIs as described in
1090 R. Morgan, ``Building an Optimizing Compiler'',
1091 Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */
1094 rewrite_out_of_ssa (struct ssaexpand
*sa
)
1096 /* If elimination of a PHI requires inserting a copy on a backedge,
1097 then we will have to split the backedge which has numerous
1098 undesirable performance effects.
1100 A significant number of such cases can be handled here by inserting
1101 copies into the loop itself. */
1102 insert_backedge_copies ();
1105 /* Eliminate PHIs which are of no use, such as virtual or dead phis. */
1106 eliminate_useless_phis ();
1108 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1109 gimple_dump_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);
1111 remove_ssa_form (flag_tree_ter
, sa
);
1113 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1114 gimple_dump_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);