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"
32 #include "gimple-ssa.h"
34 #include "tree-phinodes.h"
35 #include "ssa-iterators.h"
36 #include "tree-ssanames.h"
38 #include "diagnostic-core.h"
39 #include "tree-ssa-live.h"
40 #include "tree-ssa-ter.h"
41 #include "tree-ssa-coalesce.h"
42 #include "tree-outof-ssa.h"
44 /* FIXME: A lot of code here deals with expanding to RTL. All that code
45 should be in cfgexpand.c. */
48 /* Return TRUE if expression STMT is suitable for replacement. */
51 ssa_is_replaceable_p (gimple stmt
)
57 /* Only consider modify stmts. */
58 if (!is_gimple_assign (stmt
))
61 /* If the statement may throw an exception, it cannot be replaced. */
62 if (stmt_could_throw_p (stmt
))
65 /* Punt if there is more than 1 def. */
66 def
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_DEF
);
70 /* Only consider definitions which have a single use. */
71 if (!single_imm_use (def
, &use_p
, &use_stmt
))
74 /* Used in this block, but at the TOP of the block, not the end. */
75 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
78 /* There must be no VDEFs. */
79 if (gimple_vdef (stmt
))
82 /* Float expressions must go through memory if float-store is on. */
84 && FLOAT_TYPE_P (gimple_expr_type (stmt
)))
87 /* An assignment with a register variable on the RHS is not
89 if (gimple_assign_rhs_code (stmt
) == VAR_DECL
90 && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt
)))
93 /* No function calls can be replaced. */
94 if (is_gimple_call (stmt
))
97 /* Leave any stmt with volatile operands alone as well. */
98 if (gimple_has_volatile_ops (stmt
))
105 /* Used to hold all the components required to do SSA PHI elimination.
106 The node and pred/succ list is a simple linear list of nodes and
107 edges represented as pairs of nodes.
109 The predecessor and successor list: Nodes are entered in pairs, where
110 [0] ->PRED, [1]->SUCC. All the even indexes in the array represent
111 predecessors, all the odd elements are successors.
114 When implemented as bitmaps, very large programs SSA->Normal times were
115 being dominated by clearing the interference graph.
117 Typically this list of edges is extremely small since it only includes
118 PHI results and uses from a single edge which have not coalesced with
119 each other. This means that no virtual PHI nodes are included, and
120 empirical evidence suggests that the number of edges rarely exceed
121 3, and in a bootstrap of GCC, the maximum size encountered was 7.
122 This also limits the number of possible nodes that are involved to
123 rarely more than 6, and in the bootstrap of gcc, the maximum number
124 of nodes encountered was 12. */
126 typedef struct _elim_graph
{
127 /* Size of the elimination vectors. */
130 /* List of nodes in the elimination graph. */
133 /* The predecessor and successor edge list. */
136 /* Source locus on each edge */
137 vec
<source_location
> edge_locus
;
139 /* Visited vector. */
142 /* Stack for visited nodes. */
145 /* The variable partition map. */
148 /* Edge being eliminated by this graph. */
151 /* List of constant copies to emit. These are pushed on in pairs. */
152 vec
<int> const_dests
;
153 vec
<tree
> const_copies
;
155 /* Source locations for any constant copies. */
156 vec
<source_location
> copy_locus
;
160 /* For an edge E find out a good source location to associate with
161 instructions inserted on edge E. If E has an implicit goto set,
162 use its location. Otherwise search instructions in predecessors
163 of E for a location, and use that one. That makes sense because
164 we insert on edges for PHI nodes, and effects of PHIs happen on
165 the end of the predecessor conceptually. */
168 set_location_for_edge (edge e
)
172 set_curr_insn_location (e
->goto_locus
);
176 basic_block bb
= e
->src
;
177 gimple_stmt_iterator gsi
;
181 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
183 gimple stmt
= gsi_stmt (gsi
);
184 if (is_gimple_debug (stmt
))
186 if (gimple_has_location (stmt
) || gimple_block (stmt
))
188 set_curr_insn_location (gimple_location (stmt
));
192 /* Nothing found in this basic block. Make a half-assed attempt
193 to continue with another block. */
194 if (single_pred_p (bb
))
195 bb
= single_pred (bb
);
199 while (bb
!= e
->src
);
203 /* Emit insns to copy SRC into DEST converting SRC if necessary. As
204 SRC/DEST might be BLKmode memory locations SIZEEXP is a tree from
205 which we deduce the size to copy in that case. */
208 emit_partition_copy (rtx dest
, rtx src
, int unsignedsrcp
, tree sizeexp
)
214 if (GET_MODE (src
) != VOIDmode
&& GET_MODE (src
) != GET_MODE (dest
))
215 src
= convert_to_mode (GET_MODE (dest
), src
, unsignedsrcp
);
216 if (GET_MODE (src
) == BLKmode
)
218 gcc_assert (GET_MODE (dest
) == BLKmode
);
219 emit_block_move (dest
, src
, expr_size (sizeexp
), BLOCK_OP_NORMAL
);
222 emit_move_insn (dest
, src
);
230 /* Insert a copy instruction from partition SRC to DEST onto edge E. */
233 insert_partition_copy_on_edge (edge e
, int dest
, int src
, source_location locus
)
237 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
240 "Inserting a partition copy on edge BB%d->BB%d :"
243 e
->dest
->index
, dest
, src
);
244 fprintf (dump_file
, "\n");
247 gcc_assert (SA
.partition_to_pseudo
[dest
]);
248 gcc_assert (SA
.partition_to_pseudo
[src
]);
250 set_location_for_edge (e
);
251 /* If a locus is provided, override the default. */
253 set_curr_insn_location (locus
);
255 var
= partition_to_var (SA
.map
, src
);
256 seq
= emit_partition_copy (SA
.partition_to_pseudo
[dest
],
257 SA
.partition_to_pseudo
[src
],
258 TYPE_UNSIGNED (TREE_TYPE (var
)),
261 insert_insn_on_edge (seq
, e
);
264 /* Insert a copy instruction from expression SRC to partition DEST
268 insert_value_copy_on_edge (edge e
, int dest
, tree src
, source_location locus
)
271 enum machine_mode dest_mode
, src_mode
;
275 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
278 "Inserting a value copy on edge BB%d->BB%d : PART.%d = ",
280 e
->dest
->index
, dest
);
281 print_generic_expr (dump_file
, src
, TDF_SLIM
);
282 fprintf (dump_file
, "\n");
285 gcc_assert (SA
.partition_to_pseudo
[dest
]);
287 set_location_for_edge (e
);
288 /* If a locus is provided, override the default. */
290 set_curr_insn_location (locus
);
294 var
= SSA_NAME_VAR (partition_to_var (SA
.map
, dest
));
295 src_mode
= TYPE_MODE (TREE_TYPE (src
));
296 dest_mode
= GET_MODE (SA
.partition_to_pseudo
[dest
]);
297 gcc_assert (src_mode
== TYPE_MODE (TREE_TYPE (var
)));
298 gcc_assert (!REG_P (SA
.partition_to_pseudo
[dest
])
299 || dest_mode
== promote_decl_mode (var
, &unsignedp
));
301 if (src_mode
!= dest_mode
)
303 x
= expand_expr (src
, NULL
, src_mode
, EXPAND_NORMAL
);
304 x
= convert_modes (dest_mode
, src_mode
, x
, unsignedp
);
306 else if (src_mode
== BLKmode
)
308 x
= SA
.partition_to_pseudo
[dest
];
309 store_expr (src
, x
, 0, false);
312 x
= expand_expr (src
, SA
.partition_to_pseudo
[dest
],
313 dest_mode
, EXPAND_NORMAL
);
315 if (x
!= SA
.partition_to_pseudo
[dest
])
316 emit_move_insn (SA
.partition_to_pseudo
[dest
], x
);
320 insert_insn_on_edge (seq
, e
);
323 /* Insert a copy instruction from RTL expression SRC to partition DEST
327 insert_rtx_to_part_on_edge (edge e
, int dest
, rtx src
, int unsignedsrcp
,
328 source_location locus
)
331 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
334 "Inserting a temp copy on edge BB%d->BB%d : PART.%d = ",
336 e
->dest
->index
, dest
);
337 print_simple_rtl (dump_file
, src
);
338 fprintf (dump_file
, "\n");
341 gcc_assert (SA
.partition_to_pseudo
[dest
]);
343 set_location_for_edge (e
);
344 /* If a locus is provided, override the default. */
346 set_curr_insn_location (locus
);
348 /* We give the destination as sizeexp in case src/dest are BLKmode
349 mems. Usually we give the source. As we result from SSA names
350 the left and right size should be the same (and no WITH_SIZE_EXPR
351 involved), so it doesn't matter. */
352 seq
= emit_partition_copy (SA
.partition_to_pseudo
[dest
],
354 partition_to_var (SA
.map
, dest
));
356 insert_insn_on_edge (seq
, e
);
359 /* Insert a copy instruction from partition SRC to RTL lvalue DEST
363 insert_part_to_rtx_on_edge (edge e
, rtx dest
, int src
, source_location locus
)
367 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
370 "Inserting a temp copy on edge BB%d->BB%d : ",
373 print_simple_rtl (dump_file
, dest
);
374 fprintf (dump_file
, "= PART.%d\n", src
);
377 gcc_assert (SA
.partition_to_pseudo
[src
]);
379 set_location_for_edge (e
);
380 /* If a locus is provided, override the default. */
382 set_curr_insn_location (locus
);
384 var
= partition_to_var (SA
.map
, src
);
385 seq
= emit_partition_copy (dest
,
386 SA
.partition_to_pseudo
[src
],
387 TYPE_UNSIGNED (TREE_TYPE (var
)),
390 insert_insn_on_edge (seq
, e
);
394 /* Create an elimination graph with SIZE nodes and associated data
398 new_elim_graph (int size
)
400 elim_graph g
= (elim_graph
) xmalloc (sizeof (struct _elim_graph
));
402 g
->nodes
.create (30);
403 g
->const_dests
.create (20);
404 g
->const_copies
.create (20);
405 g
->copy_locus
.create (10);
406 g
->edge_list
.create (20);
407 g
->edge_locus
.create (10);
408 g
->stack
.create (30);
410 g
->visited
= sbitmap_alloc (size
);
416 /* Empty elimination graph G. */
419 clear_elim_graph (elim_graph g
)
421 g
->nodes
.truncate (0);
422 g
->edge_list
.truncate (0);
423 g
->edge_locus
.truncate (0);
427 /* Delete elimination graph G. */
430 delete_elim_graph (elim_graph g
)
432 sbitmap_free (g
->visited
);
434 g
->edge_list
.release ();
435 g
->const_copies
.release ();
436 g
->const_dests
.release ();
438 g
->copy_locus
.release ();
439 g
->edge_locus
.release ();
445 /* Return the number of nodes in graph G. */
448 elim_graph_size (elim_graph g
)
450 return g
->nodes
.length ();
454 /* Add NODE to graph G, if it doesn't exist already. */
457 elim_graph_add_node (elim_graph g
, int node
)
462 FOR_EACH_VEC_ELT (g
->nodes
, x
, t
)
465 g
->nodes
.safe_push (node
);
469 /* Add the edge PRED->SUCC to graph G. */
472 elim_graph_add_edge (elim_graph g
, int pred
, int succ
, source_location locus
)
474 g
->edge_list
.safe_push (pred
);
475 g
->edge_list
.safe_push (succ
);
476 g
->edge_locus
.safe_push (locus
);
480 /* Remove an edge from graph G for which NODE is the predecessor, and
481 return the successor node. -1 is returned if there is no such edge. */
484 elim_graph_remove_succ_edge (elim_graph g
, int node
, source_location
*locus
)
488 for (x
= 0; x
< g
->edge_list
.length (); x
+= 2)
489 if (g
->edge_list
[x
] == node
)
491 g
->edge_list
[x
] = -1;
492 y
= g
->edge_list
[x
+ 1];
493 g
->edge_list
[x
+ 1] = -1;
494 *locus
= g
->edge_locus
[x
/ 2];
495 g
->edge_locus
[x
/ 2] = UNKNOWN_LOCATION
;
498 *locus
= UNKNOWN_LOCATION
;
503 /* Find all the nodes in GRAPH which are successors to NODE in the
504 edge list. VAR will hold the partition number found. CODE is the
505 code fragment executed for every node found. */
507 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, LOCUS, CODE) \
511 for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \
513 y_ = (GRAPH)->edge_list[x_]; \
516 (void) ((VAR) = (GRAPH)->edge_list[x_ + 1]); \
517 (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \
523 /* Find all the nodes which are predecessors of NODE in the edge list for
524 GRAPH. VAR will hold the partition number found. CODE is the
525 code fragment executed for every node found. */
527 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, LOCUS, CODE) \
531 for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \
533 y_ = (GRAPH)->edge_list[x_ + 1]; \
536 (void) ((VAR) = (GRAPH)->edge_list[x_]); \
537 (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \
543 /* Add T to elimination graph G. */
546 eliminate_name (elim_graph g
, int T
)
548 elim_graph_add_node (g
, T
);
551 /* Return true if this phi argument T should have a copy queued when using
552 var_map MAP. PHI nodes should contain only ssa_names and invariants. A
553 test for ssa_name is definitely simpler, but don't let invalid contents
554 slip through in the meantime. */
557 queue_phi_copy_p (var_map map
, tree t
)
559 if (TREE_CODE (t
) == SSA_NAME
)
561 if (var_to_partition (map
, t
) == NO_PARTITION
)
565 gcc_checking_assert (is_gimple_min_invariant (t
));
569 /* Build elimination graph G for basic block BB on incoming PHI edge
573 eliminate_build (elim_graph g
)
577 gimple_stmt_iterator gsi
;
579 clear_elim_graph (g
);
581 for (gsi
= gsi_start_phis (g
->e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
583 gimple phi
= gsi_stmt (gsi
);
584 source_location locus
;
586 p0
= var_to_partition (g
->map
, gimple_phi_result (phi
));
587 /* Ignore results which are not in partitions. */
588 if (p0
== NO_PARTITION
)
591 Ti
= PHI_ARG_DEF (phi
, g
->e
->dest_idx
);
592 locus
= gimple_phi_arg_location_from_edge (phi
, g
->e
);
594 /* If this argument is a constant, or a SSA_NAME which is being
595 left in SSA form, just queue a copy to be emitted on this
597 if (queue_phi_copy_p (g
->map
, Ti
))
599 /* Save constant copies until all other copies have been emitted
601 g
->const_dests
.safe_push (p0
);
602 g
->const_copies
.safe_push (Ti
);
603 g
->copy_locus
.safe_push (locus
);
607 pi
= var_to_partition (g
->map
, Ti
);
610 eliminate_name (g
, p0
);
611 eliminate_name (g
, pi
);
612 elim_graph_add_edge (g
, p0
, pi
, locus
);
619 /* Push successors of T onto the elimination stack for G. */
622 elim_forward (elim_graph g
, int T
)
625 source_location locus
;
627 bitmap_set_bit (g
->visited
, T
);
628 FOR_EACH_ELIM_GRAPH_SUCC (g
, T
, S
, locus
,
630 if (!bitmap_bit_p (g
->visited
, S
))
633 g
->stack
.safe_push (T
);
637 /* Return 1 if there unvisited predecessors of T in graph G. */
640 elim_unvisited_predecessor (elim_graph g
, int T
)
643 source_location locus
;
645 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
647 if (!bitmap_bit_p (g
->visited
, P
))
653 /* Process predecessors first, and insert a copy. */
656 elim_backward (elim_graph g
, int T
)
659 source_location locus
;
661 bitmap_set_bit (g
->visited
, T
);
662 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
664 if (!bitmap_bit_p (g
->visited
, P
))
666 elim_backward (g
, P
);
667 insert_partition_copy_on_edge (g
->e
, P
, T
, locus
);
672 /* Allocate a new pseudo register usable for storing values sitting
673 in NAME (a decl or SSA name), i.e. with matching mode and attributes. */
676 get_temp_reg (tree name
)
678 tree var
= TREE_CODE (name
) == SSA_NAME
? SSA_NAME_VAR (name
) : name
;
679 tree type
= TREE_TYPE (var
);
681 enum machine_mode reg_mode
= promote_decl_mode (var
, &unsignedp
);
682 rtx x
= gen_reg_rtx (reg_mode
);
683 if (POINTER_TYPE_P (type
))
684 mark_reg_pointer (x
, TYPE_ALIGN (TREE_TYPE (TREE_TYPE (var
))));
688 /* Insert required copies for T in graph G. Check for a strongly connected
689 region, and create a temporary to break the cycle if one is found. */
692 elim_create (elim_graph g
, int T
)
695 source_location locus
;
697 if (elim_unvisited_predecessor (g
, T
))
699 tree var
= partition_to_var (g
->map
, T
);
700 rtx U
= get_temp_reg (var
);
701 int unsignedsrcp
= TYPE_UNSIGNED (TREE_TYPE (var
));
703 insert_part_to_rtx_on_edge (g
->e
, U
, T
, UNKNOWN_LOCATION
);
704 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
706 if (!bitmap_bit_p (g
->visited
, P
))
708 elim_backward (g
, P
);
709 insert_rtx_to_part_on_edge (g
->e
, P
, U
, unsignedsrcp
, locus
);
715 S
= elim_graph_remove_succ_edge (g
, T
, &locus
);
718 bitmap_set_bit (g
->visited
, T
);
719 insert_partition_copy_on_edge (g
->e
, T
, S
, locus
);
725 /* Eliminate all the phi nodes on edge E in graph G. */
728 eliminate_phi (edge e
, elim_graph g
)
732 gcc_assert (g
->const_copies
.length () == 0);
733 gcc_assert (g
->copy_locus
.length () == 0);
735 /* Abnormal edges already have everything coalesced. */
736 if (e
->flags
& EDGE_ABNORMAL
)
743 if (elim_graph_size (g
) != 0)
747 bitmap_clear (g
->visited
);
748 g
->stack
.truncate (0);
750 FOR_EACH_VEC_ELT (g
->nodes
, x
, part
)
752 if (!bitmap_bit_p (g
->visited
, part
))
753 elim_forward (g
, part
);
756 bitmap_clear (g
->visited
);
757 while (g
->stack
.length () > 0)
760 if (!bitmap_bit_p (g
->visited
, x
))
765 /* If there are any pending constant copies, issue them now. */
766 while (g
->const_copies
.length () > 0)
770 source_location locus
;
772 src
= g
->const_copies
.pop ();
773 dest
= g
->const_dests
.pop ();
774 locus
= g
->copy_locus
.pop ();
775 insert_value_copy_on_edge (e
, dest
, src
, locus
);
780 /* Remove each argument from PHI. If an arg was the last use of an SSA_NAME,
781 check to see if this allows another PHI node to be removed. */
784 remove_gimple_phi_args (gimple phi
)
789 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
791 fprintf (dump_file
, "Removing Dead PHI definition: ");
792 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
795 FOR_EACH_PHI_ARG (arg_p
, phi
, iter
, SSA_OP_USE
)
797 tree arg
= USE_FROM_PTR (arg_p
);
798 if (TREE_CODE (arg
) == SSA_NAME
)
800 /* Remove the reference to the existing argument. */
801 SET_USE (arg_p
, NULL_TREE
);
802 if (has_zero_uses (arg
))
805 gimple_stmt_iterator gsi
;
807 stmt
= SSA_NAME_DEF_STMT (arg
);
809 /* Also remove the def if it is a PHI node. */
810 if (gimple_code (stmt
) == GIMPLE_PHI
)
812 remove_gimple_phi_args (stmt
);
813 gsi
= gsi_for_stmt (stmt
);
814 remove_phi_node (&gsi
, true);
822 /* Remove any PHI node which is a virtual PHI, or a PHI with no uses. */
825 eliminate_useless_phis (void)
828 gimple_stmt_iterator gsi
;
833 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); )
835 gimple phi
= gsi_stmt (gsi
);
836 result
= gimple_phi_result (phi
);
837 if (virtual_operand_p (result
))
839 #ifdef ENABLE_CHECKING
841 /* There should be no arguments which are not virtual, or the
842 results will be incorrect. */
843 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
845 tree arg
= PHI_ARG_DEF (phi
, i
);
846 if (TREE_CODE (arg
) == SSA_NAME
847 && !virtual_operand_p (arg
))
849 fprintf (stderr
, "Argument of PHI is not virtual (");
850 print_generic_expr (stderr
, arg
, TDF_SLIM
);
851 fprintf (stderr
, "), but the result is :");
852 print_gimple_stmt (stderr
, phi
, 0, TDF_SLIM
);
853 internal_error ("SSA corruption");
857 remove_phi_node (&gsi
, true);
861 /* Also remove real PHIs with no uses. */
862 if (has_zero_uses (result
))
864 remove_gimple_phi_args (phi
);
865 remove_phi_node (&gsi
, true);
875 /* This function will rewrite the current program using the variable mapping
876 found in MAP. If the replacement vector VALUES is provided, any
877 occurrences of partitions with non-null entries in the vector will be
878 replaced with the expression in the vector instead of its mapped
882 rewrite_trees (var_map map ATTRIBUTE_UNUSED
)
884 #ifdef ENABLE_CHECKING
886 /* Search for PHIs where the destination has no partition, but one
887 or more arguments has a partition. This should not happen and can
888 create incorrect code. */
891 gimple_stmt_iterator gsi
;
892 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
894 gimple phi
= gsi_stmt (gsi
);
895 tree T0
= var_to_partition_to_var (map
, gimple_phi_result (phi
));
899 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
901 tree arg
= PHI_ARG_DEF (phi
, i
);
903 if (TREE_CODE (arg
) == SSA_NAME
904 && var_to_partition (map
, arg
) != NO_PARTITION
)
906 fprintf (stderr
, "Argument of PHI is in a partition :(");
907 print_generic_expr (stderr
, arg
, TDF_SLIM
);
908 fprintf (stderr
, "), but the result is not :");
909 print_gimple_stmt (stderr
, phi
, 0, TDF_SLIM
);
910 internal_error ("SSA corruption");
919 /* Given the out-of-ssa info object SA (with prepared partitions)
920 eliminate all phi nodes in all basic blocks. Afterwards no
921 basic block will have phi nodes anymore and there are possibly
922 some RTL instructions inserted on edges. */
925 expand_phi_nodes (struct ssaexpand
*sa
)
928 elim_graph g
= new_elim_graph (sa
->map
->num_partitions
);
931 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
, EXIT_BLOCK_PTR
, next_bb
)
932 if (!gimple_seq_empty_p (phi_nodes (bb
)))
936 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
937 eliminate_phi (e
, g
);
938 set_phi_nodes (bb
, NULL
);
939 /* We can't redirect EH edges in RTL land, so we need to do this
940 here. Redirection happens only when splitting is necessary,
941 which it is only for critical edges, normally. For EH edges
942 it might also be necessary when the successor has more than
943 one predecessor. In that case the edge is either required to
944 be fallthru (which EH edges aren't), or the predecessor needs
945 to end with a jump (which again, isn't the case with EH edges).
946 Hence, split all EH edges on which we inserted instructions
947 and whose successor has multiple predecessors. */
948 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
950 if (e
->insns
.r
&& (e
->flags
& EDGE_EH
)
951 && !single_pred_p (e
->dest
))
953 rtx insns
= e
->insns
.r
;
955 e
->insns
.r
= NULL_RTX
;
957 single_pred_edge (bb
)->insns
.r
= insns
;
964 delete_elim_graph (g
);
968 /* Remove the ssa-names in the current function and translate them into normal
969 compiler variables. PERFORM_TER is true if Temporary Expression Replacement
970 should also be used. */
973 remove_ssa_form (bool perform_ter
, struct ssaexpand
*sa
)
975 bitmap values
= NULL
;
979 map
= coalesce_ssa_name ();
981 /* Return to viewing the variable list as just all reference variables after
982 coalescing has been performed. */
983 partition_view_normal (map
, false);
985 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
987 fprintf (dump_file
, "After Coalescing:\n");
988 dump_var_map (dump_file
, map
);
993 values
= find_replaceable_exprs (map
);
994 if (values
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
995 dump_replaceable_exprs (dump_file
, values
);
1001 sa
->values
= values
;
1002 sa
->partition_has_default_def
= BITMAP_ALLOC (NULL
);
1003 for (i
= 1; i
< num_ssa_names
; i
++)
1005 tree t
= ssa_name (i
);
1006 if (t
&& SSA_NAME_IS_DEFAULT_DEF (t
))
1008 int p
= var_to_partition (map
, t
);
1009 if (p
!= NO_PARTITION
)
1010 bitmap_set_bit (sa
->partition_has_default_def
, p
);
1016 /* If not already done so for basic block BB, assign increasing uids
1017 to each of its instructions. */
1020 maybe_renumber_stmts_bb (basic_block bb
)
1023 gimple_stmt_iterator gsi
;
1028 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1030 gimple stmt
= gsi_stmt (gsi
);
1031 gimple_set_uid (stmt
, i
);
1037 /* Return true if we can determine that the SSA_NAMEs RESULT (a result
1038 of a PHI node) and ARG (one of its arguments) conflict. Return false
1039 otherwise, also when we simply aren't sure. */
1042 trivially_conflicts_p (basic_block bb
, tree result
, tree arg
)
1045 imm_use_iterator imm_iter
;
1046 gimple defa
= SSA_NAME_DEF_STMT (arg
);
1048 /* If ARG isn't defined in the same block it's too complicated for
1050 if (gimple_bb (defa
) != bb
)
1053 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, result
)
1055 gimple use_stmt
= USE_STMT (use
);
1056 if (is_gimple_debug (use_stmt
))
1058 /* Now, if there's a use of RESULT that lies outside this basic block,
1059 then there surely is a conflict with ARG. */
1060 if (gimple_bb (use_stmt
) != bb
)
1062 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
1064 /* The use now is in a real stmt of BB, so if ARG was defined
1065 in a PHI node (like RESULT) both conflict. */
1066 if (gimple_code (defa
) == GIMPLE_PHI
)
1068 maybe_renumber_stmts_bb (bb
);
1069 /* If the use of RESULT occurs after the definition of ARG,
1070 the two conflict too. */
1071 if (gimple_uid (defa
) < gimple_uid (use_stmt
))
1079 /* Search every PHI node for arguments associated with backedges which
1080 we can trivially determine will need a copy (the argument is either
1081 not an SSA_NAME or the argument has a different underlying variable
1082 than the PHI result).
1084 Insert a copy from the PHI argument to a new destination at the
1085 end of the block with the backedge to the top of the loop. Update
1086 the PHI argument to reference this new destination. */
1089 insert_backedge_copies (void)
1092 gimple_stmt_iterator gsi
;
1094 mark_dfs_back_edges ();
1098 /* Mark block as possibly needing calculation of UIDs. */
1101 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1103 gimple phi
= gsi_stmt (gsi
);
1104 tree result
= gimple_phi_result (phi
);
1107 if (virtual_operand_p (result
))
1110 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1112 tree arg
= gimple_phi_arg_def (phi
, i
);
1113 edge e
= gimple_phi_arg_edge (phi
, i
);
1115 /* If the argument is not an SSA_NAME, then we will need a
1116 constant initialization. If the argument is an SSA_NAME with
1117 a different underlying variable then a copy statement will be
1119 if ((e
->flags
& EDGE_DFS_BACK
)
1120 && (TREE_CODE (arg
) != SSA_NAME
1121 || SSA_NAME_VAR (arg
) != SSA_NAME_VAR (result
)
1122 || trivially_conflicts_p (bb
, result
, arg
)))
1125 gimple stmt
, last
= NULL
;
1126 gimple_stmt_iterator gsi2
;
1128 gsi2
= gsi_last_bb (gimple_phi_arg_edge (phi
, i
)->src
);
1129 if (!gsi_end_p (gsi2
))
1130 last
= gsi_stmt (gsi2
);
1132 /* In theory the only way we ought to get back to the
1133 start of a loop should be with a COND_EXPR or GOTO_EXPR.
1134 However, better safe than sorry.
1135 If the block ends with a control statement or
1136 something that might throw, then we have to
1137 insert this assignment before the last
1138 statement. Else insert it after the last statement. */
1139 if (last
&& stmt_ends_bb_p (last
))
1141 /* If the last statement in the block is the definition
1142 site of the PHI argument, then we can't insert
1143 anything after it. */
1144 if (TREE_CODE (arg
) == SSA_NAME
1145 && SSA_NAME_DEF_STMT (arg
) == last
)
1149 /* Create a new instance of the underlying variable of the
1151 name
= copy_ssa_name (result
, NULL
);
1152 stmt
= gimple_build_assign (name
,
1153 gimple_phi_arg_def (phi
, i
));
1155 /* copy location if present. */
1156 if (gimple_phi_arg_has_location (phi
, i
))
1157 gimple_set_location (stmt
,
1158 gimple_phi_arg_location (phi
, i
));
1160 /* Insert the new statement into the block and update
1162 if (last
&& stmt_ends_bb_p (last
))
1163 gsi_insert_before (&gsi2
, stmt
, GSI_NEW_STMT
);
1165 gsi_insert_after (&gsi2
, stmt
, GSI_NEW_STMT
);
1166 SET_PHI_ARG_DEF (phi
, i
, name
);
1171 /* Unmark this block again. */
1176 /* Free all memory associated with going out of SSA form. SA is
1177 the outof-SSA info object. */
1180 finish_out_of_ssa (struct ssaexpand
*sa
)
1182 free (sa
->partition_to_pseudo
);
1184 BITMAP_FREE (sa
->values
);
1185 delete_var_map (sa
->map
);
1186 BITMAP_FREE (sa
->partition_has_default_def
);
1187 memset (sa
, 0, sizeof *sa
);
1190 /* Take the current function out of SSA form, translating PHIs as described in
1191 R. Morgan, ``Building an Optimizing Compiler'',
1192 Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */
1195 rewrite_out_of_ssa (struct ssaexpand
*sa
)
1197 /* If elimination of a PHI requires inserting a copy on a backedge,
1198 then we will have to split the backedge which has numerous
1199 undesirable performance effects.
1201 A significant number of such cases can be handled here by inserting
1202 copies into the loop itself. */
1203 insert_backedge_copies ();
1206 /* Eliminate PHIs which are of no use, such as virtual or dead phis. */
1207 eliminate_useless_phis ();
1209 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1210 gimple_dump_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);
1212 remove_ssa_form (flag_tree_ter
, sa
);
1214 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1215 gimple_dump_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);