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"
29 #include "fold-const.h"
30 #include "stor-layout.h"
32 #include "hard-reg-set.h"
34 #include "dominance.h"
38 #include "basic-block.h"
39 #include "gimple-pretty-print.h"
42 #include "tree-ssa-alias.h"
43 #include "internal-fn.h"
45 #include "gimple-expr.h"
48 #include "gimple-iterator.h"
49 #include "gimple-ssa.h"
51 #include "tree-phinodes.h"
52 #include "ssa-iterators.h"
53 #include "stringpool.h"
54 #include "tree-ssanames.h"
56 #include "diagnostic-core.h"
57 #include "tree-ssa-live.h"
58 #include "tree-ssa-ter.h"
59 #include "tree-ssa-coalesce.h"
60 #include "tree-outof-ssa.h"
62 /* FIXME: A lot of code here deals with expanding to RTL. All that code
63 should be in cfgexpand.c. */
66 #include "insn-config.h"
76 /* Return TRUE if expression STMT is suitable for replacement. */
79 ssa_is_replaceable_p (gimple stmt
)
85 /* Only consider modify stmts. */
86 if (!is_gimple_assign (stmt
))
89 /* If the statement may throw an exception, it cannot be replaced. */
90 if (stmt_could_throw_p (stmt
))
93 /* Punt if there is more than 1 def. */
94 def
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_DEF
);
98 /* Only consider definitions which have a single use. */
99 if (!single_imm_use (def
, &use_p
, &use_stmt
))
102 /* Used in this block, but at the TOP of the block, not the end. */
103 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
106 /* There must be no VDEFs. */
107 if (gimple_vdef (stmt
))
110 /* Float expressions must go through memory if float-store is on. */
112 && FLOAT_TYPE_P (gimple_expr_type (stmt
)))
115 /* An assignment with a register variable on the RHS is not
117 if (gimple_assign_rhs_code (stmt
) == VAR_DECL
118 && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt
)))
121 /* No function calls can be replaced. */
122 if (is_gimple_call (stmt
))
125 /* Leave any stmt with volatile operands alone as well. */
126 if (gimple_has_volatile_ops (stmt
))
133 /* Used to hold all the components required to do SSA PHI elimination.
134 The node and pred/succ list is a simple linear list of nodes and
135 edges represented as pairs of nodes.
137 The predecessor and successor list: Nodes are entered in pairs, where
138 [0] ->PRED, [1]->SUCC. All the even indexes in the array represent
139 predecessors, all the odd elements are successors.
142 When implemented as bitmaps, very large programs SSA->Normal times were
143 being dominated by clearing the interference graph.
145 Typically this list of edges is extremely small since it only includes
146 PHI results and uses from a single edge which have not coalesced with
147 each other. This means that no virtual PHI nodes are included, and
148 empirical evidence suggests that the number of edges rarely exceed
149 3, and in a bootstrap of GCC, the maximum size encountered was 7.
150 This also limits the number of possible nodes that are involved to
151 rarely more than 6, and in the bootstrap of gcc, the maximum number
152 of nodes encountered was 12. */
154 typedef struct _elim_graph
{
155 /* Size of the elimination vectors. */
158 /* List of nodes in the elimination graph. */
161 /* The predecessor and successor edge list. */
164 /* Source locus on each edge */
165 vec
<source_location
> edge_locus
;
167 /* Visited vector. */
170 /* Stack for visited nodes. */
173 /* The variable partition map. */
176 /* Edge being eliminated by this graph. */
179 /* List of constant copies to emit. These are pushed on in pairs. */
180 vec
<int> const_dests
;
181 vec
<tree
> const_copies
;
183 /* Source locations for any constant copies. */
184 vec
<source_location
> copy_locus
;
188 /* For an edge E find out a good source location to associate with
189 instructions inserted on edge E. If E has an implicit goto set,
190 use its location. Otherwise search instructions in predecessors
191 of E for a location, and use that one. That makes sense because
192 we insert on edges for PHI nodes, and effects of PHIs happen on
193 the end of the predecessor conceptually. */
196 set_location_for_edge (edge e
)
200 set_curr_insn_location (e
->goto_locus
);
204 basic_block bb
= e
->src
;
205 gimple_stmt_iterator gsi
;
209 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
211 gimple stmt
= gsi_stmt (gsi
);
212 if (is_gimple_debug (stmt
))
214 if (gimple_has_location (stmt
) || gimple_block (stmt
))
216 set_curr_insn_location (gimple_location (stmt
));
220 /* Nothing found in this basic block. Make a half-assed attempt
221 to continue with another block. */
222 if (single_pred_p (bb
))
223 bb
= single_pred (bb
);
227 while (bb
!= e
->src
);
231 /* Emit insns to copy SRC into DEST converting SRC if necessary. As
232 SRC/DEST might be BLKmode memory locations SIZEEXP is a tree from
233 which we deduce the size to copy in that case. */
235 static inline rtx_insn
*
236 emit_partition_copy (rtx dest
, rtx src
, int unsignedsrcp
, tree sizeexp
)
240 if (GET_MODE (src
) != VOIDmode
&& GET_MODE (src
) != GET_MODE (dest
))
241 src
= convert_to_mode (GET_MODE (dest
), src
, unsignedsrcp
);
242 if (GET_MODE (src
) == BLKmode
)
244 gcc_assert (GET_MODE (dest
) == BLKmode
);
245 emit_block_move (dest
, src
, expr_size (sizeexp
), BLOCK_OP_NORMAL
);
248 emit_move_insn (dest
, src
);
250 rtx_insn
*seq
= get_insns ();
256 /* Insert a copy instruction from partition SRC to DEST onto edge E. */
259 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 rtx_insn
*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
)
355 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
358 "Inserting a temp copy on edge BB%d->BB%d : PART.%d = ",
360 e
->dest
->index
, dest
);
361 print_simple_rtl (dump_file
, src
);
362 fprintf (dump_file
, "\n");
365 gcc_assert (SA
.partition_to_pseudo
[dest
]);
367 set_location_for_edge (e
);
368 /* If a locus is provided, override the default. */
370 set_curr_insn_location (locus
);
372 /* We give the destination as sizeexp in case src/dest are BLKmode
373 mems. Usually we give the source. As we result from SSA names
374 the left and right size should be the same (and no WITH_SIZE_EXPR
375 involved), so it doesn't matter. */
376 rtx_insn
*seq
= emit_partition_copy (copy_rtx (SA
.partition_to_pseudo
[dest
]),
378 partition_to_var (SA
.map
, dest
));
380 insert_insn_on_edge (seq
, e
);
383 /* Insert a copy instruction from partition SRC to RTL lvalue DEST
387 insert_part_to_rtx_on_edge (edge e
, rtx dest
, int src
, source_location locus
)
390 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
393 "Inserting a temp copy on edge BB%d->BB%d : ",
396 print_simple_rtl (dump_file
, dest
);
397 fprintf (dump_file
, "= PART.%d\n", src
);
400 gcc_assert (SA
.partition_to_pseudo
[src
]);
402 set_location_for_edge (e
);
403 /* If a locus is provided, override the default. */
405 set_curr_insn_location (locus
);
407 var
= partition_to_var (SA
.map
, src
);
408 rtx_insn
*seq
= emit_partition_copy (dest
,
409 copy_rtx (SA
.partition_to_pseudo
[src
]),
410 TYPE_UNSIGNED (TREE_TYPE (var
)),
413 insert_insn_on_edge (seq
, e
);
417 /* Create an elimination graph with SIZE nodes and associated data
421 new_elim_graph (int size
)
423 elim_graph g
= (elim_graph
) xmalloc (sizeof (struct _elim_graph
));
425 g
->nodes
.create (30);
426 g
->const_dests
.create (20);
427 g
->const_copies
.create (20);
428 g
->copy_locus
.create (10);
429 g
->edge_list
.create (20);
430 g
->edge_locus
.create (10);
431 g
->stack
.create (30);
433 g
->visited
= sbitmap_alloc (size
);
439 /* Empty elimination graph G. */
442 clear_elim_graph (elim_graph g
)
444 g
->nodes
.truncate (0);
445 g
->edge_list
.truncate (0);
446 g
->edge_locus
.truncate (0);
450 /* Delete elimination graph G. */
453 delete_elim_graph (elim_graph g
)
455 sbitmap_free (g
->visited
);
457 g
->edge_list
.release ();
458 g
->const_copies
.release ();
459 g
->const_dests
.release ();
461 g
->copy_locus
.release ();
462 g
->edge_locus
.release ();
468 /* Return the number of nodes in graph G. */
471 elim_graph_size (elim_graph g
)
473 return g
->nodes
.length ();
477 /* Add NODE to graph G, if it doesn't exist already. */
480 elim_graph_add_node (elim_graph g
, int node
)
485 FOR_EACH_VEC_ELT (g
->nodes
, x
, t
)
488 g
->nodes
.safe_push (node
);
492 /* Add the edge PRED->SUCC to graph G. */
495 elim_graph_add_edge (elim_graph g
, int pred
, int succ
, source_location locus
)
497 g
->edge_list
.safe_push (pred
);
498 g
->edge_list
.safe_push (succ
);
499 g
->edge_locus
.safe_push (locus
);
503 /* Remove an edge from graph G for which NODE is the predecessor, and
504 return the successor node. -1 is returned if there is no such edge. */
507 elim_graph_remove_succ_edge (elim_graph g
, int node
, source_location
*locus
)
511 for (x
= 0; x
< g
->edge_list
.length (); x
+= 2)
512 if (g
->edge_list
[x
] == node
)
514 g
->edge_list
[x
] = -1;
515 y
= g
->edge_list
[x
+ 1];
516 g
->edge_list
[x
+ 1] = -1;
517 *locus
= g
->edge_locus
[x
/ 2];
518 g
->edge_locus
[x
/ 2] = UNKNOWN_LOCATION
;
521 *locus
= UNKNOWN_LOCATION
;
526 /* Find all the nodes in GRAPH which are successors to NODE in the
527 edge list. VAR will hold the partition number found. CODE is the
528 code fragment executed for every node found. */
530 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, LOCUS, CODE) \
534 for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \
536 y_ = (GRAPH)->edge_list[x_]; \
539 (void) ((VAR) = (GRAPH)->edge_list[x_ + 1]); \
540 (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \
546 /* Find all the nodes which are predecessors of NODE in the edge list for
547 GRAPH. VAR will hold the partition number found. CODE is the
548 code fragment executed for every node found. */
550 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, LOCUS, CODE) \
554 for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \
556 y_ = (GRAPH)->edge_list[x_ + 1]; \
559 (void) ((VAR) = (GRAPH)->edge_list[x_]); \
560 (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \
566 /* Add T to elimination graph G. */
569 eliminate_name (elim_graph g
, int T
)
571 elim_graph_add_node (g
, T
);
574 /* Return true if this phi argument T should have a copy queued when using
575 var_map MAP. PHI nodes should contain only ssa_names and invariants. A
576 test for ssa_name is definitely simpler, but don't let invalid contents
577 slip through in the meantime. */
580 queue_phi_copy_p (var_map map
, tree t
)
582 if (TREE_CODE (t
) == SSA_NAME
)
584 if (var_to_partition (map
, t
) == NO_PARTITION
)
588 gcc_checking_assert (is_gimple_min_invariant (t
));
592 /* Build elimination graph G for basic block BB on incoming PHI edge
596 eliminate_build (elim_graph g
)
602 clear_elim_graph (g
);
604 for (gsi
= gsi_start_phis (g
->e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
606 gphi
*phi
= gsi
.phi ();
607 source_location locus
;
609 p0
= var_to_partition (g
->map
, gimple_phi_result (phi
));
610 /* Ignore results which are not in partitions. */
611 if (p0
== NO_PARTITION
)
614 Ti
= PHI_ARG_DEF (phi
, g
->e
->dest_idx
);
615 locus
= gimple_phi_arg_location_from_edge (phi
, g
->e
);
617 /* If this argument is a constant, or a SSA_NAME which is being
618 left in SSA form, just queue a copy to be emitted on this
620 if (queue_phi_copy_p (g
->map
, Ti
))
622 /* Save constant copies until all other copies have been emitted
624 g
->const_dests
.safe_push (p0
);
625 g
->const_copies
.safe_push (Ti
);
626 g
->copy_locus
.safe_push (locus
);
630 pi
= var_to_partition (g
->map
, Ti
);
633 eliminate_name (g
, p0
);
634 eliminate_name (g
, pi
);
635 elim_graph_add_edge (g
, p0
, pi
, locus
);
642 /* Push successors of T onto the elimination stack for G. */
645 elim_forward (elim_graph g
, int T
)
648 source_location locus
;
650 bitmap_set_bit (g
->visited
, T
);
651 FOR_EACH_ELIM_GRAPH_SUCC (g
, T
, S
, locus
,
653 if (!bitmap_bit_p (g
->visited
, S
))
656 g
->stack
.safe_push (T
);
660 /* Return 1 if there unvisited predecessors of T in graph G. */
663 elim_unvisited_predecessor (elim_graph g
, int T
)
666 source_location locus
;
668 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
670 if (!bitmap_bit_p (g
->visited
, P
))
676 /* Process predecessors first, and insert a copy. */
679 elim_backward (elim_graph g
, int T
)
682 source_location locus
;
684 bitmap_set_bit (g
->visited
, T
);
685 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
687 if (!bitmap_bit_p (g
->visited
, P
))
689 elim_backward (g
, P
);
690 insert_partition_copy_on_edge (g
->e
, P
, T
, locus
);
695 /* Allocate a new pseudo register usable for storing values sitting
696 in NAME (a decl or SSA name), i.e. with matching mode and attributes. */
699 get_temp_reg (tree name
)
701 tree var
= TREE_CODE (name
) == SSA_NAME
? SSA_NAME_VAR (name
) : name
;
702 tree type
= TREE_TYPE (var
);
704 machine_mode reg_mode
= promote_decl_mode (var
, &unsignedp
);
705 rtx x
= gen_reg_rtx (reg_mode
);
706 if (POINTER_TYPE_P (type
))
707 mark_reg_pointer (x
, TYPE_ALIGN (TREE_TYPE (TREE_TYPE (var
))));
711 /* Insert required copies for T in graph G. Check for a strongly connected
712 region, and create a temporary to break the cycle if one is found. */
715 elim_create (elim_graph g
, int T
)
718 source_location locus
;
720 if (elim_unvisited_predecessor (g
, T
))
722 tree var
= partition_to_var (g
->map
, T
);
723 rtx U
= get_temp_reg (var
);
724 int unsignedsrcp
= TYPE_UNSIGNED (TREE_TYPE (var
));
726 insert_part_to_rtx_on_edge (g
->e
, U
, T
, UNKNOWN_LOCATION
);
727 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
729 if (!bitmap_bit_p (g
->visited
, P
))
731 elim_backward (g
, P
);
732 insert_rtx_to_part_on_edge (g
->e
, P
, U
, unsignedsrcp
, locus
);
738 S
= elim_graph_remove_succ_edge (g
, T
, &locus
);
741 bitmap_set_bit (g
->visited
, T
);
742 insert_partition_copy_on_edge (g
->e
, T
, S
, locus
);
748 /* Eliminate all the phi nodes on edge E in graph G. */
751 eliminate_phi (edge e
, elim_graph g
)
755 gcc_assert (g
->const_copies
.length () == 0);
756 gcc_assert (g
->copy_locus
.length () == 0);
758 /* Abnormal edges already have everything coalesced. */
759 if (e
->flags
& EDGE_ABNORMAL
)
766 if (elim_graph_size (g
) != 0)
770 bitmap_clear (g
->visited
);
771 g
->stack
.truncate (0);
773 FOR_EACH_VEC_ELT (g
->nodes
, x
, part
)
775 if (!bitmap_bit_p (g
->visited
, part
))
776 elim_forward (g
, part
);
779 bitmap_clear (g
->visited
);
780 while (g
->stack
.length () > 0)
783 if (!bitmap_bit_p (g
->visited
, x
))
788 /* If there are any pending constant copies, issue them now. */
789 while (g
->const_copies
.length () > 0)
793 source_location locus
;
795 src
= g
->const_copies
.pop ();
796 dest
= g
->const_dests
.pop ();
797 locus
= g
->copy_locus
.pop ();
798 insert_value_copy_on_edge (e
, dest
, src
, locus
);
803 /* Remove each argument from PHI. If an arg was the last use of an SSA_NAME,
804 check to see if this allows another PHI node to be removed. */
807 remove_gimple_phi_args (gphi
*phi
)
812 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
814 fprintf (dump_file
, "Removing Dead PHI definition: ");
815 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
818 FOR_EACH_PHI_ARG (arg_p
, phi
, iter
, SSA_OP_USE
)
820 tree arg
= USE_FROM_PTR (arg_p
);
821 if (TREE_CODE (arg
) == SSA_NAME
)
823 /* Remove the reference to the existing argument. */
824 SET_USE (arg_p
, NULL_TREE
);
825 if (has_zero_uses (arg
))
828 gimple_stmt_iterator gsi
;
830 stmt
= SSA_NAME_DEF_STMT (arg
);
832 /* Also remove the def if it is a PHI node. */
833 if (gimple_code (stmt
) == GIMPLE_PHI
)
835 remove_gimple_phi_args (as_a
<gphi
*> (stmt
));
836 gsi
= gsi_for_stmt (stmt
);
837 remove_phi_node (&gsi
, true);
845 /* Remove any PHI node which is a virtual PHI, or a PHI with no uses. */
848 eliminate_useless_phis (void)
854 FOR_EACH_BB_FN (bb
, cfun
)
856 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); )
858 gphi
*phi
= gsi
.phi ();
859 result
= gimple_phi_result (phi
);
860 if (virtual_operand_p (result
))
862 #ifdef ENABLE_CHECKING
864 /* There should be no arguments which are not virtual, or the
865 results will be incorrect. */
866 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
868 tree arg
= PHI_ARG_DEF (phi
, i
);
869 if (TREE_CODE (arg
) == SSA_NAME
870 && !virtual_operand_p (arg
))
872 fprintf (stderr
, "Argument of PHI is not virtual (");
873 print_generic_expr (stderr
, arg
, TDF_SLIM
);
874 fprintf (stderr
, "), but the result is :");
875 print_gimple_stmt (stderr
, phi
, 0, TDF_SLIM
);
876 internal_error ("SSA corruption");
880 remove_phi_node (&gsi
, true);
884 /* Also remove real PHIs with no uses. */
885 if (has_zero_uses (result
))
887 remove_gimple_phi_args (phi
);
888 remove_phi_node (&gsi
, true);
898 /* This function will rewrite the current program using the variable mapping
899 found in MAP. If the replacement vector VALUES is provided, any
900 occurrences of partitions with non-null entries in the vector will be
901 replaced with the expression in the vector instead of its mapped
905 rewrite_trees (var_map map ATTRIBUTE_UNUSED
)
907 #ifdef ENABLE_CHECKING
909 /* Search for PHIs where the destination has no partition, but one
910 or more arguments has a partition. This should not happen and can
911 create incorrect code. */
912 FOR_EACH_BB_FN (bb
, cfun
)
915 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
917 gphi
*phi
= gsi
.phi ();
918 tree T0
= var_to_partition_to_var (map
, gimple_phi_result (phi
));
922 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
924 tree arg
= PHI_ARG_DEF (phi
, i
);
926 if (TREE_CODE (arg
) == SSA_NAME
927 && var_to_partition (map
, arg
) != NO_PARTITION
)
929 fprintf (stderr
, "Argument of PHI is in a partition :(");
930 print_generic_expr (stderr
, arg
, TDF_SLIM
);
931 fprintf (stderr
, "), but the result is not :");
932 print_gimple_stmt (stderr
, phi
, 0, TDF_SLIM
);
933 internal_error ("SSA corruption");
942 /* Given the out-of-ssa info object SA (with prepared partitions)
943 eliminate all phi nodes in all basic blocks. Afterwards no
944 basic block will have phi nodes anymore and there are possibly
945 some RTL instructions inserted on edges. */
948 expand_phi_nodes (struct ssaexpand
*sa
)
951 elim_graph g
= new_elim_graph (sa
->map
->num_partitions
);
954 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
,
955 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
956 if (!gimple_seq_empty_p (phi_nodes (bb
)))
960 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
961 eliminate_phi (e
, g
);
962 set_phi_nodes (bb
, NULL
);
963 /* We can't redirect EH edges in RTL land, so we need to do this
964 here. Redirection happens only when splitting is necessary,
965 which it is only for critical edges, normally. For EH edges
966 it might also be necessary when the successor has more than
967 one predecessor. In that case the edge is either required to
968 be fallthru (which EH edges aren't), or the predecessor needs
969 to end with a jump (which again, isn't the case with EH edges).
970 Hence, split all EH edges on which we inserted instructions
971 and whose successor has multiple predecessors. */
972 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
974 if (e
->insns
.r
&& (e
->flags
& EDGE_EH
)
975 && !single_pred_p (e
->dest
))
977 rtx_insn
*insns
= e
->insns
.r
;
981 single_pred_edge (bb
)->insns
.r
= insns
;
988 delete_elim_graph (g
);
992 /* Remove the ssa-names in the current function and translate them into normal
993 compiler variables. PERFORM_TER is true if Temporary Expression Replacement
994 should also be used. */
997 remove_ssa_form (bool perform_ter
, struct ssaexpand
*sa
)
999 bitmap values
= NULL
;
1003 map
= coalesce_ssa_name ();
1005 /* Return to viewing the variable list as just all reference variables after
1006 coalescing has been performed. */
1007 partition_view_normal (map
, false);
1009 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1011 fprintf (dump_file
, "After Coalescing:\n");
1012 dump_var_map (dump_file
, map
);
1017 values
= find_replaceable_exprs (map
);
1018 if (values
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
1019 dump_replaceable_exprs (dump_file
, values
);
1022 rewrite_trees (map
);
1025 sa
->values
= values
;
1026 sa
->partition_has_default_def
= BITMAP_ALLOC (NULL
);
1027 for (i
= 1; i
< num_ssa_names
; i
++)
1029 tree t
= ssa_name (i
);
1030 if (t
&& SSA_NAME_IS_DEFAULT_DEF (t
))
1032 int p
= var_to_partition (map
, t
);
1033 if (p
!= NO_PARTITION
)
1034 bitmap_set_bit (sa
->partition_has_default_def
, p
);
1040 /* If not already done so for basic block BB, assign increasing uids
1041 to each of its instructions. */
1044 maybe_renumber_stmts_bb (basic_block bb
)
1047 gimple_stmt_iterator gsi
;
1052 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1054 gimple stmt
= gsi_stmt (gsi
);
1055 gimple_set_uid (stmt
, i
);
1061 /* Return true if we can determine that the SSA_NAMEs RESULT (a result
1062 of a PHI node) and ARG (one of its arguments) conflict. Return false
1063 otherwise, also when we simply aren't sure. */
1066 trivially_conflicts_p (basic_block bb
, tree result
, tree arg
)
1069 imm_use_iterator imm_iter
;
1070 gimple defa
= SSA_NAME_DEF_STMT (arg
);
1072 /* If ARG isn't defined in the same block it's too complicated for
1074 if (gimple_bb (defa
) != bb
)
1077 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, result
)
1079 gimple use_stmt
= USE_STMT (use
);
1080 if (is_gimple_debug (use_stmt
))
1082 /* Now, if there's a use of RESULT that lies outside this basic block,
1083 then there surely is a conflict with ARG. */
1084 if (gimple_bb (use_stmt
) != bb
)
1086 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
1088 /* The use now is in a real stmt of BB, so if ARG was defined
1089 in a PHI node (like RESULT) both conflict. */
1090 if (gimple_code (defa
) == GIMPLE_PHI
)
1092 maybe_renumber_stmts_bb (bb
);
1093 /* If the use of RESULT occurs after the definition of ARG,
1094 the two conflict too. */
1095 if (gimple_uid (defa
) < gimple_uid (use_stmt
))
1103 /* Search every PHI node for arguments associated with backedges which
1104 we can trivially determine will need a copy (the argument is either
1105 not an SSA_NAME or the argument has a different underlying variable
1106 than the PHI result).
1108 Insert a copy from the PHI argument to a new destination at the
1109 end of the block with the backedge to the top of the loop. Update
1110 the PHI argument to reference this new destination. */
1113 insert_backedge_copies (void)
1118 mark_dfs_back_edges ();
1120 FOR_EACH_BB_FN (bb
, cfun
)
1122 /* Mark block as possibly needing calculation of UIDs. */
1125 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1127 gphi
*phi
= gsi
.phi ();
1128 tree result
= gimple_phi_result (phi
);
1131 if (virtual_operand_p (result
))
1134 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1136 tree arg
= gimple_phi_arg_def (phi
, i
);
1137 edge e
= gimple_phi_arg_edge (phi
, i
);
1139 /* If the argument is not an SSA_NAME, then we will need a
1140 constant initialization. If the argument is an SSA_NAME with
1141 a different underlying variable then a copy statement will be
1143 if ((e
->flags
& EDGE_DFS_BACK
)
1144 && (TREE_CODE (arg
) != SSA_NAME
1145 || SSA_NAME_VAR (arg
) != SSA_NAME_VAR (result
)
1146 || trivially_conflicts_p (bb
, result
, arg
)))
1151 gimple_stmt_iterator gsi2
;
1153 gsi2
= gsi_last_bb (gimple_phi_arg_edge (phi
, i
)->src
);
1154 if (!gsi_end_p (gsi2
))
1155 last
= gsi_stmt (gsi2
);
1157 /* In theory the only way we ought to get back to the
1158 start of a loop should be with a COND_EXPR or GOTO_EXPR.
1159 However, better safe than sorry.
1160 If the block ends with a control statement or
1161 something that might throw, then we have to
1162 insert this assignment before the last
1163 statement. Else insert it after the last statement. */
1164 if (last
&& stmt_ends_bb_p (last
))
1166 /* If the last statement in the block is the definition
1167 site of the PHI argument, then we can't insert
1168 anything after it. */
1169 if (TREE_CODE (arg
) == SSA_NAME
1170 && SSA_NAME_DEF_STMT (arg
) == last
)
1174 /* Create a new instance of the underlying variable of the
1176 name
= copy_ssa_name (result
);
1177 stmt
= gimple_build_assign (name
,
1178 gimple_phi_arg_def (phi
, i
));
1180 /* copy location if present. */
1181 if (gimple_phi_arg_has_location (phi
, i
))
1182 gimple_set_location (stmt
,
1183 gimple_phi_arg_location (phi
, i
));
1185 /* Insert the new statement into the block and update
1187 if (last
&& stmt_ends_bb_p (last
))
1188 gsi_insert_before (&gsi2
, stmt
, GSI_NEW_STMT
);
1190 gsi_insert_after (&gsi2
, stmt
, GSI_NEW_STMT
);
1191 SET_PHI_ARG_DEF (phi
, i
, name
);
1196 /* Unmark this block again. */
1201 /* Free all memory associated with going out of SSA form. SA is
1202 the outof-SSA info object. */
1205 finish_out_of_ssa (struct ssaexpand
*sa
)
1207 free (sa
->partition_to_pseudo
);
1209 BITMAP_FREE (sa
->values
);
1210 delete_var_map (sa
->map
);
1211 BITMAP_FREE (sa
->partition_has_default_def
);
1212 memset (sa
, 0, sizeof *sa
);
1215 /* Take the current function out of SSA form, translating PHIs as described in
1216 R. Morgan, ``Building an Optimizing Compiler'',
1217 Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */
1220 rewrite_out_of_ssa (struct ssaexpand
*sa
)
1222 /* If elimination of a PHI requires inserting a copy on a backedge,
1223 then we will have to split the backedge which has numerous
1224 undesirable performance effects.
1226 A significant number of such cases can be handled here by inserting
1227 copies into the loop itself. */
1228 insert_backedge_copies ();
1231 /* Eliminate PHIs which are of no use, such as virtual or dead phis. */
1232 eliminate_useless_phis ();
1234 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1235 gimple_dump_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);
1237 remove_ssa_form (flag_tree_ter
, sa
);
1239 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1240 gimple_dump_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);