1 /* Convert a program in SSA form into Normal form.
2 Copyright (C) 2004-2013 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 "gimple-pretty-print.h"
30 #include "tree-flow.h"
32 #include "diagnostic-core.h"
33 #include "ssaexpand.h"
35 /* FIXME: A lot of code here deals with expanding to RTL. All that code
36 should be in cfgexpand.c. */
41 /* Used to hold all the components required to do SSA PHI elimination.
42 The node and pred/succ list is a simple linear list of nodes and
43 edges represented as pairs of nodes.
45 The predecessor and successor list: Nodes are entered in pairs, where
46 [0] ->PRED, [1]->SUCC. All the even indexes in the array represent
47 predecessors, all the odd elements are successors.
50 When implemented as bitmaps, very large programs SSA->Normal times were
51 being dominated by clearing the interference graph.
53 Typically this list of edges is extremely small since it only includes
54 PHI results and uses from a single edge which have not coalesced with
55 each other. This means that no virtual PHI nodes are included, and
56 empirical evidence suggests that the number of edges rarely exceed
57 3, and in a bootstrap of GCC, the maximum size encountered was 7.
58 This also limits the number of possible nodes that are involved to
59 rarely more than 6, and in the bootstrap of gcc, the maximum number
60 of nodes encountered was 12. */
62 typedef struct _elim_graph
{
63 /* Size of the elimination vectors. */
66 /* List of nodes in the elimination graph. */
69 /* The predecessor and successor edge list. */
72 /* Source locus on each edge */
73 vec
<source_location
> edge_locus
;
78 /* Stack for visited nodes. */
81 /* The variable partition map. */
84 /* Edge being eliminated by this graph. */
87 /* List of constant copies to emit. These are pushed on in pairs. */
89 vec
<tree
> const_copies
;
91 /* Source locations for any constant copies. */
92 vec
<source_location
> copy_locus
;
96 /* For an edge E find out a good source location to associate with
97 instructions inserted on edge E. If E has an implicit goto set,
98 use its location. Otherwise search instructions in predecessors
99 of E for a location, and use that one. That makes sense because
100 we insert on edges for PHI nodes, and effects of PHIs happen on
101 the end of the predecessor conceptually. */
104 set_location_for_edge (edge e
)
108 set_curr_insn_location (e
->goto_locus
);
112 basic_block bb
= e
->src
;
113 gimple_stmt_iterator gsi
;
117 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
119 gimple stmt
= gsi_stmt (gsi
);
120 if (is_gimple_debug (stmt
))
122 if (gimple_has_location (stmt
) || gimple_block (stmt
))
124 set_curr_insn_location (gimple_location (stmt
));
128 /* Nothing found in this basic block. Make a half-assed attempt
129 to continue with another block. */
130 if (single_pred_p (bb
))
131 bb
= single_pred (bb
);
135 while (bb
!= e
->src
);
139 /* Emit insns to copy SRC into DEST converting SRC if necessary. As
140 SRC/DEST might be BLKmode memory locations SIZEEXP is a tree from
141 which we deduce the size to copy in that case. */
144 emit_partition_copy (rtx dest
, rtx src
, int unsignedsrcp
, tree sizeexp
)
150 if (GET_MODE (src
) != VOIDmode
&& GET_MODE (src
) != GET_MODE (dest
))
151 src
= convert_to_mode (GET_MODE (dest
), src
, unsignedsrcp
);
152 if (GET_MODE (src
) == BLKmode
)
154 gcc_assert (GET_MODE (dest
) == BLKmode
);
155 emit_block_move (dest
, src
, expr_size (sizeexp
), BLOCK_OP_NORMAL
);
158 emit_move_insn (dest
, src
);
166 /* Insert a copy instruction from partition SRC to DEST onto edge E. */
169 insert_partition_copy_on_edge (edge e
, int dest
, int src
, source_location locus
)
173 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
176 "Inserting a partition copy on edge BB%d->BB%d :"
179 e
->dest
->index
, dest
, src
);
180 fprintf (dump_file
, "\n");
183 gcc_assert (SA
.partition_to_pseudo
[dest
]);
184 gcc_assert (SA
.partition_to_pseudo
[src
]);
186 set_location_for_edge (e
);
187 /* If a locus is provided, override the default. */
189 set_curr_insn_location (locus
);
191 var
= partition_to_var (SA
.map
, src
);
192 seq
= emit_partition_copy (SA
.partition_to_pseudo
[dest
],
193 SA
.partition_to_pseudo
[src
],
194 TYPE_UNSIGNED (TREE_TYPE (var
)),
197 insert_insn_on_edge (seq
, e
);
200 /* Insert a copy instruction from expression SRC to partition DEST
204 insert_value_copy_on_edge (edge e
, int dest
, tree src
, source_location locus
)
207 enum machine_mode dest_mode
, src_mode
;
211 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
214 "Inserting a value copy on edge BB%d->BB%d : PART.%d = ",
216 e
->dest
->index
, dest
);
217 print_generic_expr (dump_file
, src
, TDF_SLIM
);
218 fprintf (dump_file
, "\n");
221 gcc_assert (SA
.partition_to_pseudo
[dest
]);
223 set_location_for_edge (e
);
224 /* If a locus is provided, override the default. */
226 set_curr_insn_location (locus
);
230 var
= SSA_NAME_VAR (partition_to_var (SA
.map
, dest
));
231 src_mode
= TYPE_MODE (TREE_TYPE (src
));
232 dest_mode
= GET_MODE (SA
.partition_to_pseudo
[dest
]);
233 gcc_assert (src_mode
== TYPE_MODE (TREE_TYPE (var
)));
234 gcc_assert (!REG_P (SA
.partition_to_pseudo
[dest
])
235 || dest_mode
== promote_decl_mode (var
, &unsignedp
));
237 if (src_mode
!= dest_mode
)
239 x
= expand_expr (src
, NULL
, src_mode
, EXPAND_NORMAL
);
240 x
= convert_modes (dest_mode
, src_mode
, x
, unsignedp
);
242 else if (src_mode
== BLKmode
)
244 x
= SA
.partition_to_pseudo
[dest
];
245 store_expr (src
, x
, 0, false);
248 x
= expand_expr (src
, SA
.partition_to_pseudo
[dest
],
249 dest_mode
, EXPAND_NORMAL
);
251 if (x
!= SA
.partition_to_pseudo
[dest
])
252 emit_move_insn (SA
.partition_to_pseudo
[dest
], x
);
256 insert_insn_on_edge (seq
, e
);
259 /* Insert a copy instruction from RTL expression SRC to partition DEST
263 insert_rtx_to_part_on_edge (edge e
, int dest
, rtx src
, int unsignedsrcp
,
264 source_location locus
)
267 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
270 "Inserting a temp copy on edge BB%d->BB%d : PART.%d = ",
272 e
->dest
->index
, dest
);
273 print_simple_rtl (dump_file
, src
);
274 fprintf (dump_file
, "\n");
277 gcc_assert (SA
.partition_to_pseudo
[dest
]);
279 set_location_for_edge (e
);
280 /* If a locus is provided, override the default. */
282 set_curr_insn_location (locus
);
284 /* We give the destination as sizeexp in case src/dest are BLKmode
285 mems. Usually we give the source. As we result from SSA names
286 the left and right size should be the same (and no WITH_SIZE_EXPR
287 involved), so it doesn't matter. */
288 seq
= emit_partition_copy (SA
.partition_to_pseudo
[dest
],
290 partition_to_var (SA
.map
, dest
));
292 insert_insn_on_edge (seq
, e
);
295 /* Insert a copy instruction from partition SRC to RTL lvalue DEST
299 insert_part_to_rtx_on_edge (edge e
, rtx dest
, int src
, source_location locus
)
303 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
306 "Inserting a temp copy on edge BB%d->BB%d : ",
309 print_simple_rtl (dump_file
, dest
);
310 fprintf (dump_file
, "= PART.%d\n", src
);
313 gcc_assert (SA
.partition_to_pseudo
[src
]);
315 set_location_for_edge (e
);
316 /* If a locus is provided, override the default. */
318 set_curr_insn_location (locus
);
320 var
= partition_to_var (SA
.map
, src
);
321 seq
= emit_partition_copy (dest
,
322 SA
.partition_to_pseudo
[src
],
323 TYPE_UNSIGNED (TREE_TYPE (var
)),
326 insert_insn_on_edge (seq
, e
);
330 /* Create an elimination graph with SIZE nodes and associated data
334 new_elim_graph (int size
)
336 elim_graph g
= (elim_graph
) xmalloc (sizeof (struct _elim_graph
));
338 g
->nodes
.create (30);
339 g
->const_dests
.create (20);
340 g
->const_copies
.create (20);
341 g
->copy_locus
.create (10);
342 g
->edge_list
.create (20);
343 g
->edge_locus
.create (10);
344 g
->stack
.create (30);
346 g
->visited
= sbitmap_alloc (size
);
352 /* Empty elimination graph G. */
355 clear_elim_graph (elim_graph g
)
357 g
->nodes
.truncate (0);
358 g
->edge_list
.truncate (0);
359 g
->edge_locus
.truncate (0);
363 /* Delete elimination graph G. */
366 delete_elim_graph (elim_graph g
)
368 sbitmap_free (g
->visited
);
370 g
->edge_list
.release ();
371 g
->const_copies
.release ();
372 g
->const_dests
.release ();
374 g
->copy_locus
.release ();
375 g
->edge_locus
.release ();
381 /* Return the number of nodes in graph G. */
384 elim_graph_size (elim_graph g
)
386 return g
->nodes
.length ();
390 /* Add NODE to graph G, if it doesn't exist already. */
393 elim_graph_add_node (elim_graph g
, int node
)
398 FOR_EACH_VEC_ELT (g
->nodes
, x
, t
)
401 g
->nodes
.safe_push (node
);
405 /* Add the edge PRED->SUCC to graph G. */
408 elim_graph_add_edge (elim_graph g
, int pred
, int succ
, source_location locus
)
410 g
->edge_list
.safe_push (pred
);
411 g
->edge_list
.safe_push (succ
);
412 g
->edge_locus
.safe_push (locus
);
416 /* Remove an edge from graph G for which NODE is the predecessor, and
417 return the successor node. -1 is returned if there is no such edge. */
420 elim_graph_remove_succ_edge (elim_graph g
, int node
, source_location
*locus
)
424 for (x
= 0; x
< g
->edge_list
.length (); x
+= 2)
425 if (g
->edge_list
[x
] == node
)
427 g
->edge_list
[x
] = -1;
428 y
= g
->edge_list
[x
+ 1];
429 g
->edge_list
[x
+ 1] = -1;
430 *locus
= g
->edge_locus
[x
/ 2];
431 g
->edge_locus
[x
/ 2] = UNKNOWN_LOCATION
;
434 *locus
= UNKNOWN_LOCATION
;
439 /* Find all the nodes in GRAPH which are successors to NODE in the
440 edge list. VAR will hold the partition number found. CODE is the
441 code fragment executed for every node found. */
443 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, LOCUS, CODE) \
447 for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \
449 y_ = (GRAPH)->edge_list[x_]; \
452 (void) ((VAR) = (GRAPH)->edge_list[x_ + 1]); \
453 (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \
459 /* Find all the nodes which are predecessors of NODE in the edge list for
460 GRAPH. VAR will hold the partition number found. CODE is the
461 code fragment executed for every node found. */
463 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, LOCUS, CODE) \
467 for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \
469 y_ = (GRAPH)->edge_list[x_ + 1]; \
472 (void) ((VAR) = (GRAPH)->edge_list[x_]); \
473 (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \
479 /* Add T to elimination graph G. */
482 eliminate_name (elim_graph g
, int T
)
484 elim_graph_add_node (g
, T
);
488 /* Build elimination graph G for basic block BB on incoming PHI edge
492 eliminate_build (elim_graph g
)
496 gimple_stmt_iterator gsi
;
498 clear_elim_graph (g
);
500 for (gsi
= gsi_start_phis (g
->e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
502 gimple phi
= gsi_stmt (gsi
);
503 source_location locus
;
505 p0
= var_to_partition (g
->map
, gimple_phi_result (phi
));
506 /* Ignore results which are not in partitions. */
507 if (p0
== NO_PARTITION
)
510 Ti
= PHI_ARG_DEF (phi
, g
->e
->dest_idx
);
511 locus
= gimple_phi_arg_location_from_edge (phi
, g
->e
);
513 /* If this argument is a constant, or a SSA_NAME which is being
514 left in SSA form, just queue a copy to be emitted on this
516 if (!phi_ssa_name_p (Ti
)
517 || (TREE_CODE (Ti
) == SSA_NAME
518 && var_to_partition (g
->map
, Ti
) == NO_PARTITION
))
520 /* Save constant copies until all other copies have been emitted
522 g
->const_dests
.safe_push (p0
);
523 g
->const_copies
.safe_push (Ti
);
524 g
->copy_locus
.safe_push (locus
);
528 pi
= var_to_partition (g
->map
, Ti
);
531 eliminate_name (g
, p0
);
532 eliminate_name (g
, pi
);
533 elim_graph_add_edge (g
, p0
, pi
, locus
);
540 /* Push successors of T onto the elimination stack for G. */
543 elim_forward (elim_graph g
, int T
)
546 source_location locus
;
548 bitmap_set_bit (g
->visited
, T
);
549 FOR_EACH_ELIM_GRAPH_SUCC (g
, T
, S
, locus
,
551 if (!bitmap_bit_p (g
->visited
, S
))
554 g
->stack
.safe_push (T
);
558 /* Return 1 if there unvisited predecessors of T in graph G. */
561 elim_unvisited_predecessor (elim_graph g
, int T
)
564 source_location locus
;
566 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
568 if (!bitmap_bit_p (g
->visited
, P
))
574 /* Process predecessors first, and insert a copy. */
577 elim_backward (elim_graph g
, int T
)
580 source_location locus
;
582 bitmap_set_bit (g
->visited
, T
);
583 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
585 if (!bitmap_bit_p (g
->visited
, P
))
587 elim_backward (g
, P
);
588 insert_partition_copy_on_edge (g
->e
, P
, T
, locus
);
593 /* Allocate a new pseudo register usable for storing values sitting
594 in NAME (a decl or SSA name), i.e. with matching mode and attributes. */
597 get_temp_reg (tree name
)
599 tree var
= TREE_CODE (name
) == SSA_NAME
? SSA_NAME_VAR (name
) : name
;
600 tree type
= TREE_TYPE (var
);
602 enum machine_mode reg_mode
= promote_decl_mode (var
, &unsignedp
);
603 rtx x
= gen_reg_rtx (reg_mode
);
604 if (POINTER_TYPE_P (type
))
605 mark_reg_pointer (x
, TYPE_ALIGN (TREE_TYPE (TREE_TYPE (var
))));
609 /* Insert required copies for T in graph G. Check for a strongly connected
610 region, and create a temporary to break the cycle if one is found. */
613 elim_create (elim_graph g
, int T
)
616 source_location locus
;
618 if (elim_unvisited_predecessor (g
, T
))
620 tree var
= partition_to_var (g
->map
, T
);
621 rtx U
= get_temp_reg (var
);
622 int unsignedsrcp
= TYPE_UNSIGNED (TREE_TYPE (var
));
624 insert_part_to_rtx_on_edge (g
->e
, U
, T
, UNKNOWN_LOCATION
);
625 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
627 if (!bitmap_bit_p (g
->visited
, P
))
629 elim_backward (g
, P
);
630 insert_rtx_to_part_on_edge (g
->e
, P
, U
, unsignedsrcp
, locus
);
636 S
= elim_graph_remove_succ_edge (g
, T
, &locus
);
639 bitmap_set_bit (g
->visited
, T
);
640 insert_partition_copy_on_edge (g
->e
, T
, S
, locus
);
646 /* Eliminate all the phi nodes on edge E in graph G. */
649 eliminate_phi (edge e
, elim_graph g
)
653 gcc_assert (g
->const_copies
.length () == 0);
654 gcc_assert (g
->copy_locus
.length () == 0);
656 /* Abnormal edges already have everything coalesced. */
657 if (e
->flags
& EDGE_ABNORMAL
)
664 if (elim_graph_size (g
) != 0)
668 bitmap_clear (g
->visited
);
669 g
->stack
.truncate (0);
671 FOR_EACH_VEC_ELT (g
->nodes
, x
, part
)
673 if (!bitmap_bit_p (g
->visited
, part
))
674 elim_forward (g
, part
);
677 bitmap_clear (g
->visited
);
678 while (g
->stack
.length () > 0)
681 if (!bitmap_bit_p (g
->visited
, x
))
686 /* If there are any pending constant copies, issue them now. */
687 while (g
->const_copies
.length () > 0)
691 source_location locus
;
693 src
= g
->const_copies
.pop ();
694 dest
= g
->const_dests
.pop ();
695 locus
= g
->copy_locus
.pop ();
696 insert_value_copy_on_edge (e
, dest
, src
, locus
);
701 /* Remove each argument from PHI. If an arg was the last use of an SSA_NAME,
702 check to see if this allows another PHI node to be removed. */
705 remove_gimple_phi_args (gimple phi
)
710 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
712 fprintf (dump_file
, "Removing Dead PHI definition: ");
713 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
716 FOR_EACH_PHI_ARG (arg_p
, phi
, iter
, SSA_OP_USE
)
718 tree arg
= USE_FROM_PTR (arg_p
);
719 if (TREE_CODE (arg
) == SSA_NAME
)
721 /* Remove the reference to the existing argument. */
722 SET_USE (arg_p
, NULL_TREE
);
723 if (has_zero_uses (arg
))
726 gimple_stmt_iterator gsi
;
728 stmt
= SSA_NAME_DEF_STMT (arg
);
730 /* Also remove the def if it is a PHI node. */
731 if (gimple_code (stmt
) == GIMPLE_PHI
)
733 remove_gimple_phi_args (stmt
);
734 gsi
= gsi_for_stmt (stmt
);
735 remove_phi_node (&gsi
, true);
743 /* Remove any PHI node which is a virtual PHI, or a PHI with no uses. */
746 eliminate_useless_phis (void)
749 gimple_stmt_iterator gsi
;
754 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); )
756 gimple phi
= gsi_stmt (gsi
);
757 result
= gimple_phi_result (phi
);
758 if (virtual_operand_p (result
))
760 #ifdef ENABLE_CHECKING
762 /* There should be no arguments which are not virtual, or the
763 results will be incorrect. */
764 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
766 tree arg
= PHI_ARG_DEF (phi
, i
);
767 if (TREE_CODE (arg
) == SSA_NAME
768 && !virtual_operand_p (arg
))
770 fprintf (stderr
, "Argument of PHI is not virtual (");
771 print_generic_expr (stderr
, arg
, TDF_SLIM
);
772 fprintf (stderr
, "), but the result is :");
773 print_gimple_stmt (stderr
, phi
, 0, TDF_SLIM
);
774 internal_error ("SSA corruption");
778 remove_phi_node (&gsi
, true);
782 /* Also remove real PHIs with no uses. */
783 if (has_zero_uses (result
))
785 remove_gimple_phi_args (phi
);
786 remove_phi_node (&gsi
, true);
796 /* This function will rewrite the current program using the variable mapping
797 found in MAP. If the replacement vector VALUES is provided, any
798 occurrences of partitions with non-null entries in the vector will be
799 replaced with the expression in the vector instead of its mapped
803 rewrite_trees (var_map map ATTRIBUTE_UNUSED
)
805 #ifdef ENABLE_CHECKING
807 /* Search for PHIs where the destination has no partition, but one
808 or more arguments has a partition. This should not happen and can
809 create incorrect code. */
812 gimple_stmt_iterator gsi
;
813 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
815 gimple phi
= gsi_stmt (gsi
);
816 tree T0
= var_to_partition_to_var (map
, gimple_phi_result (phi
));
820 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
822 tree arg
= PHI_ARG_DEF (phi
, i
);
824 if (TREE_CODE (arg
) == SSA_NAME
825 && var_to_partition (map
, arg
) != NO_PARTITION
)
827 fprintf (stderr
, "Argument of PHI is in a partition :(");
828 print_generic_expr (stderr
, arg
, TDF_SLIM
);
829 fprintf (stderr
, "), but the result is not :");
830 print_gimple_stmt (stderr
, phi
, 0, TDF_SLIM
);
831 internal_error ("SSA corruption");
840 /* Given the out-of-ssa info object SA (with prepared partitions)
841 eliminate all phi nodes in all basic blocks. Afterwards no
842 basic block will have phi nodes anymore and there are possibly
843 some RTL instructions inserted on edges. */
846 expand_phi_nodes (struct ssaexpand
*sa
)
849 elim_graph g
= new_elim_graph (sa
->map
->num_partitions
);
852 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
, EXIT_BLOCK_PTR
, next_bb
)
853 if (!gimple_seq_empty_p (phi_nodes (bb
)))
857 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
858 eliminate_phi (e
, g
);
859 set_phi_nodes (bb
, NULL
);
860 /* We can't redirect EH edges in RTL land, so we need to do this
861 here. Redirection happens only when splitting is necessary,
862 which it is only for critical edges, normally. For EH edges
863 it might also be necessary when the successor has more than
864 one predecessor. In that case the edge is either required to
865 be fallthru (which EH edges aren't), or the predecessor needs
866 to end with a jump (which again, isn't the case with EH edges).
867 Hence, split all EH edges on which we inserted instructions
868 and whose successor has multiple predecessors. */
869 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
871 if (e
->insns
.r
&& (e
->flags
& EDGE_EH
)
872 && !single_pred_p (e
->dest
))
874 rtx insns
= e
->insns
.r
;
876 e
->insns
.r
= NULL_RTX
;
878 single_pred_edge (bb
)->insns
.r
= insns
;
885 delete_elim_graph (g
);
889 /* Remove the ssa-names in the current function and translate them into normal
890 compiler variables. PERFORM_TER is true if Temporary Expression Replacement
891 should also be used. */
894 remove_ssa_form (bool perform_ter
, struct ssaexpand
*sa
)
896 bitmap values
= NULL
;
900 map
= coalesce_ssa_name ();
902 /* Return to viewing the variable list as just all reference variables after
903 coalescing has been performed. */
904 partition_view_normal (map
, false);
906 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
908 fprintf (dump_file
, "After Coalescing:\n");
909 dump_var_map (dump_file
, map
);
914 values
= find_replaceable_exprs (map
);
915 if (values
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
916 dump_replaceable_exprs (dump_file
, values
);
923 sa
->partition_has_default_def
= BITMAP_ALLOC (NULL
);
924 for (i
= 1; i
< num_ssa_names
; i
++)
926 tree t
= ssa_name (i
);
927 if (t
&& SSA_NAME_IS_DEFAULT_DEF (t
))
929 int p
= var_to_partition (map
, t
);
930 if (p
!= NO_PARTITION
)
931 bitmap_set_bit (sa
->partition_has_default_def
, p
);
937 /* If not already done so for basic block BB, assign increasing uids
938 to each of its instructions. */
941 maybe_renumber_stmts_bb (basic_block bb
)
944 gimple_stmt_iterator gsi
;
949 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
951 gimple stmt
= gsi_stmt (gsi
);
952 gimple_set_uid (stmt
, i
);
958 /* Return true if we can determine that the SSA_NAMEs RESULT (a result
959 of a PHI node) and ARG (one of its arguments) conflict. Return false
960 otherwise, also when we simply aren't sure. */
963 trivially_conflicts_p (basic_block bb
, tree result
, tree arg
)
966 imm_use_iterator imm_iter
;
967 gimple defa
= SSA_NAME_DEF_STMT (arg
);
969 /* If ARG isn't defined in the same block it's too complicated for
971 if (gimple_bb (defa
) != bb
)
974 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, result
)
976 gimple use_stmt
= USE_STMT (use
);
977 if (is_gimple_debug (use_stmt
))
979 /* Now, if there's a use of RESULT that lies outside this basic block,
980 then there surely is a conflict with ARG. */
981 if (gimple_bb (use_stmt
) != bb
)
983 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
985 /* The use now is in a real stmt of BB, so if ARG was defined
986 in a PHI node (like RESULT) both conflict. */
987 if (gimple_code (defa
) == GIMPLE_PHI
)
989 maybe_renumber_stmts_bb (bb
);
990 /* If the use of RESULT occurs after the definition of ARG,
991 the two conflict too. */
992 if (gimple_uid (defa
) < gimple_uid (use_stmt
))
1000 /* Search every PHI node for arguments associated with backedges which
1001 we can trivially determine will need a copy (the argument is either
1002 not an SSA_NAME or the argument has a different underlying variable
1003 than the PHI result).
1005 Insert a copy from the PHI argument to a new destination at the
1006 end of the block with the backedge to the top of the loop. Update
1007 the PHI argument to reference this new destination. */
1010 insert_backedge_copies (void)
1013 gimple_stmt_iterator gsi
;
1015 mark_dfs_back_edges ();
1019 /* Mark block as possibly needing calculation of UIDs. */
1022 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1024 gimple phi
= gsi_stmt (gsi
);
1025 tree result
= gimple_phi_result (phi
);
1028 if (virtual_operand_p (result
))
1031 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1033 tree arg
= gimple_phi_arg_def (phi
, i
);
1034 edge e
= gimple_phi_arg_edge (phi
, i
);
1036 /* If the argument is not an SSA_NAME, then we will need a
1037 constant initialization. If the argument is an SSA_NAME with
1038 a different underlying variable then a copy statement will be
1040 if ((e
->flags
& EDGE_DFS_BACK
)
1041 && (TREE_CODE (arg
) != SSA_NAME
1042 || SSA_NAME_VAR (arg
) != SSA_NAME_VAR (result
)
1043 || trivially_conflicts_p (bb
, result
, arg
)))
1046 gimple stmt
, last
= NULL
;
1047 gimple_stmt_iterator gsi2
;
1049 gsi2
= gsi_last_bb (gimple_phi_arg_edge (phi
, i
)->src
);
1050 if (!gsi_end_p (gsi2
))
1051 last
= gsi_stmt (gsi2
);
1053 /* In theory the only way we ought to get back to the
1054 start of a loop should be with a COND_EXPR or GOTO_EXPR.
1055 However, better safe than sorry.
1056 If the block ends with a control statement or
1057 something that might throw, then we have to
1058 insert this assignment before the last
1059 statement. Else insert it after the last statement. */
1060 if (last
&& stmt_ends_bb_p (last
))
1062 /* If the last statement in the block is the definition
1063 site of the PHI argument, then we can't insert
1064 anything after it. */
1065 if (TREE_CODE (arg
) == SSA_NAME
1066 && SSA_NAME_DEF_STMT (arg
) == last
)
1070 /* Create a new instance of the underlying variable of the
1072 name
= copy_ssa_name (result
, NULL
);
1073 stmt
= gimple_build_assign (name
,
1074 gimple_phi_arg_def (phi
, i
));
1076 /* copy location if present. */
1077 if (gimple_phi_arg_has_location (phi
, i
))
1078 gimple_set_location (stmt
,
1079 gimple_phi_arg_location (phi
, i
));
1081 /* Insert the new statement into the block and update
1083 if (last
&& stmt_ends_bb_p (last
))
1084 gsi_insert_before (&gsi2
, stmt
, GSI_NEW_STMT
);
1086 gsi_insert_after (&gsi2
, stmt
, GSI_NEW_STMT
);
1087 SET_PHI_ARG_DEF (phi
, i
, name
);
1092 /* Unmark this block again. */
1097 /* Free all memory associated with going out of SSA form. SA is
1098 the outof-SSA info object. */
1101 finish_out_of_ssa (struct ssaexpand
*sa
)
1103 free (sa
->partition_to_pseudo
);
1105 BITMAP_FREE (sa
->values
);
1106 delete_var_map (sa
->map
);
1107 BITMAP_FREE (sa
->partition_has_default_def
);
1108 memset (sa
, 0, sizeof *sa
);
1111 /* Take the current function out of SSA form, translating PHIs as described in
1112 R. Morgan, ``Building an Optimizing Compiler'',
1113 Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */
1116 rewrite_out_of_ssa (struct ssaexpand
*sa
)
1118 /* If elimination of a PHI requires inserting a copy on a backedge,
1119 then we will have to split the backedge which has numerous
1120 undesirable performance effects.
1122 A significant number of such cases can be handled here by inserting
1123 copies into the loop itself. */
1124 insert_backedge_copies ();
1127 /* Eliminate PHIs which are of no use, such as virtual or dead phis. */
1128 eliminate_useless_phis ();
1130 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1131 gimple_dump_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);
1133 remove_ssa_form (flag_tree_ter
, sa
);
1135 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1136 gimple_dump_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);