1 /* Convert a program in SSA form into Normal form.
2 Copyright (C) 2004-2015 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"
28 #include "double-int.h"
35 #include "fold-const.h"
36 #include "stor-layout.h"
38 #include "hard-reg-set.h"
41 #include "dominance.h"
45 #include "basic-block.h"
46 #include "gimple-pretty-print.h"
49 #include "tree-ssa-alias.h"
50 #include "internal-fn.h"
52 #include "gimple-expr.h"
55 #include "gimple-iterator.h"
56 #include "gimple-ssa.h"
58 #include "tree-phinodes.h"
59 #include "ssa-iterators.h"
60 #include "stringpool.h"
61 #include "tree-ssanames.h"
63 #include "diagnostic-core.h"
64 #include "tree-ssa-live.h"
65 #include "tree-ssa-ter.h"
66 #include "tree-ssa-coalesce.h"
67 #include "tree-outof-ssa.h"
69 /* FIXME: A lot of code here deals with expanding to RTL. All that code
70 should be in cfgexpand.c. */
73 /* Return TRUE if expression STMT is suitable for replacement. */
76 ssa_is_replaceable_p (gimple stmt
)
82 /* Only consider modify stmts. */
83 if (!is_gimple_assign (stmt
))
86 /* If the statement may throw an exception, it cannot be replaced. */
87 if (stmt_could_throw_p (stmt
))
90 /* Punt if there is more than 1 def. */
91 def
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_DEF
);
95 /* Only consider definitions which have a single use. */
96 if (!single_imm_use (def
, &use_p
, &use_stmt
))
99 /* Used in this block, but at the TOP of the block, not the end. */
100 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
103 /* There must be no VDEFs. */
104 if (gimple_vdef (stmt
))
107 /* Float expressions must go through memory if float-store is on. */
109 && FLOAT_TYPE_P (gimple_expr_type (stmt
)))
112 /* An assignment with a register variable on the RHS is not
114 if (gimple_assign_rhs_code (stmt
) == VAR_DECL
115 && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt
)))
118 /* No function calls can be replaced. */
119 if (is_gimple_call (stmt
))
122 /* Leave any stmt with volatile operands alone as well. */
123 if (gimple_has_volatile_ops (stmt
))
130 /* Used to hold all the components required to do SSA PHI elimination.
131 The node and pred/succ list is a simple linear list of nodes and
132 edges represented as pairs of nodes.
134 The predecessor and successor list: Nodes are entered in pairs, where
135 [0] ->PRED, [1]->SUCC. All the even indexes in the array represent
136 predecessors, all the odd elements are successors.
139 When implemented as bitmaps, very large programs SSA->Normal times were
140 being dominated by clearing the interference graph.
142 Typically this list of edges is extremely small since it only includes
143 PHI results and uses from a single edge which have not coalesced with
144 each other. This means that no virtual PHI nodes are included, and
145 empirical evidence suggests that the number of edges rarely exceed
146 3, and in a bootstrap of GCC, the maximum size encountered was 7.
147 This also limits the number of possible nodes that are involved to
148 rarely more than 6, and in the bootstrap of gcc, the maximum number
149 of nodes encountered was 12. */
151 typedef struct _elim_graph
{
152 /* Size of the elimination vectors. */
155 /* List of nodes in the elimination graph. */
158 /* The predecessor and successor edge list. */
161 /* Source locus on each edge */
162 vec
<source_location
> edge_locus
;
164 /* Visited vector. */
167 /* Stack for visited nodes. */
170 /* The variable partition map. */
173 /* Edge being eliminated by this graph. */
176 /* List of constant copies to emit. These are pushed on in pairs. */
177 vec
<int> const_dests
;
178 vec
<tree
> const_copies
;
180 /* Source locations for any constant copies. */
181 vec
<source_location
> copy_locus
;
185 /* For an edge E find out a good source location to associate with
186 instructions inserted on edge E. If E has an implicit goto set,
187 use its location. Otherwise search instructions in predecessors
188 of E for a location, and use that one. That makes sense because
189 we insert on edges for PHI nodes, and effects of PHIs happen on
190 the end of the predecessor conceptually. */
193 set_location_for_edge (edge e
)
197 set_curr_insn_location (e
->goto_locus
);
201 basic_block bb
= e
->src
;
202 gimple_stmt_iterator gsi
;
206 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
208 gimple stmt
= gsi_stmt (gsi
);
209 if (is_gimple_debug (stmt
))
211 if (gimple_has_location (stmt
) || gimple_block (stmt
))
213 set_curr_insn_location (gimple_location (stmt
));
217 /* Nothing found in this basic block. Make a half-assed attempt
218 to continue with another block. */
219 if (single_pred_p (bb
))
220 bb
= single_pred (bb
);
224 while (bb
!= e
->src
);
228 /* Emit insns to copy SRC into DEST converting SRC if necessary. As
229 SRC/DEST might be BLKmode memory locations SIZEEXP is a tree from
230 which we deduce the size to copy in that case. */
233 emit_partition_copy (rtx dest
, rtx src
, int unsignedsrcp
, tree sizeexp
)
239 if (GET_MODE (src
) != VOIDmode
&& GET_MODE (src
) != GET_MODE (dest
))
240 src
= convert_to_mode (GET_MODE (dest
), src
, unsignedsrcp
);
241 if (GET_MODE (src
) == BLKmode
)
243 gcc_assert (GET_MODE (dest
) == BLKmode
);
244 emit_block_move (dest
, src
, expr_size (sizeexp
), BLOCK_OP_NORMAL
);
247 emit_move_insn (dest
, src
);
255 /* Insert a copy instruction from partition SRC to DEST onto edge E. */
258 insert_partition_copy_on_edge (edge e
, int dest
, int src
, source_location locus
)
262 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
265 "Inserting a partition copy on edge BB%d->BB%d :"
268 e
->dest
->index
, dest
, src
);
269 fprintf (dump_file
, "\n");
272 gcc_assert (SA
.partition_to_pseudo
[dest
]);
273 gcc_assert (SA
.partition_to_pseudo
[src
]);
275 set_location_for_edge (e
);
276 /* If a locus is provided, override the default. */
278 set_curr_insn_location (locus
);
280 var
= partition_to_var (SA
.map
, src
);
281 seq
= emit_partition_copy (copy_rtx (SA
.partition_to_pseudo
[dest
]),
282 copy_rtx (SA
.partition_to_pseudo
[src
]),
283 TYPE_UNSIGNED (TREE_TYPE (var
)),
286 insert_insn_on_edge (seq
, e
);
289 /* Insert a copy instruction from expression SRC to partition DEST
293 insert_value_copy_on_edge (edge e
, int dest
, tree src
, source_location locus
)
295 rtx dest_rtx
, seq
, x
;
296 machine_mode dest_mode
, src_mode
;
300 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
303 "Inserting a value copy on edge BB%d->BB%d : PART.%d = ",
305 e
->dest
->index
, dest
);
306 print_generic_expr (dump_file
, src
, TDF_SLIM
);
307 fprintf (dump_file
, "\n");
310 dest_rtx
= copy_rtx (SA
.partition_to_pseudo
[dest
]);
311 gcc_assert (dest_rtx
);
313 set_location_for_edge (e
);
314 /* If a locus is provided, override the default. */
316 set_curr_insn_location (locus
);
320 var
= SSA_NAME_VAR (partition_to_var (SA
.map
, dest
));
321 src_mode
= TYPE_MODE (TREE_TYPE (src
));
322 dest_mode
= GET_MODE (dest_rtx
);
323 gcc_assert (src_mode
== TYPE_MODE (TREE_TYPE (var
)));
324 gcc_assert (!REG_P (dest_rtx
)
325 || dest_mode
== promote_decl_mode (var
, &unsignedp
));
327 if (src_mode
!= dest_mode
)
329 x
= expand_expr (src
, NULL
, src_mode
, EXPAND_NORMAL
);
330 x
= convert_modes (dest_mode
, src_mode
, x
, unsignedp
);
332 else if (src_mode
== BLKmode
)
335 store_expr (src
, x
, 0, false);
338 x
= expand_expr (src
, dest_rtx
, dest_mode
, EXPAND_NORMAL
);
341 emit_move_insn (dest_rtx
, x
);
345 insert_insn_on_edge (seq
, e
);
348 /* Insert a copy instruction from RTL expression SRC to partition DEST
352 insert_rtx_to_part_on_edge (edge e
, int dest
, rtx src
, int unsignedsrcp
,
353 source_location locus
)
356 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
359 "Inserting a temp copy on edge BB%d->BB%d : PART.%d = ",
361 e
->dest
->index
, dest
);
362 print_simple_rtl (dump_file
, src
);
363 fprintf (dump_file
, "\n");
366 gcc_assert (SA
.partition_to_pseudo
[dest
]);
368 set_location_for_edge (e
);
369 /* If a locus is provided, override the default. */
371 set_curr_insn_location (locus
);
373 /* We give the destination as sizeexp in case src/dest are BLKmode
374 mems. Usually we give the source. As we result from SSA names
375 the left and right size should be the same (and no WITH_SIZE_EXPR
376 involved), so it doesn't matter. */
377 seq
= emit_partition_copy (copy_rtx (SA
.partition_to_pseudo
[dest
]),
379 partition_to_var (SA
.map
, dest
));
381 insert_insn_on_edge (seq
, e
);
384 /* Insert a copy instruction from partition SRC to RTL lvalue DEST
388 insert_part_to_rtx_on_edge (edge e
, rtx dest
, int src
, source_location locus
)
392 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
395 "Inserting a temp copy on edge BB%d->BB%d : ",
398 print_simple_rtl (dump_file
, dest
);
399 fprintf (dump_file
, "= PART.%d\n", src
);
402 gcc_assert (SA
.partition_to_pseudo
[src
]);
404 set_location_for_edge (e
);
405 /* If a locus is provided, override the default. */
407 set_curr_insn_location (locus
);
409 var
= partition_to_var (SA
.map
, src
);
410 seq
= emit_partition_copy (dest
,
411 copy_rtx (SA
.partition_to_pseudo
[src
]),
412 TYPE_UNSIGNED (TREE_TYPE (var
)),
415 insert_insn_on_edge (seq
, e
);
419 /* Create an elimination graph with SIZE nodes and associated data
423 new_elim_graph (int size
)
425 elim_graph g
= (elim_graph
) xmalloc (sizeof (struct _elim_graph
));
427 g
->nodes
.create (30);
428 g
->const_dests
.create (20);
429 g
->const_copies
.create (20);
430 g
->copy_locus
.create (10);
431 g
->edge_list
.create (20);
432 g
->edge_locus
.create (10);
433 g
->stack
.create (30);
435 g
->visited
= sbitmap_alloc (size
);
441 /* Empty elimination graph G. */
444 clear_elim_graph (elim_graph g
)
446 g
->nodes
.truncate (0);
447 g
->edge_list
.truncate (0);
448 g
->edge_locus
.truncate (0);
452 /* Delete elimination graph G. */
455 delete_elim_graph (elim_graph g
)
457 sbitmap_free (g
->visited
);
459 g
->edge_list
.release ();
460 g
->const_copies
.release ();
461 g
->const_dests
.release ();
463 g
->copy_locus
.release ();
464 g
->edge_locus
.release ();
470 /* Return the number of nodes in graph G. */
473 elim_graph_size (elim_graph g
)
475 return g
->nodes
.length ();
479 /* Add NODE to graph G, if it doesn't exist already. */
482 elim_graph_add_node (elim_graph g
, int node
)
487 FOR_EACH_VEC_ELT (g
->nodes
, x
, t
)
490 g
->nodes
.safe_push (node
);
494 /* Add the edge PRED->SUCC to graph G. */
497 elim_graph_add_edge (elim_graph g
, int pred
, int succ
, source_location locus
)
499 g
->edge_list
.safe_push (pred
);
500 g
->edge_list
.safe_push (succ
);
501 g
->edge_locus
.safe_push (locus
);
505 /* Remove an edge from graph G for which NODE is the predecessor, and
506 return the successor node. -1 is returned if there is no such edge. */
509 elim_graph_remove_succ_edge (elim_graph g
, int node
, source_location
*locus
)
513 for (x
= 0; x
< g
->edge_list
.length (); x
+= 2)
514 if (g
->edge_list
[x
] == node
)
516 g
->edge_list
[x
] = -1;
517 y
= g
->edge_list
[x
+ 1];
518 g
->edge_list
[x
+ 1] = -1;
519 *locus
= g
->edge_locus
[x
/ 2];
520 g
->edge_locus
[x
/ 2] = UNKNOWN_LOCATION
;
523 *locus
= UNKNOWN_LOCATION
;
528 /* Find all the nodes in GRAPH which are successors to NODE in the
529 edge list. VAR will hold the partition number found. CODE is the
530 code fragment executed for every node found. */
532 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, LOCUS, CODE) \
536 for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \
538 y_ = (GRAPH)->edge_list[x_]; \
541 (void) ((VAR) = (GRAPH)->edge_list[x_ + 1]); \
542 (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \
548 /* Find all the nodes which are predecessors of NODE in the edge list for
549 GRAPH. VAR will hold the partition number found. CODE is the
550 code fragment executed for every node found. */
552 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, LOCUS, CODE) \
556 for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \
558 y_ = (GRAPH)->edge_list[x_ + 1]; \
561 (void) ((VAR) = (GRAPH)->edge_list[x_]); \
562 (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \
568 /* Add T to elimination graph G. */
571 eliminate_name (elim_graph g
, int T
)
573 elim_graph_add_node (g
, T
);
576 /* Return true if this phi argument T should have a copy queued when using
577 var_map MAP. PHI nodes should contain only ssa_names and invariants. A
578 test for ssa_name is definitely simpler, but don't let invalid contents
579 slip through in the meantime. */
582 queue_phi_copy_p (var_map map
, tree t
)
584 if (TREE_CODE (t
) == SSA_NAME
)
586 if (var_to_partition (map
, t
) == NO_PARTITION
)
590 gcc_checking_assert (is_gimple_min_invariant (t
));
594 /* Build elimination graph G for basic block BB on incoming PHI edge
598 eliminate_build (elim_graph g
)
604 clear_elim_graph (g
);
606 for (gsi
= gsi_start_phis (g
->e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
608 gphi
*phi
= gsi
.phi ();
609 source_location locus
;
611 p0
= var_to_partition (g
->map
, gimple_phi_result (phi
));
612 /* Ignore results which are not in partitions. */
613 if (p0
== NO_PARTITION
)
616 Ti
= PHI_ARG_DEF (phi
, g
->e
->dest_idx
);
617 locus
= gimple_phi_arg_location_from_edge (phi
, g
->e
);
619 /* If this argument is a constant, or a SSA_NAME which is being
620 left in SSA form, just queue a copy to be emitted on this
622 if (queue_phi_copy_p (g
->map
, Ti
))
624 /* Save constant copies until all other copies have been emitted
626 g
->const_dests
.safe_push (p0
);
627 g
->const_copies
.safe_push (Ti
);
628 g
->copy_locus
.safe_push (locus
);
632 pi
= var_to_partition (g
->map
, Ti
);
635 eliminate_name (g
, p0
);
636 eliminate_name (g
, pi
);
637 elim_graph_add_edge (g
, p0
, pi
, locus
);
644 /* Push successors of T onto the elimination stack for G. */
647 elim_forward (elim_graph g
, int T
)
650 source_location locus
;
652 bitmap_set_bit (g
->visited
, T
);
653 FOR_EACH_ELIM_GRAPH_SUCC (g
, T
, S
, locus
,
655 if (!bitmap_bit_p (g
->visited
, S
))
658 g
->stack
.safe_push (T
);
662 /* Return 1 if there unvisited predecessors of T in graph G. */
665 elim_unvisited_predecessor (elim_graph g
, int T
)
668 source_location locus
;
670 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
672 if (!bitmap_bit_p (g
->visited
, P
))
678 /* Process predecessors first, and insert a copy. */
681 elim_backward (elim_graph g
, int T
)
684 source_location locus
;
686 bitmap_set_bit (g
->visited
, T
);
687 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
689 if (!bitmap_bit_p (g
->visited
, P
))
691 elim_backward (g
, P
);
692 insert_partition_copy_on_edge (g
->e
, P
, T
, locus
);
697 /* Allocate a new pseudo register usable for storing values sitting
698 in NAME (a decl or SSA name), i.e. with matching mode and attributes. */
701 get_temp_reg (tree name
)
703 tree var
= TREE_CODE (name
) == SSA_NAME
? SSA_NAME_VAR (name
) : name
;
704 tree type
= TREE_TYPE (var
);
706 machine_mode reg_mode
= promote_decl_mode (var
, &unsignedp
);
707 rtx x
= gen_reg_rtx (reg_mode
);
708 if (POINTER_TYPE_P (type
))
709 mark_reg_pointer (x
, TYPE_ALIGN (TREE_TYPE (TREE_TYPE (var
))));
713 /* Insert required copies for T in graph G. Check for a strongly connected
714 region, and create a temporary to break the cycle if one is found. */
717 elim_create (elim_graph g
, int T
)
720 source_location locus
;
722 if (elim_unvisited_predecessor (g
, T
))
724 tree var
= partition_to_var (g
->map
, T
);
725 rtx U
= get_temp_reg (var
);
726 int unsignedsrcp
= TYPE_UNSIGNED (TREE_TYPE (var
));
728 insert_part_to_rtx_on_edge (g
->e
, U
, T
, UNKNOWN_LOCATION
);
729 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
731 if (!bitmap_bit_p (g
->visited
, P
))
733 elim_backward (g
, P
);
734 insert_rtx_to_part_on_edge (g
->e
, P
, U
, unsignedsrcp
, locus
);
740 S
= elim_graph_remove_succ_edge (g
, T
, &locus
);
743 bitmap_set_bit (g
->visited
, T
);
744 insert_partition_copy_on_edge (g
->e
, T
, S
, locus
);
750 /* Eliminate all the phi nodes on edge E in graph G. */
753 eliminate_phi (edge e
, elim_graph g
)
757 gcc_assert (g
->const_copies
.length () == 0);
758 gcc_assert (g
->copy_locus
.length () == 0);
760 /* Abnormal edges already have everything coalesced. */
761 if (e
->flags
& EDGE_ABNORMAL
)
768 if (elim_graph_size (g
) != 0)
772 bitmap_clear (g
->visited
);
773 g
->stack
.truncate (0);
775 FOR_EACH_VEC_ELT (g
->nodes
, x
, part
)
777 if (!bitmap_bit_p (g
->visited
, part
))
778 elim_forward (g
, part
);
781 bitmap_clear (g
->visited
);
782 while (g
->stack
.length () > 0)
785 if (!bitmap_bit_p (g
->visited
, x
))
790 /* If there are any pending constant copies, issue them now. */
791 while (g
->const_copies
.length () > 0)
795 source_location locus
;
797 src
= g
->const_copies
.pop ();
798 dest
= g
->const_dests
.pop ();
799 locus
= g
->copy_locus
.pop ();
800 insert_value_copy_on_edge (e
, dest
, src
, locus
);
805 /* Remove each argument from PHI. If an arg was the last use of an SSA_NAME,
806 check to see if this allows another PHI node to be removed. */
809 remove_gimple_phi_args (gphi
*phi
)
814 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
816 fprintf (dump_file
, "Removing Dead PHI definition: ");
817 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
820 FOR_EACH_PHI_ARG (arg_p
, phi
, iter
, SSA_OP_USE
)
822 tree arg
= USE_FROM_PTR (arg_p
);
823 if (TREE_CODE (arg
) == SSA_NAME
)
825 /* Remove the reference to the existing argument. */
826 SET_USE (arg_p
, NULL_TREE
);
827 if (has_zero_uses (arg
))
830 gimple_stmt_iterator gsi
;
832 stmt
= SSA_NAME_DEF_STMT (arg
);
834 /* Also remove the def if it is a PHI node. */
835 if (gimple_code (stmt
) == GIMPLE_PHI
)
837 remove_gimple_phi_args (as_a
<gphi
*> (stmt
));
838 gsi
= gsi_for_stmt (stmt
);
839 remove_phi_node (&gsi
, true);
847 /* Remove any PHI node which is a virtual PHI, or a PHI with no uses. */
850 eliminate_useless_phis (void)
856 FOR_EACH_BB_FN (bb
, cfun
)
858 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); )
860 gphi
*phi
= gsi
.phi ();
861 result
= gimple_phi_result (phi
);
862 if (virtual_operand_p (result
))
864 #ifdef ENABLE_CHECKING
866 /* There should be no arguments which are not virtual, or the
867 results will be incorrect. */
868 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
870 tree arg
= PHI_ARG_DEF (phi
, i
);
871 if (TREE_CODE (arg
) == SSA_NAME
872 && !virtual_operand_p (arg
))
874 fprintf (stderr
, "Argument of PHI is not virtual (");
875 print_generic_expr (stderr
, arg
, TDF_SLIM
);
876 fprintf (stderr
, "), but the result is :");
877 print_gimple_stmt (stderr
, phi
, 0, TDF_SLIM
);
878 internal_error ("SSA corruption");
882 remove_phi_node (&gsi
, true);
886 /* Also remove real PHIs with no uses. */
887 if (has_zero_uses (result
))
889 remove_gimple_phi_args (phi
);
890 remove_phi_node (&gsi
, true);
900 /* This function will rewrite the current program using the variable mapping
901 found in MAP. If the replacement vector VALUES is provided, any
902 occurrences of partitions with non-null entries in the vector will be
903 replaced with the expression in the vector instead of its mapped
907 rewrite_trees (var_map map ATTRIBUTE_UNUSED
)
909 #ifdef ENABLE_CHECKING
911 /* Search for PHIs where the destination has no partition, but one
912 or more arguments has a partition. This should not happen and can
913 create incorrect code. */
914 FOR_EACH_BB_FN (bb
, cfun
)
917 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
919 gphi
*phi
= gsi
.phi ();
920 tree T0
= var_to_partition_to_var (map
, gimple_phi_result (phi
));
924 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
926 tree arg
= PHI_ARG_DEF (phi
, i
);
928 if (TREE_CODE (arg
) == SSA_NAME
929 && var_to_partition (map
, arg
) != NO_PARTITION
)
931 fprintf (stderr
, "Argument of PHI is in a partition :(");
932 print_generic_expr (stderr
, arg
, TDF_SLIM
);
933 fprintf (stderr
, "), but the result is not :");
934 print_gimple_stmt (stderr
, phi
, 0, TDF_SLIM
);
935 internal_error ("SSA corruption");
944 /* Given the out-of-ssa info object SA (with prepared partitions)
945 eliminate all phi nodes in all basic blocks. Afterwards no
946 basic block will have phi nodes anymore and there are possibly
947 some RTL instructions inserted on edges. */
950 expand_phi_nodes (struct ssaexpand
*sa
)
953 elim_graph g
= new_elim_graph (sa
->map
->num_partitions
);
956 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
,
957 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
958 if (!gimple_seq_empty_p (phi_nodes (bb
)))
962 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
963 eliminate_phi (e
, g
);
964 set_phi_nodes (bb
, NULL
);
965 /* We can't redirect EH edges in RTL land, so we need to do this
966 here. Redirection happens only when splitting is necessary,
967 which it is only for critical edges, normally. For EH edges
968 it might also be necessary when the successor has more than
969 one predecessor. In that case the edge is either required to
970 be fallthru (which EH edges aren't), or the predecessor needs
971 to end with a jump (which again, isn't the case with EH edges).
972 Hence, split all EH edges on which we inserted instructions
973 and whose successor has multiple predecessors. */
974 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
976 if (e
->insns
.r
&& (e
->flags
& EDGE_EH
)
977 && !single_pred_p (e
->dest
))
979 rtx_insn
*insns
= e
->insns
.r
;
983 single_pred_edge (bb
)->insns
.r
= insns
;
990 delete_elim_graph (g
);
994 /* Remove the ssa-names in the current function and translate them into normal
995 compiler variables. PERFORM_TER is true if Temporary Expression Replacement
996 should also be used. */
999 remove_ssa_form (bool perform_ter
, struct ssaexpand
*sa
)
1001 bitmap values
= NULL
;
1005 map
= coalesce_ssa_name ();
1007 /* Return to viewing the variable list as just all reference variables after
1008 coalescing has been performed. */
1009 partition_view_normal (map
, false);
1011 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1013 fprintf (dump_file
, "After Coalescing:\n");
1014 dump_var_map (dump_file
, map
);
1019 values
= find_replaceable_exprs (map
);
1020 if (values
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
1021 dump_replaceable_exprs (dump_file
, values
);
1024 rewrite_trees (map
);
1027 sa
->values
= values
;
1028 sa
->partition_has_default_def
= BITMAP_ALLOC (NULL
);
1029 for (i
= 1; i
< num_ssa_names
; i
++)
1031 tree t
= ssa_name (i
);
1032 if (t
&& SSA_NAME_IS_DEFAULT_DEF (t
))
1034 int p
= var_to_partition (map
, t
);
1035 if (p
!= NO_PARTITION
)
1036 bitmap_set_bit (sa
->partition_has_default_def
, p
);
1042 /* If not already done so for basic block BB, assign increasing uids
1043 to each of its instructions. */
1046 maybe_renumber_stmts_bb (basic_block bb
)
1049 gimple_stmt_iterator gsi
;
1054 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1056 gimple stmt
= gsi_stmt (gsi
);
1057 gimple_set_uid (stmt
, i
);
1063 /* Return true if we can determine that the SSA_NAMEs RESULT (a result
1064 of a PHI node) and ARG (one of its arguments) conflict. Return false
1065 otherwise, also when we simply aren't sure. */
1068 trivially_conflicts_p (basic_block bb
, tree result
, tree arg
)
1071 imm_use_iterator imm_iter
;
1072 gimple defa
= SSA_NAME_DEF_STMT (arg
);
1074 /* If ARG isn't defined in the same block it's too complicated for
1076 if (gimple_bb (defa
) != bb
)
1079 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, result
)
1081 gimple use_stmt
= USE_STMT (use
);
1082 if (is_gimple_debug (use_stmt
))
1084 /* Now, if there's a use of RESULT that lies outside this basic block,
1085 then there surely is a conflict with ARG. */
1086 if (gimple_bb (use_stmt
) != bb
)
1088 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
1090 /* The use now is in a real stmt of BB, so if ARG was defined
1091 in a PHI node (like RESULT) both conflict. */
1092 if (gimple_code (defa
) == GIMPLE_PHI
)
1094 maybe_renumber_stmts_bb (bb
);
1095 /* If the use of RESULT occurs after the definition of ARG,
1096 the two conflict too. */
1097 if (gimple_uid (defa
) < gimple_uid (use_stmt
))
1105 /* Search every PHI node for arguments associated with backedges which
1106 we can trivially determine will need a copy (the argument is either
1107 not an SSA_NAME or the argument has a different underlying variable
1108 than the PHI result).
1110 Insert a copy from the PHI argument to a new destination at the
1111 end of the block with the backedge to the top of the loop. Update
1112 the PHI argument to reference this new destination. */
1115 insert_backedge_copies (void)
1120 mark_dfs_back_edges ();
1122 FOR_EACH_BB_FN (bb
, cfun
)
1124 /* Mark block as possibly needing calculation of UIDs. */
1127 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1129 gphi
*phi
= gsi
.phi ();
1130 tree result
= gimple_phi_result (phi
);
1133 if (virtual_operand_p (result
))
1136 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1138 tree arg
= gimple_phi_arg_def (phi
, i
);
1139 edge e
= gimple_phi_arg_edge (phi
, i
);
1141 /* If the argument is not an SSA_NAME, then we will need a
1142 constant initialization. If the argument is an SSA_NAME with
1143 a different underlying variable then a copy statement will be
1145 if ((e
->flags
& EDGE_DFS_BACK
)
1146 && (TREE_CODE (arg
) != SSA_NAME
1147 || SSA_NAME_VAR (arg
) != SSA_NAME_VAR (result
)
1148 || trivially_conflicts_p (bb
, result
, arg
)))
1153 gimple_stmt_iterator gsi2
;
1155 gsi2
= gsi_last_bb (gimple_phi_arg_edge (phi
, i
)->src
);
1156 if (!gsi_end_p (gsi2
))
1157 last
= gsi_stmt (gsi2
);
1159 /* In theory the only way we ought to get back to the
1160 start of a loop should be with a COND_EXPR or GOTO_EXPR.
1161 However, better safe than sorry.
1162 If the block ends with a control statement or
1163 something that might throw, then we have to
1164 insert this assignment before the last
1165 statement. Else insert it after the last statement. */
1166 if (last
&& stmt_ends_bb_p (last
))
1168 /* If the last statement in the block is the definition
1169 site of the PHI argument, then we can't insert
1170 anything after it. */
1171 if (TREE_CODE (arg
) == SSA_NAME
1172 && SSA_NAME_DEF_STMT (arg
) == last
)
1176 /* Create a new instance of the underlying variable of the
1178 name
= copy_ssa_name (result
);
1179 stmt
= gimple_build_assign (name
,
1180 gimple_phi_arg_def (phi
, i
));
1182 /* copy location if present. */
1183 if (gimple_phi_arg_has_location (phi
, i
))
1184 gimple_set_location (stmt
,
1185 gimple_phi_arg_location (phi
, i
));
1187 /* Insert the new statement into the block and update
1189 if (last
&& stmt_ends_bb_p (last
))
1190 gsi_insert_before (&gsi2
, stmt
, GSI_NEW_STMT
);
1192 gsi_insert_after (&gsi2
, stmt
, GSI_NEW_STMT
);
1193 SET_PHI_ARG_DEF (phi
, i
, name
);
1198 /* Unmark this block again. */
1203 /* Free all memory associated with going out of SSA form. SA is
1204 the outof-SSA info object. */
1207 finish_out_of_ssa (struct ssaexpand
*sa
)
1209 free (sa
->partition_to_pseudo
);
1211 BITMAP_FREE (sa
->values
);
1212 delete_var_map (sa
->map
);
1213 BITMAP_FREE (sa
->partition_has_default_def
);
1214 memset (sa
, 0, sizeof *sa
);
1217 /* Take the current function out of SSA form, translating PHIs as described in
1218 R. Morgan, ``Building an Optimizing Compiler'',
1219 Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */
1222 rewrite_out_of_ssa (struct ssaexpand
*sa
)
1224 /* If elimination of a PHI requires inserting a copy on a backedge,
1225 then we will have to split the backedge which has numerous
1226 undesirable performance effects.
1228 A significant number of such cases can be handled here by inserting
1229 copies into the loop itself. */
1230 insert_backedge_copies ();
1233 /* Eliminate PHIs which are of no use, such as virtual or dead phis. */
1234 eliminate_useless_phis ();
1236 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1237 gimple_dump_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);
1239 remove_ssa_form (flag_tree_ter
, sa
);
1241 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1242 gimple_dump_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);