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"
30 #include "fold-const.h"
31 #include "stor-layout.h"
34 #include "gimple-pretty-print.h"
35 #include "internal-fn.h"
37 #include "gimple-iterator.h"
40 #include "diagnostic-core.h"
41 #include "tree-ssa-live.h"
42 #include "tree-ssa-ter.h"
43 #include "tree-ssa-coalesce.h"
44 #include "tree-outof-ssa.h"
46 /* FIXME: A lot of code here deals with expanding to RTL. All that code
47 should be in cfgexpand.c. */
49 #include "insn-config.h"
59 /* Return TRUE if expression STMT is suitable for replacement. */
62 ssa_is_replaceable_p (gimple stmt
)
68 /* Only consider modify stmts. */
69 if (!is_gimple_assign (stmt
))
72 /* If the statement may throw an exception, it cannot be replaced. */
73 if (stmt_could_throw_p (stmt
))
76 /* Punt if there is more than 1 def. */
77 def
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_DEF
);
81 /* Only consider definitions which have a single use. */
82 if (!single_imm_use (def
, &use_p
, &use_stmt
))
85 /* Used in this block, but at the TOP of the block, not the end. */
86 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
89 /* There must be no VDEFs. */
90 if (gimple_vdef (stmt
))
93 /* Float expressions must go through memory if float-store is on. */
95 && FLOAT_TYPE_P (gimple_expr_type (stmt
)))
98 /* An assignment with a register variable on the RHS is not
100 if (gimple_assign_rhs_code (stmt
) == VAR_DECL
101 && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt
)))
104 /* No function calls can be replaced. */
105 if (is_gimple_call (stmt
))
108 /* Leave any stmt with volatile operands alone as well. */
109 if (gimple_has_volatile_ops (stmt
))
116 /* Used to hold all the components required to do SSA PHI elimination.
117 The node and pred/succ list is a simple linear list of nodes and
118 edges represented as pairs of nodes.
120 The predecessor and successor list: Nodes are entered in pairs, where
121 [0] ->PRED, [1]->SUCC. All the even indexes in the array represent
122 predecessors, all the odd elements are successors.
125 When implemented as bitmaps, very large programs SSA->Normal times were
126 being dominated by clearing the interference graph.
128 Typically this list of edges is extremely small since it only includes
129 PHI results and uses from a single edge which have not coalesced with
130 each other. This means that no virtual PHI nodes are included, and
131 empirical evidence suggests that the number of edges rarely exceed
132 3, and in a bootstrap of GCC, the maximum size encountered was 7.
133 This also limits the number of possible nodes that are involved to
134 rarely more than 6, and in the bootstrap of gcc, the maximum number
135 of nodes encountered was 12. */
137 typedef struct _elim_graph
{
138 /* Size of the elimination vectors. */
141 /* List of nodes in the elimination graph. */
144 /* The predecessor and successor edge list. */
147 /* Source locus on each edge */
148 vec
<source_location
> edge_locus
;
150 /* Visited vector. */
153 /* Stack for visited nodes. */
156 /* The variable partition map. */
159 /* Edge being eliminated by this graph. */
162 /* List of constant copies to emit. These are pushed on in pairs. */
163 vec
<int> const_dests
;
164 vec
<tree
> const_copies
;
166 /* Source locations for any constant copies. */
167 vec
<source_location
> copy_locus
;
171 /* For an edge E find out a good source location to associate with
172 instructions inserted on edge E. If E has an implicit goto set,
173 use its location. Otherwise search instructions in predecessors
174 of E for a location, and use that one. That makes sense because
175 we insert on edges for PHI nodes, and effects of PHIs happen on
176 the end of the predecessor conceptually. */
179 set_location_for_edge (edge e
)
183 set_curr_insn_location (e
->goto_locus
);
187 basic_block bb
= e
->src
;
188 gimple_stmt_iterator gsi
;
192 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
194 gimple stmt
= gsi_stmt (gsi
);
195 if (is_gimple_debug (stmt
))
197 if (gimple_has_location (stmt
) || gimple_block (stmt
))
199 set_curr_insn_location (gimple_location (stmt
));
203 /* Nothing found in this basic block. Make a half-assed attempt
204 to continue with another block. */
205 if (single_pred_p (bb
))
206 bb
= single_pred (bb
);
210 while (bb
!= e
->src
);
214 /* Emit insns to copy SRC into DEST converting SRC if necessary. As
215 SRC/DEST might be BLKmode memory locations SIZEEXP is a tree from
216 which we deduce the size to copy in that case. */
218 static inline rtx_insn
*
219 emit_partition_copy (rtx dest
, rtx src
, int unsignedsrcp
, tree sizeexp
)
223 if (GET_MODE (src
) != VOIDmode
&& GET_MODE (src
) != GET_MODE (dest
))
224 src
= convert_to_mode (GET_MODE (dest
), src
, unsignedsrcp
);
225 if (GET_MODE (src
) == BLKmode
)
227 gcc_assert (GET_MODE (dest
) == BLKmode
);
228 emit_block_move (dest
, src
, expr_size (sizeexp
), BLOCK_OP_NORMAL
);
231 emit_move_insn (dest
, src
);
233 rtx_insn
*seq
= get_insns ();
239 /* Insert a copy instruction from partition SRC to DEST onto edge E. */
242 insert_partition_copy_on_edge (edge e
, int dest
, int src
, source_location locus
)
245 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
248 "Inserting a partition copy on edge BB%d->BB%d :"
251 e
->dest
->index
, dest
, src
);
252 fprintf (dump_file
, "\n");
255 gcc_assert (SA
.partition_to_pseudo
[dest
]);
256 gcc_assert (SA
.partition_to_pseudo
[src
]);
258 set_location_for_edge (e
);
259 /* If a locus is provided, override the default. */
261 set_curr_insn_location (locus
);
263 var
= partition_to_var (SA
.map
, src
);
264 rtx_insn
*seq
= emit_partition_copy (copy_rtx (SA
.partition_to_pseudo
[dest
]),
265 copy_rtx (SA
.partition_to_pseudo
[src
]),
266 TYPE_UNSIGNED (TREE_TYPE (var
)),
269 insert_insn_on_edge (seq
, e
);
272 /* Insert a copy instruction from expression SRC to partition DEST
276 insert_value_copy_on_edge (edge e
, int dest
, tree src
, source_location locus
)
278 rtx dest_rtx
, seq
, x
;
279 machine_mode dest_mode
, src_mode
;
283 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
286 "Inserting a value copy on edge BB%d->BB%d : PART.%d = ",
288 e
->dest
->index
, dest
);
289 print_generic_expr (dump_file
, src
, TDF_SLIM
);
290 fprintf (dump_file
, "\n");
293 dest_rtx
= copy_rtx (SA
.partition_to_pseudo
[dest
]);
294 gcc_assert (dest_rtx
);
296 set_location_for_edge (e
);
297 /* If a locus is provided, override the default. */
299 set_curr_insn_location (locus
);
303 var
= SSA_NAME_VAR (partition_to_var (SA
.map
, dest
));
304 src_mode
= TYPE_MODE (TREE_TYPE (src
));
305 dest_mode
= GET_MODE (dest_rtx
);
306 gcc_assert (src_mode
== TYPE_MODE (TREE_TYPE (var
)));
307 gcc_assert (!REG_P (dest_rtx
)
308 || dest_mode
== promote_decl_mode (var
, &unsignedp
));
310 if (src_mode
!= dest_mode
)
312 x
= expand_expr (src
, NULL
, src_mode
, EXPAND_NORMAL
);
313 x
= convert_modes (dest_mode
, src_mode
, x
, unsignedp
);
315 else if (src_mode
== BLKmode
)
318 store_expr (src
, x
, 0, false);
321 x
= expand_expr (src
, dest_rtx
, dest_mode
, EXPAND_NORMAL
);
324 emit_move_insn (dest_rtx
, x
);
328 insert_insn_on_edge (seq
, e
);
331 /* Insert a copy instruction from RTL expression SRC to partition DEST
335 insert_rtx_to_part_on_edge (edge e
, int dest
, rtx src
, int unsignedsrcp
,
336 source_location locus
)
338 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
341 "Inserting a temp copy on edge BB%d->BB%d : PART.%d = ",
343 e
->dest
->index
, dest
);
344 print_simple_rtl (dump_file
, src
);
345 fprintf (dump_file
, "\n");
348 gcc_assert (SA
.partition_to_pseudo
[dest
]);
350 set_location_for_edge (e
);
351 /* If a locus is provided, override the default. */
353 set_curr_insn_location (locus
);
355 /* We give the destination as sizeexp in case src/dest are BLKmode
356 mems. Usually we give the source. As we result from SSA names
357 the left and right size should be the same (and no WITH_SIZE_EXPR
358 involved), so it doesn't matter. */
359 rtx_insn
*seq
= emit_partition_copy (copy_rtx (SA
.partition_to_pseudo
[dest
]),
361 partition_to_var (SA
.map
, dest
));
363 insert_insn_on_edge (seq
, e
);
366 /* Insert a copy instruction from partition SRC to RTL lvalue DEST
370 insert_part_to_rtx_on_edge (edge e
, rtx dest
, int src
, source_location locus
)
373 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
376 "Inserting a temp copy on edge BB%d->BB%d : ",
379 print_simple_rtl (dump_file
, dest
);
380 fprintf (dump_file
, "= PART.%d\n", src
);
383 gcc_assert (SA
.partition_to_pseudo
[src
]);
385 set_location_for_edge (e
);
386 /* If a locus is provided, override the default. */
388 set_curr_insn_location (locus
);
390 var
= partition_to_var (SA
.map
, src
);
391 rtx_insn
*seq
= emit_partition_copy (dest
,
392 copy_rtx (SA
.partition_to_pseudo
[src
]),
393 TYPE_UNSIGNED (TREE_TYPE (var
)),
396 insert_insn_on_edge (seq
, e
);
400 /* Create an elimination graph with SIZE nodes and associated data
404 new_elim_graph (int size
)
406 elim_graph g
= (elim_graph
) xmalloc (sizeof (struct _elim_graph
));
408 g
->nodes
.create (30);
409 g
->const_dests
.create (20);
410 g
->const_copies
.create (20);
411 g
->copy_locus
.create (10);
412 g
->edge_list
.create (20);
413 g
->edge_locus
.create (10);
414 g
->stack
.create (30);
416 g
->visited
= sbitmap_alloc (size
);
422 /* Empty elimination graph G. */
425 clear_elim_graph (elim_graph g
)
427 g
->nodes
.truncate (0);
428 g
->edge_list
.truncate (0);
429 g
->edge_locus
.truncate (0);
433 /* Delete elimination graph G. */
436 delete_elim_graph (elim_graph g
)
438 sbitmap_free (g
->visited
);
440 g
->edge_list
.release ();
441 g
->const_copies
.release ();
442 g
->const_dests
.release ();
444 g
->copy_locus
.release ();
445 g
->edge_locus
.release ();
451 /* Return the number of nodes in graph G. */
454 elim_graph_size (elim_graph g
)
456 return g
->nodes
.length ();
460 /* Add NODE to graph G, if it doesn't exist already. */
463 elim_graph_add_node (elim_graph g
, int node
)
468 FOR_EACH_VEC_ELT (g
->nodes
, x
, t
)
471 g
->nodes
.safe_push (node
);
475 /* Add the edge PRED->SUCC to graph G. */
478 elim_graph_add_edge (elim_graph g
, int pred
, int succ
, source_location locus
)
480 g
->edge_list
.safe_push (pred
);
481 g
->edge_list
.safe_push (succ
);
482 g
->edge_locus
.safe_push (locus
);
486 /* Remove an edge from graph G for which NODE is the predecessor, and
487 return the successor node. -1 is returned if there is no such edge. */
490 elim_graph_remove_succ_edge (elim_graph g
, int node
, source_location
*locus
)
494 for (x
= 0; x
< g
->edge_list
.length (); x
+= 2)
495 if (g
->edge_list
[x
] == node
)
497 g
->edge_list
[x
] = -1;
498 y
= g
->edge_list
[x
+ 1];
499 g
->edge_list
[x
+ 1] = -1;
500 *locus
= g
->edge_locus
[x
/ 2];
501 g
->edge_locus
[x
/ 2] = UNKNOWN_LOCATION
;
504 *locus
= UNKNOWN_LOCATION
;
509 /* Find all the nodes in GRAPH which are successors to NODE in the
510 edge list. VAR will hold the partition number found. CODE is the
511 code fragment executed for every node found. */
513 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, LOCUS, CODE) \
517 for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \
519 y_ = (GRAPH)->edge_list[x_]; \
522 (void) ((VAR) = (GRAPH)->edge_list[x_ + 1]); \
523 (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \
529 /* Find all the nodes which are predecessors of NODE in the edge list for
530 GRAPH. VAR will hold the partition number found. CODE is the
531 code fragment executed for every node found. */
533 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, LOCUS, CODE) \
537 for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \
539 y_ = (GRAPH)->edge_list[x_ + 1]; \
542 (void) ((VAR) = (GRAPH)->edge_list[x_]); \
543 (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \
549 /* Add T to elimination graph G. */
552 eliminate_name (elim_graph g
, int T
)
554 elim_graph_add_node (g
, T
);
557 /* Return true if this phi argument T should have a copy queued when using
558 var_map MAP. PHI nodes should contain only ssa_names and invariants. A
559 test for ssa_name is definitely simpler, but don't let invalid contents
560 slip through in the meantime. */
563 queue_phi_copy_p (var_map map
, tree t
)
565 if (TREE_CODE (t
) == SSA_NAME
)
567 if (var_to_partition (map
, t
) == NO_PARTITION
)
571 gcc_checking_assert (is_gimple_min_invariant (t
));
575 /* Build elimination graph G for basic block BB on incoming PHI edge
579 eliminate_build (elim_graph g
)
585 clear_elim_graph (g
);
587 for (gsi
= gsi_start_phis (g
->e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
589 gphi
*phi
= gsi
.phi ();
590 source_location locus
;
592 p0
= var_to_partition (g
->map
, gimple_phi_result (phi
));
593 /* Ignore results which are not in partitions. */
594 if (p0
== NO_PARTITION
)
597 Ti
= PHI_ARG_DEF (phi
, g
->e
->dest_idx
);
598 locus
= gimple_phi_arg_location_from_edge (phi
, g
->e
);
600 /* If this argument is a constant, or a SSA_NAME which is being
601 left in SSA form, just queue a copy to be emitted on this
603 if (queue_phi_copy_p (g
->map
, Ti
))
605 /* Save constant copies until all other copies have been emitted
607 g
->const_dests
.safe_push (p0
);
608 g
->const_copies
.safe_push (Ti
);
609 g
->copy_locus
.safe_push (locus
);
613 pi
= var_to_partition (g
->map
, Ti
);
616 eliminate_name (g
, p0
);
617 eliminate_name (g
, pi
);
618 elim_graph_add_edge (g
, p0
, pi
, locus
);
625 /* Push successors of T onto the elimination stack for G. */
628 elim_forward (elim_graph g
, int T
)
631 source_location locus
;
633 bitmap_set_bit (g
->visited
, T
);
634 FOR_EACH_ELIM_GRAPH_SUCC (g
, T
, S
, locus
,
636 if (!bitmap_bit_p (g
->visited
, S
))
639 g
->stack
.safe_push (T
);
643 /* Return 1 if there unvisited predecessors of T in graph G. */
646 elim_unvisited_predecessor (elim_graph g
, int T
)
649 source_location locus
;
651 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
653 if (!bitmap_bit_p (g
->visited
, P
))
659 /* Process predecessors first, and insert a copy. */
662 elim_backward (elim_graph g
, int T
)
665 source_location locus
;
667 bitmap_set_bit (g
->visited
, T
);
668 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
670 if (!bitmap_bit_p (g
->visited
, P
))
672 elim_backward (g
, P
);
673 insert_partition_copy_on_edge (g
->e
, P
, T
, locus
);
678 /* Allocate a new pseudo register usable for storing values sitting
679 in NAME (a decl or SSA name), i.e. with matching mode and attributes. */
682 get_temp_reg (tree name
)
684 tree var
= TREE_CODE (name
) == SSA_NAME
? SSA_NAME_VAR (name
) : name
;
685 tree type
= TREE_TYPE (var
);
687 machine_mode reg_mode
= promote_decl_mode (var
, &unsignedp
);
688 rtx x
= gen_reg_rtx (reg_mode
);
689 if (POINTER_TYPE_P (type
))
690 mark_reg_pointer (x
, TYPE_ALIGN (TREE_TYPE (TREE_TYPE (var
))));
694 /* Insert required copies for T in graph G. Check for a strongly connected
695 region, and create a temporary to break the cycle if one is found. */
698 elim_create (elim_graph g
, int T
)
701 source_location locus
;
703 if (elim_unvisited_predecessor (g
, T
))
705 tree var
= partition_to_var (g
->map
, T
);
706 rtx U
= get_temp_reg (var
);
707 int unsignedsrcp
= TYPE_UNSIGNED (TREE_TYPE (var
));
709 insert_part_to_rtx_on_edge (g
->e
, U
, T
, UNKNOWN_LOCATION
);
710 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
712 if (!bitmap_bit_p (g
->visited
, P
))
714 elim_backward (g
, P
);
715 insert_rtx_to_part_on_edge (g
->e
, P
, U
, unsignedsrcp
, locus
);
721 S
= elim_graph_remove_succ_edge (g
, T
, &locus
);
724 bitmap_set_bit (g
->visited
, T
);
725 insert_partition_copy_on_edge (g
->e
, T
, S
, locus
);
731 /* Eliminate all the phi nodes on edge E in graph G. */
734 eliminate_phi (edge e
, elim_graph g
)
738 gcc_assert (g
->const_copies
.length () == 0);
739 gcc_assert (g
->copy_locus
.length () == 0);
741 /* Abnormal edges already have everything coalesced. */
742 if (e
->flags
& EDGE_ABNORMAL
)
749 if (elim_graph_size (g
) != 0)
753 bitmap_clear (g
->visited
);
754 g
->stack
.truncate (0);
756 FOR_EACH_VEC_ELT (g
->nodes
, x
, part
)
758 if (!bitmap_bit_p (g
->visited
, part
))
759 elim_forward (g
, part
);
762 bitmap_clear (g
->visited
);
763 while (g
->stack
.length () > 0)
766 if (!bitmap_bit_p (g
->visited
, x
))
771 /* If there are any pending constant copies, issue them now. */
772 while (g
->const_copies
.length () > 0)
776 source_location locus
;
778 src
= g
->const_copies
.pop ();
779 dest
= g
->const_dests
.pop ();
780 locus
= g
->copy_locus
.pop ();
781 insert_value_copy_on_edge (e
, dest
, src
, locus
);
786 /* Remove each argument from PHI. If an arg was the last use of an SSA_NAME,
787 check to see if this allows another PHI node to be removed. */
790 remove_gimple_phi_args (gphi
*phi
)
795 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
797 fprintf (dump_file
, "Removing Dead PHI definition: ");
798 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
801 FOR_EACH_PHI_ARG (arg_p
, phi
, iter
, SSA_OP_USE
)
803 tree arg
= USE_FROM_PTR (arg_p
);
804 if (TREE_CODE (arg
) == SSA_NAME
)
806 /* Remove the reference to the existing argument. */
807 SET_USE (arg_p
, NULL_TREE
);
808 if (has_zero_uses (arg
))
811 gimple_stmt_iterator gsi
;
813 stmt
= SSA_NAME_DEF_STMT (arg
);
815 /* Also remove the def if it is a PHI node. */
816 if (gimple_code (stmt
) == GIMPLE_PHI
)
818 remove_gimple_phi_args (as_a
<gphi
*> (stmt
));
819 gsi
= gsi_for_stmt (stmt
);
820 remove_phi_node (&gsi
, true);
828 /* Remove any PHI node which is a virtual PHI, or a PHI with no uses. */
831 eliminate_useless_phis (void)
837 FOR_EACH_BB_FN (bb
, cfun
)
839 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); )
841 gphi
*phi
= gsi
.phi ();
842 result
= gimple_phi_result (phi
);
843 if (virtual_operand_p (result
))
845 #ifdef ENABLE_CHECKING
847 /* There should be no arguments which are not virtual, or the
848 results will be incorrect. */
849 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
851 tree arg
= PHI_ARG_DEF (phi
, i
);
852 if (TREE_CODE (arg
) == SSA_NAME
853 && !virtual_operand_p (arg
))
855 fprintf (stderr
, "Argument of PHI is not virtual (");
856 print_generic_expr (stderr
, arg
, TDF_SLIM
);
857 fprintf (stderr
, "), but the result is :");
858 print_gimple_stmt (stderr
, phi
, 0, TDF_SLIM
);
859 internal_error ("SSA corruption");
863 remove_phi_node (&gsi
, true);
867 /* Also remove real PHIs with no uses. */
868 if (has_zero_uses (result
))
870 remove_gimple_phi_args (phi
);
871 remove_phi_node (&gsi
, true);
881 /* This function will rewrite the current program using the variable mapping
882 found in MAP. If the replacement vector VALUES is provided, any
883 occurrences of partitions with non-null entries in the vector will be
884 replaced with the expression in the vector instead of its mapped
888 rewrite_trees (var_map map ATTRIBUTE_UNUSED
)
890 #ifdef ENABLE_CHECKING
892 /* Search for PHIs where the destination has no partition, but one
893 or more arguments has a partition. This should not happen and can
894 create incorrect code. */
895 FOR_EACH_BB_FN (bb
, cfun
)
898 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
900 gphi
*phi
= gsi
.phi ();
901 tree T0
= var_to_partition_to_var (map
, gimple_phi_result (phi
));
905 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
907 tree arg
= PHI_ARG_DEF (phi
, i
);
909 if (TREE_CODE (arg
) == SSA_NAME
910 && var_to_partition (map
, arg
) != NO_PARTITION
)
912 fprintf (stderr
, "Argument of PHI is in a partition :(");
913 print_generic_expr (stderr
, arg
, TDF_SLIM
);
914 fprintf (stderr
, "), but the result is not :");
915 print_gimple_stmt (stderr
, phi
, 0, TDF_SLIM
);
916 internal_error ("SSA corruption");
925 /* Given the out-of-ssa info object SA (with prepared partitions)
926 eliminate all phi nodes in all basic blocks. Afterwards no
927 basic block will have phi nodes anymore and there are possibly
928 some RTL instructions inserted on edges. */
931 expand_phi_nodes (struct ssaexpand
*sa
)
934 elim_graph g
= new_elim_graph (sa
->map
->num_partitions
);
937 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
,
938 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
939 if (!gimple_seq_empty_p (phi_nodes (bb
)))
943 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
944 eliminate_phi (e
, g
);
945 set_phi_nodes (bb
, NULL
);
946 /* We can't redirect EH edges in RTL land, so we need to do this
947 here. Redirection happens only when splitting is necessary,
948 which it is only for critical edges, normally. For EH edges
949 it might also be necessary when the successor has more than
950 one predecessor. In that case the edge is either required to
951 be fallthru (which EH edges aren't), or the predecessor needs
952 to end with a jump (which again, isn't the case with EH edges).
953 Hence, split all EH edges on which we inserted instructions
954 and whose successor has multiple predecessors. */
955 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
957 if (e
->insns
.r
&& (e
->flags
& EDGE_EH
)
958 && !single_pred_p (e
->dest
))
960 rtx_insn
*insns
= e
->insns
.r
;
964 single_pred_edge (bb
)->insns
.r
= insns
;
971 delete_elim_graph (g
);
975 /* Remove the ssa-names in the current function and translate them into normal
976 compiler variables. PERFORM_TER is true if Temporary Expression Replacement
977 should also be used. */
980 remove_ssa_form (bool perform_ter
, struct ssaexpand
*sa
)
982 bitmap values
= NULL
;
986 map
= coalesce_ssa_name ();
988 /* Return to viewing the variable list as just all reference variables after
989 coalescing has been performed. */
990 partition_view_normal (map
, false);
992 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
994 fprintf (dump_file
, "After Coalescing:\n");
995 dump_var_map (dump_file
, map
);
1000 values
= find_replaceable_exprs (map
);
1001 if (values
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
1002 dump_replaceable_exprs (dump_file
, values
);
1005 rewrite_trees (map
);
1008 sa
->values
= values
;
1009 sa
->partition_has_default_def
= BITMAP_ALLOC (NULL
);
1010 for (i
= 1; i
< num_ssa_names
; i
++)
1012 tree t
= ssa_name (i
);
1013 if (t
&& SSA_NAME_IS_DEFAULT_DEF (t
))
1015 int p
= var_to_partition (map
, t
);
1016 if (p
!= NO_PARTITION
)
1017 bitmap_set_bit (sa
->partition_has_default_def
, p
);
1023 /* If not already done so for basic block BB, assign increasing uids
1024 to each of its instructions. */
1027 maybe_renumber_stmts_bb (basic_block bb
)
1030 gimple_stmt_iterator gsi
;
1035 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1037 gimple stmt
= gsi_stmt (gsi
);
1038 gimple_set_uid (stmt
, i
);
1044 /* Return true if we can determine that the SSA_NAMEs RESULT (a result
1045 of a PHI node) and ARG (one of its arguments) conflict. Return false
1046 otherwise, also when we simply aren't sure. */
1049 trivially_conflicts_p (basic_block bb
, tree result
, tree arg
)
1052 imm_use_iterator imm_iter
;
1053 gimple defa
= SSA_NAME_DEF_STMT (arg
);
1055 /* If ARG isn't defined in the same block it's too complicated for
1057 if (gimple_bb (defa
) != bb
)
1060 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, result
)
1062 gimple use_stmt
= USE_STMT (use
);
1063 if (is_gimple_debug (use_stmt
))
1065 /* Now, if there's a use of RESULT that lies outside this basic block,
1066 then there surely is a conflict with ARG. */
1067 if (gimple_bb (use_stmt
) != bb
)
1069 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
1071 /* The use now is in a real stmt of BB, so if ARG was defined
1072 in a PHI node (like RESULT) both conflict. */
1073 if (gimple_code (defa
) == GIMPLE_PHI
)
1075 maybe_renumber_stmts_bb (bb
);
1076 /* If the use of RESULT occurs after the definition of ARG,
1077 the two conflict too. */
1078 if (gimple_uid (defa
) < gimple_uid (use_stmt
))
1086 /* Search every PHI node for arguments associated with backedges which
1087 we can trivially determine will need a copy (the argument is either
1088 not an SSA_NAME or the argument has a different underlying variable
1089 than the PHI result).
1091 Insert a copy from the PHI argument to a new destination at the
1092 end of the block with the backedge to the top of the loop. Update
1093 the PHI argument to reference this new destination. */
1096 insert_backedge_copies (void)
1101 mark_dfs_back_edges ();
1103 FOR_EACH_BB_FN (bb
, cfun
)
1105 /* Mark block as possibly needing calculation of UIDs. */
1108 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1110 gphi
*phi
= gsi
.phi ();
1111 tree result
= gimple_phi_result (phi
);
1114 if (virtual_operand_p (result
))
1117 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1119 tree arg
= gimple_phi_arg_def (phi
, i
);
1120 edge e
= gimple_phi_arg_edge (phi
, i
);
1122 /* If the argument is not an SSA_NAME, then we will need a
1123 constant initialization. If the argument is an SSA_NAME with
1124 a different underlying variable then a copy statement will be
1126 if ((e
->flags
& EDGE_DFS_BACK
)
1127 && (TREE_CODE (arg
) != SSA_NAME
1128 || SSA_NAME_VAR (arg
) != SSA_NAME_VAR (result
)
1129 || trivially_conflicts_p (bb
, result
, arg
)))
1134 gimple_stmt_iterator gsi2
;
1136 gsi2
= gsi_last_bb (gimple_phi_arg_edge (phi
, i
)->src
);
1137 if (!gsi_end_p (gsi2
))
1138 last
= gsi_stmt (gsi2
);
1140 /* In theory the only way we ought to get back to the
1141 start of a loop should be with a COND_EXPR or GOTO_EXPR.
1142 However, better safe than sorry.
1143 If the block ends with a control statement or
1144 something that might throw, then we have to
1145 insert this assignment before the last
1146 statement. Else insert it after the last statement. */
1147 if (last
&& stmt_ends_bb_p (last
))
1149 /* If the last statement in the block is the definition
1150 site of the PHI argument, then we can't insert
1151 anything after it. */
1152 if (TREE_CODE (arg
) == SSA_NAME
1153 && SSA_NAME_DEF_STMT (arg
) == last
)
1157 /* Create a new instance of the underlying variable of the
1159 name
= copy_ssa_name (result
);
1160 stmt
= gimple_build_assign (name
,
1161 gimple_phi_arg_def (phi
, i
));
1163 /* copy location if present. */
1164 if (gimple_phi_arg_has_location (phi
, i
))
1165 gimple_set_location (stmt
,
1166 gimple_phi_arg_location (phi
, i
));
1168 /* Insert the new statement into the block and update
1170 if (last
&& stmt_ends_bb_p (last
))
1171 gsi_insert_before (&gsi2
, stmt
, GSI_NEW_STMT
);
1173 gsi_insert_after (&gsi2
, stmt
, GSI_NEW_STMT
);
1174 SET_PHI_ARG_DEF (phi
, i
, name
);
1179 /* Unmark this block again. */
1184 /* Free all memory associated with going out of SSA form. SA is
1185 the outof-SSA info object. */
1188 finish_out_of_ssa (struct ssaexpand
*sa
)
1190 free (sa
->partition_to_pseudo
);
1192 BITMAP_FREE (sa
->values
);
1193 delete_var_map (sa
->map
);
1194 BITMAP_FREE (sa
->partition_has_default_def
);
1195 memset (sa
, 0, sizeof *sa
);
1198 /* Take the current function out of SSA form, translating PHIs as described in
1199 R. Morgan, ``Building an Optimizing Compiler'',
1200 Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */
1203 rewrite_out_of_ssa (struct ssaexpand
*sa
)
1205 /* If elimination of a PHI requires inserting a copy on a backedge,
1206 then we will have to split the backedge which has numerous
1207 undesirable performance effects.
1209 A significant number of such cases can be handled here by inserting
1210 copies into the loop itself. */
1211 insert_backedge_copies ();
1214 /* Eliminate PHIs which are of no use, such as virtual or dead phis. */
1215 eliminate_useless_phis ();
1217 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1218 gimple_dump_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);
1220 remove_ssa_form (flag_tree_ter
, sa
);
1222 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1223 gimple_dump_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);