1 /* Convert a program in SSA form into Normal form.
2 Copyright (C) 2004-2016 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"
31 #include "gimple-pretty-print.h"
32 #include "diagnostic-core.h"
33 #include "stor-layout.h"
37 #include "gimple-iterator.h"
40 #include "tree-ssa-live.h"
41 #include "tree-ssa-ter.h"
42 #include "tree-ssa-coalesce.h"
43 #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. */
51 /* Return TRUE if expression STMT is suitable for replacement. */
54 ssa_is_replaceable_p (gimple
*stmt
)
60 /* Only consider modify stmts. */
61 if (!is_gimple_assign (stmt
))
64 /* If the statement may throw an exception, it cannot be replaced. */
65 if (stmt_could_throw_p (stmt
))
68 /* Punt if there is more than 1 def. */
69 def
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_DEF
);
73 /* Only consider definitions which have a single use. */
74 if (!single_imm_use (def
, &use_p
, &use_stmt
))
77 /* Used in this block, but at the TOP of the block, not the end. */
78 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
81 /* There must be no VDEFs. */
82 if (gimple_vdef (stmt
))
85 /* Float expressions must go through memory if float-store is on. */
87 && FLOAT_TYPE_P (gimple_expr_type (stmt
)))
90 /* An assignment with a register variable on the RHS is not
92 if (gimple_assign_rhs_code (stmt
) == VAR_DECL
93 && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt
)))
96 /* No function calls can be replaced. */
97 if (is_gimple_call (stmt
))
100 /* Leave any stmt with volatile operands alone as well. */
101 if (gimple_has_volatile_ops (stmt
))
108 /* Used to hold all the components required to do SSA PHI elimination.
109 The node and pred/succ list is a simple linear list of nodes and
110 edges represented as pairs of nodes.
112 The predecessor and successor list: Nodes are entered in pairs, where
113 [0] ->PRED, [1]->SUCC. All the even indexes in the array represent
114 predecessors, all the odd elements are successors.
117 When implemented as bitmaps, very large programs SSA->Normal times were
118 being dominated by clearing the interference graph.
120 Typically this list of edges is extremely small since it only includes
121 PHI results and uses from a single edge which have not coalesced with
122 each other. This means that no virtual PHI nodes are included, and
123 empirical evidence suggests that the number of edges rarely exceed
124 3, and in a bootstrap of GCC, the maximum size encountered was 7.
125 This also limits the number of possible nodes that are involved to
126 rarely more than 6, and in the bootstrap of gcc, the maximum number
127 of nodes encountered was 12. */
131 /* Size of the elimination vectors. */
134 /* List of nodes in the elimination graph. */
137 /* The predecessor and successor edge list. */
140 /* Source locus on each edge */
141 vec
<source_location
> edge_locus
;
143 /* Visited vector. */
146 /* Stack for visited nodes. */
149 /* The variable partition map. */
152 /* Edge being eliminated by this graph. */
155 /* List of constant copies to emit. These are pushed on in pairs. */
156 vec
<int> const_dests
;
157 vec
<tree
> const_copies
;
159 /* Source locations for any constant copies. */
160 vec
<source_location
> copy_locus
;
164 /* For an edge E find out a good source location to associate with
165 instructions inserted on edge E. If E has an implicit goto set,
166 use its location. Otherwise search instructions in predecessors
167 of E for a location, and use that one. That makes sense because
168 we insert on edges for PHI nodes, and effects of PHIs happen on
169 the end of the predecessor conceptually. */
172 set_location_for_edge (edge e
)
176 set_curr_insn_location (e
->goto_locus
);
180 basic_block bb
= e
->src
;
181 gimple_stmt_iterator gsi
;
185 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
187 gimple
*stmt
= gsi_stmt (gsi
);
188 if (is_gimple_debug (stmt
))
190 if (gimple_has_location (stmt
) || gimple_block (stmt
))
192 set_curr_insn_location (gimple_location (stmt
));
196 /* Nothing found in this basic block. Make a half-assed attempt
197 to continue with another block. */
198 if (single_pred_p (bb
))
199 bb
= single_pred (bb
);
203 while (bb
!= e
->src
);
207 /* Emit insns to copy SRC into DEST converting SRC if necessary. As
208 SRC/DEST might be BLKmode memory locations SIZEEXP is a tree from
209 which we deduce the size to copy in that case. */
211 static inline rtx_insn
*
212 emit_partition_copy (rtx dest
, rtx src
, int unsignedsrcp
, tree sizeexp
)
216 if (GET_MODE (src
) != VOIDmode
&& GET_MODE (src
) != GET_MODE (dest
))
217 src
= convert_to_mode (GET_MODE (dest
), src
, unsignedsrcp
);
218 if (GET_MODE (src
) == BLKmode
)
220 gcc_assert (GET_MODE (dest
) == BLKmode
);
221 emit_block_move (dest
, src
, expr_size (sizeexp
), BLOCK_OP_NORMAL
);
224 emit_move_insn (dest
, src
);
225 do_pending_stack_adjust ();
227 rtx_insn
*seq
= get_insns ();
233 /* Insert a copy instruction from partition SRC to DEST onto edge E. */
236 insert_partition_copy_on_edge (edge e
, int dest
, int src
, source_location locus
)
239 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
242 "Inserting a partition copy on edge BB%d->BB%d :"
245 e
->dest
->index
, dest
, src
);
246 fprintf (dump_file
, "\n");
249 gcc_assert (SA
.partition_to_pseudo
[dest
]);
250 gcc_assert (SA
.partition_to_pseudo
[src
]);
252 set_location_for_edge (e
);
253 /* If a locus is provided, override the default. */
255 set_curr_insn_location (locus
);
257 var
= partition_to_var (SA
.map
, src
);
258 rtx_insn
*seq
= emit_partition_copy (copy_rtx (SA
.partition_to_pseudo
[dest
]),
259 copy_rtx (SA
.partition_to_pseudo
[src
]),
260 TYPE_UNSIGNED (TREE_TYPE (var
)),
263 insert_insn_on_edge (seq
, e
);
266 /* Insert a copy instruction from expression SRC to partition DEST
270 insert_value_copy_on_edge (edge e
, int dest
, tree src
, source_location locus
)
272 rtx dest_rtx
, seq
, x
;
273 machine_mode dest_mode
, src_mode
;
276 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
279 "Inserting a value copy on edge BB%d->BB%d : PART.%d = ",
281 e
->dest
->index
, dest
);
282 print_generic_expr (dump_file
, src
, TDF_SLIM
);
283 fprintf (dump_file
, "\n");
286 dest_rtx
= copy_rtx (SA
.partition_to_pseudo
[dest
]);
287 gcc_assert (dest_rtx
);
289 set_location_for_edge (e
);
290 /* If a locus is provided, override the default. */
292 set_curr_insn_location (locus
);
296 tree name
= partition_to_var (SA
.map
, dest
);
297 src_mode
= TYPE_MODE (TREE_TYPE (src
));
298 dest_mode
= GET_MODE (dest_rtx
);
299 gcc_assert (src_mode
== TYPE_MODE (TREE_TYPE (name
)));
300 gcc_assert (!REG_P (dest_rtx
)
301 || dest_mode
== promote_ssa_mode (name
, &unsignedp
));
303 if (src_mode
!= dest_mode
)
305 x
= expand_expr (src
, NULL
, src_mode
, EXPAND_NORMAL
);
306 x
= convert_modes (dest_mode
, src_mode
, x
, unsignedp
);
308 else if (src_mode
== BLKmode
)
311 store_expr (src
, x
, 0, false, false);
314 x
= expand_expr (src
, dest_rtx
, dest_mode
, EXPAND_NORMAL
);
317 emit_move_insn (dest_rtx
, x
);
318 do_pending_stack_adjust ();
323 insert_insn_on_edge (seq
, e
);
326 /* Insert a copy instruction from RTL expression SRC to partition DEST
330 insert_rtx_to_part_on_edge (edge e
, int dest
, rtx src
, int unsignedsrcp
,
331 source_location locus
)
333 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
336 "Inserting a temp copy on edge BB%d->BB%d : PART.%d = ",
338 e
->dest
->index
, dest
);
339 print_simple_rtl (dump_file
, src
);
340 fprintf (dump_file
, "\n");
343 gcc_assert (SA
.partition_to_pseudo
[dest
]);
345 set_location_for_edge (e
);
346 /* If a locus is provided, override the default. */
348 set_curr_insn_location (locus
);
350 /* We give the destination as sizeexp in case src/dest are BLKmode
351 mems. Usually we give the source. As we result from SSA names
352 the left and right size should be the same (and no WITH_SIZE_EXPR
353 involved), so it doesn't matter. */
354 rtx_insn
*seq
= emit_partition_copy (copy_rtx (SA
.partition_to_pseudo
[dest
]),
356 partition_to_var (SA
.map
, dest
));
358 insert_insn_on_edge (seq
, e
);
361 /* Insert a copy instruction from partition SRC to RTL lvalue DEST
365 insert_part_to_rtx_on_edge (edge e
, rtx dest
, int src
, source_location locus
)
368 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
371 "Inserting a temp copy on edge BB%d->BB%d : ",
374 print_simple_rtl (dump_file
, dest
);
375 fprintf (dump_file
, "= PART.%d\n", src
);
378 gcc_assert (SA
.partition_to_pseudo
[src
]);
380 set_location_for_edge (e
);
381 /* If a locus is provided, override the default. */
383 set_curr_insn_location (locus
);
385 var
= partition_to_var (SA
.map
, src
);
386 rtx_insn
*seq
= emit_partition_copy (dest
,
387 copy_rtx (SA
.partition_to_pseudo
[src
]),
388 TYPE_UNSIGNED (TREE_TYPE (var
)),
391 insert_insn_on_edge (seq
, e
);
395 /* Create an elimination graph with SIZE nodes and associated data
399 new_elim_graph (int size
)
401 elim_graph
*g
= (elim_graph
*) xmalloc (sizeof (struct elim_graph
));
403 g
->nodes
.create (30);
404 g
->const_dests
.create (20);
405 g
->const_copies
.create (20);
406 g
->copy_locus
.create (10);
407 g
->edge_list
.create (20);
408 g
->edge_locus
.create (10);
409 g
->stack
.create (30);
411 g
->visited
= sbitmap_alloc (size
);
417 /* Empty elimination graph G. */
420 clear_elim_graph (elim_graph
*g
)
422 g
->nodes
.truncate (0);
423 g
->edge_list
.truncate (0);
424 g
->edge_locus
.truncate (0);
428 /* Delete elimination graph G. */
431 delete_elim_graph (elim_graph
*g
)
433 sbitmap_free (g
->visited
);
435 g
->edge_list
.release ();
436 g
->const_copies
.release ();
437 g
->const_dests
.release ();
439 g
->copy_locus
.release ();
440 g
->edge_locus
.release ();
446 /* Return the number of nodes in graph G. */
449 elim_graph_size (elim_graph
*g
)
451 return g
->nodes
.length ();
455 /* Add NODE to graph G, if it doesn't exist already. */
458 elim_graph_add_node (elim_graph
*g
, int node
)
463 FOR_EACH_VEC_ELT (g
->nodes
, x
, t
)
466 g
->nodes
.safe_push (node
);
470 /* Add the edge PRED->SUCC to graph G. */
473 elim_graph_add_edge (elim_graph
*g
, int pred
, int succ
, source_location locus
)
475 g
->edge_list
.safe_push (pred
);
476 g
->edge_list
.safe_push (succ
);
477 g
->edge_locus
.safe_push (locus
);
481 /* Remove an edge from graph G for which NODE is the predecessor, and
482 return the successor node. -1 is returned if there is no such edge. */
485 elim_graph_remove_succ_edge (elim_graph
*g
, int node
, source_location
*locus
)
489 for (x
= 0; x
< g
->edge_list
.length (); x
+= 2)
490 if (g
->edge_list
[x
] == node
)
492 g
->edge_list
[x
] = -1;
493 y
= g
->edge_list
[x
+ 1];
494 g
->edge_list
[x
+ 1] = -1;
495 *locus
= g
->edge_locus
[x
/ 2];
496 g
->edge_locus
[x
/ 2] = UNKNOWN_LOCATION
;
499 *locus
= UNKNOWN_LOCATION
;
504 /* Find all the nodes in GRAPH which are successors to NODE in the
505 edge list. VAR will hold the partition number found. CODE is the
506 code fragment executed for every node found. */
508 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, LOCUS, CODE) \
512 for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \
514 y_ = (GRAPH)->edge_list[x_]; \
517 (void) ((VAR) = (GRAPH)->edge_list[x_ + 1]); \
518 (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \
524 /* Find all the nodes which are predecessors of NODE in the edge list for
525 GRAPH. VAR will hold the partition number found. CODE is the
526 code fragment executed for every node found. */
528 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, LOCUS, CODE) \
532 for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \
534 y_ = (GRAPH)->edge_list[x_ + 1]; \
537 (void) ((VAR) = (GRAPH)->edge_list[x_]); \
538 (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \
544 /* Add T to elimination graph G. */
547 eliminate_name (elim_graph
*g
, int T
)
549 elim_graph_add_node (g
, T
);
552 /* Return true if this phi argument T should have a copy queued when using
553 var_map MAP. PHI nodes should contain only ssa_names and invariants. A
554 test for ssa_name is definitely simpler, but don't let invalid contents
555 slip through in the meantime. */
558 queue_phi_copy_p (var_map map
, tree t
)
560 if (TREE_CODE (t
) == SSA_NAME
)
562 if (var_to_partition (map
, t
) == NO_PARTITION
)
566 gcc_checking_assert (is_gimple_min_invariant (t
));
570 /* Build elimination graph G for basic block BB on incoming PHI edge
574 eliminate_build (elim_graph
*g
)
580 clear_elim_graph (g
);
582 for (gsi
= gsi_start_phis (g
->e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
584 gphi
*phi
= gsi
.phi ();
585 source_location locus
;
587 p0
= var_to_partition (g
->map
, gimple_phi_result (phi
));
588 /* Ignore results which are not in partitions. */
589 if (p0
== NO_PARTITION
)
592 Ti
= PHI_ARG_DEF (phi
, g
->e
->dest_idx
);
593 locus
= gimple_phi_arg_location_from_edge (phi
, g
->e
);
595 /* If this argument is a constant, or a SSA_NAME which is being
596 left in SSA form, just queue a copy to be emitted on this
598 if (queue_phi_copy_p (g
->map
, Ti
))
600 /* Save constant copies until all other copies have been emitted
602 g
->const_dests
.safe_push (p0
);
603 g
->const_copies
.safe_push (Ti
);
604 g
->copy_locus
.safe_push (locus
);
608 pi
= var_to_partition (g
->map
, Ti
);
611 eliminate_name (g
, p0
);
612 eliminate_name (g
, pi
);
613 elim_graph_add_edge (g
, p0
, pi
, locus
);
620 /* Push successors of T onto the elimination stack for G. */
623 elim_forward (elim_graph
*g
, int T
)
626 source_location locus
;
628 bitmap_set_bit (g
->visited
, T
);
629 FOR_EACH_ELIM_GRAPH_SUCC (g
, T
, S
, locus
,
631 if (!bitmap_bit_p (g
->visited
, S
))
634 g
->stack
.safe_push (T
);
638 /* Return 1 if there unvisited predecessors of T in graph G. */
641 elim_unvisited_predecessor (elim_graph
*g
, int T
)
644 source_location locus
;
646 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
648 if (!bitmap_bit_p (g
->visited
, P
))
654 /* Process predecessors first, and insert a copy. */
657 elim_backward (elim_graph
*g
, int T
)
660 source_location locus
;
662 bitmap_set_bit (g
->visited
, T
);
663 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
665 if (!bitmap_bit_p (g
->visited
, P
))
667 elim_backward (g
, P
);
668 insert_partition_copy_on_edge (g
->e
, P
, T
, locus
);
673 /* Allocate a new pseudo register usable for storing values sitting
674 in NAME (a decl or SSA name), i.e. with matching mode and attributes. */
677 get_temp_reg (tree name
)
679 tree type
= TREE_TYPE (name
);
681 machine_mode reg_mode
= promote_ssa_mode (name
, &unsignedp
);
682 rtx x
= gen_reg_rtx (reg_mode
);
683 if (POINTER_TYPE_P (type
))
684 mark_reg_pointer (x
, TYPE_ALIGN (TREE_TYPE (type
)));
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 (gphi
*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 (as_a
<gphi
*> (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)
831 FOR_EACH_BB_FN (bb
, cfun
)
833 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); )
835 gphi
*phi
= gsi
.phi ();
836 result
= gimple_phi_result (phi
);
837 if (virtual_operand_p (result
))
839 /* There should be no arguments which are not virtual, or the
840 results will be incorrect. */
842 for (size_t i
= 0; i
< gimple_phi_num_args (phi
); i
++)
844 tree arg
= PHI_ARG_DEF (phi
, i
);
845 if (TREE_CODE (arg
) == SSA_NAME
846 && !virtual_operand_p (arg
))
848 fprintf (stderr
, "Argument of PHI is not virtual (");
849 print_generic_expr (stderr
, arg
, TDF_SLIM
);
850 fprintf (stderr
, "), but the result is :");
851 print_gimple_stmt (stderr
, phi
, 0, TDF_SLIM
);
852 internal_error ("SSA corruption");
856 remove_phi_node (&gsi
, true);
860 /* Also remove real PHIs with no uses. */
861 if (has_zero_uses (result
))
863 remove_gimple_phi_args (phi
);
864 remove_phi_node (&gsi
, true);
874 /* This function will rewrite the current program using the variable mapping
875 found in MAP. If the replacement vector VALUES is provided, any
876 occurrences of partitions with non-null entries in the vector will be
877 replaced with the expression in the vector instead of its mapped
881 rewrite_trees (var_map map
)
887 /* Search for PHIs where the destination has no partition, but one
888 or more arguments has a partition. This should not happen and can
889 create incorrect code. */
890 FOR_EACH_BB_FN (bb
, cfun
)
893 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
895 gphi
*phi
= gsi
.phi ();
896 tree T0
= var_to_partition_to_var (map
, gimple_phi_result (phi
));
900 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
902 tree arg
= PHI_ARG_DEF (phi
, i
);
904 if (TREE_CODE (arg
) == SSA_NAME
905 && var_to_partition (map
, arg
) != NO_PARTITION
)
907 fprintf (stderr
, "Argument of PHI is in a partition :(");
908 print_generic_expr (stderr
, arg
, TDF_SLIM
);
909 fprintf (stderr
, "), but the result is not :");
910 print_gimple_stmt (stderr
, phi
, 0, TDF_SLIM
);
911 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_FOR_FN (cfun
)->next_bb
,
932 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
933 if (!gimple_seq_empty_p (phi_nodes (bb
)))
937 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
938 eliminate_phi (e
, g
);
939 set_phi_nodes (bb
, NULL
);
940 /* We can't redirect EH edges in RTL land, so we need to do this
941 here. Redirection happens only when splitting is necessary,
942 which it is only for critical edges, normally. For EH edges
943 it might also be necessary when the successor has more than
944 one predecessor. In that case the edge is either required to
945 be fallthru (which EH edges aren't), or the predecessor needs
946 to end with a jump (which again, isn't the case with EH edges).
947 Hence, split all EH edges on which we inserted instructions
948 and whose successor has multiple predecessors. */
949 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
951 if (e
->insns
.r
&& (e
->flags
& EDGE_EH
)
952 && !single_pred_p (e
->dest
))
954 rtx_insn
*insns
= e
->insns
.r
;
958 single_pred_edge (bb
)->insns
.r
= insns
;
965 delete_elim_graph (g
);
969 /* Remove the ssa-names in the current function and translate them into normal
970 compiler variables. PERFORM_TER is true if Temporary Expression Replacement
971 should also be used. */
974 remove_ssa_form (bool perform_ter
, struct ssaexpand
*sa
)
976 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
);
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
->partitions_for_parm_default_defs
= get_parm_default_def_partitions (map
);
1006 /* If not already done so for basic block BB, assign increasing uids
1007 to each of its instructions. */
1010 maybe_renumber_stmts_bb (basic_block bb
)
1013 gimple_stmt_iterator gsi
;
1018 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1020 gimple
*stmt
= gsi_stmt (gsi
);
1021 gimple_set_uid (stmt
, i
);
1027 /* Return true if we can determine that the SSA_NAMEs RESULT (a result
1028 of a PHI node) and ARG (one of its arguments) conflict. Return false
1029 otherwise, also when we simply aren't sure. */
1032 trivially_conflicts_p (basic_block bb
, tree result
, tree arg
)
1035 imm_use_iterator imm_iter
;
1036 gimple
*defa
= SSA_NAME_DEF_STMT (arg
);
1038 /* If ARG isn't defined in the same block it's too complicated for
1040 if (gimple_bb (defa
) != bb
)
1043 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, result
)
1045 gimple
*use_stmt
= USE_STMT (use
);
1046 if (is_gimple_debug (use_stmt
))
1048 /* Now, if there's a use of RESULT that lies outside this basic block,
1049 then there surely is a conflict with ARG. */
1050 if (gimple_bb (use_stmt
) != bb
)
1052 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
1054 /* The use now is in a real stmt of BB, so if ARG was defined
1055 in a PHI node (like RESULT) both conflict. */
1056 if (gimple_code (defa
) == GIMPLE_PHI
)
1058 maybe_renumber_stmts_bb (bb
);
1059 /* If the use of RESULT occurs after the definition of ARG,
1060 the two conflict too. */
1061 if (gimple_uid (defa
) < gimple_uid (use_stmt
))
1069 /* Search every PHI node for arguments associated with backedges which
1070 we can trivially determine will need a copy (the argument is either
1071 not an SSA_NAME or the argument has a different underlying variable
1072 than the PHI result).
1074 Insert a copy from the PHI argument to a new destination at the
1075 end of the block with the backedge to the top of the loop. Update
1076 the PHI argument to reference this new destination. */
1079 insert_backedge_copies (void)
1084 mark_dfs_back_edges ();
1086 FOR_EACH_BB_FN (bb
, cfun
)
1088 /* Mark block as possibly needing calculation of UIDs. */
1091 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1093 gphi
*phi
= gsi
.phi ();
1094 tree result
= gimple_phi_result (phi
);
1097 if (virtual_operand_p (result
))
1100 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1102 tree arg
= gimple_phi_arg_def (phi
, i
);
1103 edge e
= gimple_phi_arg_edge (phi
, i
);
1105 /* If the argument is not an SSA_NAME, then we will need a
1106 constant initialization. If the argument is an SSA_NAME with
1107 a different underlying variable then a copy statement will be
1109 if ((e
->flags
& EDGE_DFS_BACK
)
1110 && (TREE_CODE (arg
) != SSA_NAME
1111 || SSA_NAME_VAR (arg
) != SSA_NAME_VAR (result
)
1112 || trivially_conflicts_p (bb
, result
, arg
)))
1116 gimple
*last
= NULL
;
1117 gimple_stmt_iterator gsi2
;
1119 gsi2
= gsi_last_bb (gimple_phi_arg_edge (phi
, i
)->src
);
1120 if (!gsi_end_p (gsi2
))
1121 last
= gsi_stmt (gsi2
);
1123 /* In theory the only way we ought to get back to the
1124 start of a loop should be with a COND_EXPR or GOTO_EXPR.
1125 However, better safe than sorry.
1126 If the block ends with a control statement or
1127 something that might throw, then we have to
1128 insert this assignment before the last
1129 statement. Else insert it after the last statement. */
1130 if (last
&& stmt_ends_bb_p (last
))
1132 /* If the last statement in the block is the definition
1133 site of the PHI argument, then we can't insert
1134 anything after it. */
1135 if (TREE_CODE (arg
) == SSA_NAME
1136 && SSA_NAME_DEF_STMT (arg
) == last
)
1140 /* Create a new instance of the underlying variable of the
1142 name
= copy_ssa_name (result
);
1143 stmt
= gimple_build_assign (name
,
1144 gimple_phi_arg_def (phi
, i
));
1146 /* copy location if present. */
1147 if (gimple_phi_arg_has_location (phi
, i
))
1148 gimple_set_location (stmt
,
1149 gimple_phi_arg_location (phi
, i
));
1151 /* Insert the new statement into the block and update
1153 if (last
&& stmt_ends_bb_p (last
))
1154 gsi_insert_before (&gsi2
, stmt
, GSI_NEW_STMT
);
1156 gsi_insert_after (&gsi2
, stmt
, GSI_NEW_STMT
);
1157 SET_PHI_ARG_DEF (phi
, i
, name
);
1162 /* Unmark this block again. */
1167 /* Free all memory associated with going out of SSA form. SA is
1168 the outof-SSA info object. */
1171 finish_out_of_ssa (struct ssaexpand
*sa
)
1173 free (sa
->partition_to_pseudo
);
1175 BITMAP_FREE (sa
->values
);
1176 delete_var_map (sa
->map
);
1177 BITMAP_FREE (sa
->partitions_for_parm_default_defs
);
1178 memset (sa
, 0, sizeof *sa
);
1181 /* Take the current function out of SSA form, translating PHIs as described in
1182 R. Morgan, ``Building an Optimizing Compiler'',
1183 Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */
1186 rewrite_out_of_ssa (struct ssaexpand
*sa
)
1188 /* If elimination of a PHI requires inserting a copy on a backedge,
1189 then we will have to split the backedge which has numerous
1190 undesirable performance effects.
1192 A significant number of such cases can be handled here by inserting
1193 copies into the loop itself. */
1194 insert_backedge_copies ();
1197 /* Eliminate PHIs which are of no use, such as virtual or dead phis. */
1198 eliminate_useless_phis ();
1200 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1201 gimple_dump_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);
1203 remove_ssa_form (flag_tree_ter
, sa
);
1205 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1206 gimple_dump_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);