1 /* Convert a program in SSA form into Normal form.
2 Copyright (C) 2004-2013 Free Software Foundation, Inc.
3 Contributed by Andrew Macleod <amacleod@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
27 #include "basic-block.h"
28 #include "gimple-pretty-print.h"
33 #include "diagnostic-core.h"
34 #include "tree-outof-ssa.h"
36 /* FIXME: A lot of code here deals with expanding to RTL. All that code
37 should be in cfgexpand.c. */
40 /* Return TRUE if expression STMT is suitable for replacement. */
43 ssa_is_replaceable_p (gimple stmt
)
49 /* Only consider modify stmts. */
50 if (!is_gimple_assign (stmt
))
53 /* If the statement may throw an exception, it cannot be replaced. */
54 if (stmt_could_throw_p (stmt
))
57 /* Punt if there is more than 1 def. */
58 def
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_DEF
);
62 /* Only consider definitions which have a single use. */
63 if (!single_imm_use (def
, &use_p
, &use_stmt
))
66 /* Used in this block, but at the TOP of the block, not the end. */
67 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
70 /* There must be no VDEFs. */
71 if (gimple_vdef (stmt
))
74 /* Float expressions must go through memory if float-store is on. */
76 && FLOAT_TYPE_P (gimple_expr_type (stmt
)))
79 /* An assignment with a register variable on the RHS is not
81 if (gimple_assign_rhs_code (stmt
) == VAR_DECL
82 && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt
)))
85 /* No function calls can be replaced. */
86 if (is_gimple_call (stmt
))
89 /* Leave any stmt with volatile operands alone as well. */
90 if (gimple_has_volatile_ops (stmt
))
97 /* Used to hold all the components required to do SSA PHI elimination.
98 The node and pred/succ list is a simple linear list of nodes and
99 edges represented as pairs of nodes.
101 The predecessor and successor list: Nodes are entered in pairs, where
102 [0] ->PRED, [1]->SUCC. All the even indexes in the array represent
103 predecessors, all the odd elements are successors.
106 When implemented as bitmaps, very large programs SSA->Normal times were
107 being dominated by clearing the interference graph.
109 Typically this list of edges is extremely small since it only includes
110 PHI results and uses from a single edge which have not coalesced with
111 each other. This means that no virtual PHI nodes are included, and
112 empirical evidence suggests that the number of edges rarely exceed
113 3, and in a bootstrap of GCC, the maximum size encountered was 7.
114 This also limits the number of possible nodes that are involved to
115 rarely more than 6, and in the bootstrap of gcc, the maximum number
116 of nodes encountered was 12. */
118 typedef struct _elim_graph
{
119 /* Size of the elimination vectors. */
122 /* List of nodes in the elimination graph. */
125 /* The predecessor and successor edge list. */
128 /* Source locus on each edge */
129 vec
<source_location
> edge_locus
;
131 /* Visited vector. */
134 /* Stack for visited nodes. */
137 /* The variable partition map. */
140 /* Edge being eliminated by this graph. */
143 /* List of constant copies to emit. These are pushed on in pairs. */
144 vec
<int> const_dests
;
145 vec
<tree
> const_copies
;
147 /* Source locations for any constant copies. */
148 vec
<source_location
> copy_locus
;
152 /* For an edge E find out a good source location to associate with
153 instructions inserted on edge E. If E has an implicit goto set,
154 use its location. Otherwise search instructions in predecessors
155 of E for a location, and use that one. That makes sense because
156 we insert on edges for PHI nodes, and effects of PHIs happen on
157 the end of the predecessor conceptually. */
160 set_location_for_edge (edge e
)
164 set_curr_insn_location (e
->goto_locus
);
168 basic_block bb
= e
->src
;
169 gimple_stmt_iterator gsi
;
173 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
175 gimple stmt
= gsi_stmt (gsi
);
176 if (is_gimple_debug (stmt
))
178 if (gimple_has_location (stmt
) || gimple_block (stmt
))
180 set_curr_insn_location (gimple_location (stmt
));
184 /* Nothing found in this basic block. Make a half-assed attempt
185 to continue with another block. */
186 if (single_pred_p (bb
))
187 bb
= single_pred (bb
);
191 while (bb
!= e
->src
);
195 /* Emit insns to copy SRC into DEST converting SRC if necessary. As
196 SRC/DEST might be BLKmode memory locations SIZEEXP is a tree from
197 which we deduce the size to copy in that case. */
200 emit_partition_copy (rtx dest
, rtx src
, int unsignedsrcp
, tree sizeexp
)
206 if (GET_MODE (src
) != VOIDmode
&& GET_MODE (src
) != GET_MODE (dest
))
207 src
= convert_to_mode (GET_MODE (dest
), src
, unsignedsrcp
);
208 if (GET_MODE (src
) == BLKmode
)
210 gcc_assert (GET_MODE (dest
) == BLKmode
);
211 emit_block_move (dest
, src
, expr_size (sizeexp
), BLOCK_OP_NORMAL
);
214 emit_move_insn (dest
, src
);
222 /* Insert a copy instruction from partition SRC to DEST onto edge E. */
225 insert_partition_copy_on_edge (edge e
, int dest
, int src
, source_location locus
)
229 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
232 "Inserting a partition copy on edge BB%d->BB%d :"
235 e
->dest
->index
, dest
, src
);
236 fprintf (dump_file
, "\n");
239 gcc_assert (SA
.partition_to_pseudo
[dest
]);
240 gcc_assert (SA
.partition_to_pseudo
[src
]);
242 set_location_for_edge (e
);
243 /* If a locus is provided, override the default. */
245 set_curr_insn_location (locus
);
247 var
= partition_to_var (SA
.map
, src
);
248 seq
= emit_partition_copy (SA
.partition_to_pseudo
[dest
],
249 SA
.partition_to_pseudo
[src
],
250 TYPE_UNSIGNED (TREE_TYPE (var
)),
253 insert_insn_on_edge (seq
, e
);
256 /* Insert a copy instruction from expression SRC to partition DEST
260 insert_value_copy_on_edge (edge e
, int dest
, tree src
, source_location locus
)
263 enum machine_mode dest_mode
, src_mode
;
267 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
270 "Inserting a value copy on edge BB%d->BB%d : PART.%d = ",
272 e
->dest
->index
, dest
);
273 print_generic_expr (dump_file
, src
, TDF_SLIM
);
274 fprintf (dump_file
, "\n");
277 gcc_assert (SA
.partition_to_pseudo
[dest
]);
279 set_location_for_edge (e
);
280 /* If a locus is provided, override the default. */
282 set_curr_insn_location (locus
);
286 var
= SSA_NAME_VAR (partition_to_var (SA
.map
, dest
));
287 src_mode
= TYPE_MODE (TREE_TYPE (src
));
288 dest_mode
= GET_MODE (SA
.partition_to_pseudo
[dest
]);
289 gcc_assert (src_mode
== TYPE_MODE (TREE_TYPE (var
)));
290 gcc_assert (!REG_P (SA
.partition_to_pseudo
[dest
])
291 || dest_mode
== promote_decl_mode (var
, &unsignedp
));
293 if (src_mode
!= dest_mode
)
295 x
= expand_expr (src
, NULL
, src_mode
, EXPAND_NORMAL
);
296 x
= convert_modes (dest_mode
, src_mode
, x
, unsignedp
);
298 else if (src_mode
== BLKmode
)
300 x
= SA
.partition_to_pseudo
[dest
];
301 store_expr (src
, x
, 0, false);
304 x
= expand_expr (src
, SA
.partition_to_pseudo
[dest
],
305 dest_mode
, EXPAND_NORMAL
);
307 if (x
!= SA
.partition_to_pseudo
[dest
])
308 emit_move_insn (SA
.partition_to_pseudo
[dest
], x
);
312 insert_insn_on_edge (seq
, e
);
315 /* Insert a copy instruction from RTL expression SRC to partition DEST
319 insert_rtx_to_part_on_edge (edge e
, int dest
, rtx src
, int unsignedsrcp
,
320 source_location locus
)
323 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
326 "Inserting a temp copy on edge BB%d->BB%d : PART.%d = ",
328 e
->dest
->index
, dest
);
329 print_simple_rtl (dump_file
, src
);
330 fprintf (dump_file
, "\n");
333 gcc_assert (SA
.partition_to_pseudo
[dest
]);
335 set_location_for_edge (e
);
336 /* If a locus is provided, override the default. */
338 set_curr_insn_location (locus
);
340 /* We give the destination as sizeexp in case src/dest are BLKmode
341 mems. Usually we give the source. As we result from SSA names
342 the left and right size should be the same (and no WITH_SIZE_EXPR
343 involved), so it doesn't matter. */
344 seq
= emit_partition_copy (SA
.partition_to_pseudo
[dest
],
346 partition_to_var (SA
.map
, dest
));
348 insert_insn_on_edge (seq
, e
);
351 /* Insert a copy instruction from partition SRC to RTL lvalue DEST
355 insert_part_to_rtx_on_edge (edge e
, rtx dest
, int src
, source_location locus
)
359 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
362 "Inserting a temp copy on edge BB%d->BB%d : ",
365 print_simple_rtl (dump_file
, dest
);
366 fprintf (dump_file
, "= PART.%d\n", src
);
369 gcc_assert (SA
.partition_to_pseudo
[src
]);
371 set_location_for_edge (e
);
372 /* If a locus is provided, override the default. */
374 set_curr_insn_location (locus
);
376 var
= partition_to_var (SA
.map
, src
);
377 seq
= emit_partition_copy (dest
,
378 SA
.partition_to_pseudo
[src
],
379 TYPE_UNSIGNED (TREE_TYPE (var
)),
382 insert_insn_on_edge (seq
, e
);
386 /* Create an elimination graph with SIZE nodes and associated data
390 new_elim_graph (int size
)
392 elim_graph g
= (elim_graph
) xmalloc (sizeof (struct _elim_graph
));
394 g
->nodes
.create (30);
395 g
->const_dests
.create (20);
396 g
->const_copies
.create (20);
397 g
->copy_locus
.create (10);
398 g
->edge_list
.create (20);
399 g
->edge_locus
.create (10);
400 g
->stack
.create (30);
402 g
->visited
= sbitmap_alloc (size
);
408 /* Empty elimination graph G. */
411 clear_elim_graph (elim_graph g
)
413 g
->nodes
.truncate (0);
414 g
->edge_list
.truncate (0);
415 g
->edge_locus
.truncate (0);
419 /* Delete elimination graph G. */
422 delete_elim_graph (elim_graph g
)
424 sbitmap_free (g
->visited
);
426 g
->edge_list
.release ();
427 g
->const_copies
.release ();
428 g
->const_dests
.release ();
430 g
->copy_locus
.release ();
431 g
->edge_locus
.release ();
437 /* Return the number of nodes in graph G. */
440 elim_graph_size (elim_graph g
)
442 return g
->nodes
.length ();
446 /* Add NODE to graph G, if it doesn't exist already. */
449 elim_graph_add_node (elim_graph g
, int node
)
454 FOR_EACH_VEC_ELT (g
->nodes
, x
, t
)
457 g
->nodes
.safe_push (node
);
461 /* Add the edge PRED->SUCC to graph G. */
464 elim_graph_add_edge (elim_graph g
, int pred
, int succ
, source_location locus
)
466 g
->edge_list
.safe_push (pred
);
467 g
->edge_list
.safe_push (succ
);
468 g
->edge_locus
.safe_push (locus
);
472 /* Remove an edge from graph G for which NODE is the predecessor, and
473 return the successor node. -1 is returned if there is no such edge. */
476 elim_graph_remove_succ_edge (elim_graph g
, int node
, source_location
*locus
)
480 for (x
= 0; x
< g
->edge_list
.length (); x
+= 2)
481 if (g
->edge_list
[x
] == node
)
483 g
->edge_list
[x
] = -1;
484 y
= g
->edge_list
[x
+ 1];
485 g
->edge_list
[x
+ 1] = -1;
486 *locus
= g
->edge_locus
[x
/ 2];
487 g
->edge_locus
[x
/ 2] = UNKNOWN_LOCATION
;
490 *locus
= UNKNOWN_LOCATION
;
495 /* Find all the nodes in GRAPH which are successors to NODE in the
496 edge list. VAR will hold the partition number found. CODE is the
497 code fragment executed for every node found. */
499 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, LOCUS, CODE) \
503 for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \
505 y_ = (GRAPH)->edge_list[x_]; \
508 (void) ((VAR) = (GRAPH)->edge_list[x_ + 1]); \
509 (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \
515 /* Find all the nodes which are predecessors of NODE in the edge list for
516 GRAPH. VAR will hold the partition number found. CODE is the
517 code fragment executed for every node found. */
519 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, LOCUS, CODE) \
523 for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \
525 y_ = (GRAPH)->edge_list[x_ + 1]; \
528 (void) ((VAR) = (GRAPH)->edge_list[x_]); \
529 (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \
535 /* Add T to elimination graph G. */
538 eliminate_name (elim_graph g
, int T
)
540 elim_graph_add_node (g
, T
);
544 /* Build elimination graph G for basic block BB on incoming PHI edge
548 eliminate_build (elim_graph g
)
552 gimple_stmt_iterator gsi
;
554 clear_elim_graph (g
);
556 for (gsi
= gsi_start_phis (g
->e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
558 gimple phi
= gsi_stmt (gsi
);
559 source_location locus
;
561 p0
= var_to_partition (g
->map
, gimple_phi_result (phi
));
562 /* Ignore results which are not in partitions. */
563 if (p0
== NO_PARTITION
)
566 Ti
= PHI_ARG_DEF (phi
, g
->e
->dest_idx
);
567 locus
= gimple_phi_arg_location_from_edge (phi
, g
->e
);
569 /* If this argument is a constant, or a SSA_NAME which is being
570 left in SSA form, just queue a copy to be emitted on this
572 if (!phi_ssa_name_p (Ti
)
573 || (TREE_CODE (Ti
) == SSA_NAME
574 && var_to_partition (g
->map
, Ti
) == NO_PARTITION
))
576 /* Save constant copies until all other copies have been emitted
578 g
->const_dests
.safe_push (p0
);
579 g
->const_copies
.safe_push (Ti
);
580 g
->copy_locus
.safe_push (locus
);
584 pi
= var_to_partition (g
->map
, Ti
);
587 eliminate_name (g
, p0
);
588 eliminate_name (g
, pi
);
589 elim_graph_add_edge (g
, p0
, pi
, locus
);
596 /* Push successors of T onto the elimination stack for G. */
599 elim_forward (elim_graph g
, int T
)
602 source_location locus
;
604 bitmap_set_bit (g
->visited
, T
);
605 FOR_EACH_ELIM_GRAPH_SUCC (g
, T
, S
, locus
,
607 if (!bitmap_bit_p (g
->visited
, S
))
610 g
->stack
.safe_push (T
);
614 /* Return 1 if there unvisited predecessors of T in graph G. */
617 elim_unvisited_predecessor (elim_graph g
, int T
)
620 source_location locus
;
622 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
624 if (!bitmap_bit_p (g
->visited
, P
))
630 /* Process predecessors first, and insert a copy. */
633 elim_backward (elim_graph g
, int T
)
636 source_location locus
;
638 bitmap_set_bit (g
->visited
, T
);
639 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
641 if (!bitmap_bit_p (g
->visited
, P
))
643 elim_backward (g
, P
);
644 insert_partition_copy_on_edge (g
->e
, P
, T
, locus
);
649 /* Allocate a new pseudo register usable for storing values sitting
650 in NAME (a decl or SSA name), i.e. with matching mode and attributes. */
653 get_temp_reg (tree name
)
655 tree var
= TREE_CODE (name
) == SSA_NAME
? SSA_NAME_VAR (name
) : name
;
656 tree type
= TREE_TYPE (var
);
658 enum machine_mode reg_mode
= promote_decl_mode (var
, &unsignedp
);
659 rtx x
= gen_reg_rtx (reg_mode
);
660 if (POINTER_TYPE_P (type
))
661 mark_reg_pointer (x
, TYPE_ALIGN (TREE_TYPE (TREE_TYPE (var
))));
665 /* Insert required copies for T in graph G. Check for a strongly connected
666 region, and create a temporary to break the cycle if one is found. */
669 elim_create (elim_graph g
, int T
)
672 source_location locus
;
674 if (elim_unvisited_predecessor (g
, T
))
676 tree var
= partition_to_var (g
->map
, T
);
677 rtx U
= get_temp_reg (var
);
678 int unsignedsrcp
= TYPE_UNSIGNED (TREE_TYPE (var
));
680 insert_part_to_rtx_on_edge (g
->e
, U
, T
, UNKNOWN_LOCATION
);
681 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
, locus
,
683 if (!bitmap_bit_p (g
->visited
, P
))
685 elim_backward (g
, P
);
686 insert_rtx_to_part_on_edge (g
->e
, P
, U
, unsignedsrcp
, locus
);
692 S
= elim_graph_remove_succ_edge (g
, T
, &locus
);
695 bitmap_set_bit (g
->visited
, T
);
696 insert_partition_copy_on_edge (g
->e
, T
, S
, locus
);
702 /* Eliminate all the phi nodes on edge E in graph G. */
705 eliminate_phi (edge e
, elim_graph g
)
709 gcc_assert (g
->const_copies
.length () == 0);
710 gcc_assert (g
->copy_locus
.length () == 0);
712 /* Abnormal edges already have everything coalesced. */
713 if (e
->flags
& EDGE_ABNORMAL
)
720 if (elim_graph_size (g
) != 0)
724 bitmap_clear (g
->visited
);
725 g
->stack
.truncate (0);
727 FOR_EACH_VEC_ELT (g
->nodes
, x
, part
)
729 if (!bitmap_bit_p (g
->visited
, part
))
730 elim_forward (g
, part
);
733 bitmap_clear (g
->visited
);
734 while (g
->stack
.length () > 0)
737 if (!bitmap_bit_p (g
->visited
, x
))
742 /* If there are any pending constant copies, issue them now. */
743 while (g
->const_copies
.length () > 0)
747 source_location locus
;
749 src
= g
->const_copies
.pop ();
750 dest
= g
->const_dests
.pop ();
751 locus
= g
->copy_locus
.pop ();
752 insert_value_copy_on_edge (e
, dest
, src
, locus
);
757 /* Remove each argument from PHI. If an arg was the last use of an SSA_NAME,
758 check to see if this allows another PHI node to be removed. */
761 remove_gimple_phi_args (gimple phi
)
766 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
768 fprintf (dump_file
, "Removing Dead PHI definition: ");
769 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
772 FOR_EACH_PHI_ARG (arg_p
, phi
, iter
, SSA_OP_USE
)
774 tree arg
= USE_FROM_PTR (arg_p
);
775 if (TREE_CODE (arg
) == SSA_NAME
)
777 /* Remove the reference to the existing argument. */
778 SET_USE (arg_p
, NULL_TREE
);
779 if (has_zero_uses (arg
))
782 gimple_stmt_iterator gsi
;
784 stmt
= SSA_NAME_DEF_STMT (arg
);
786 /* Also remove the def if it is a PHI node. */
787 if (gimple_code (stmt
) == GIMPLE_PHI
)
789 remove_gimple_phi_args (stmt
);
790 gsi
= gsi_for_stmt (stmt
);
791 remove_phi_node (&gsi
, true);
799 /* Remove any PHI node which is a virtual PHI, or a PHI with no uses. */
802 eliminate_useless_phis (void)
805 gimple_stmt_iterator gsi
;
810 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); )
812 gimple phi
= gsi_stmt (gsi
);
813 result
= gimple_phi_result (phi
);
814 if (virtual_operand_p (result
))
816 #ifdef ENABLE_CHECKING
818 /* There should be no arguments which are not virtual, or the
819 results will be incorrect. */
820 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
822 tree arg
= PHI_ARG_DEF (phi
, i
);
823 if (TREE_CODE (arg
) == SSA_NAME
824 && !virtual_operand_p (arg
))
826 fprintf (stderr
, "Argument of PHI is not virtual (");
827 print_generic_expr (stderr
, arg
, TDF_SLIM
);
828 fprintf (stderr
, "), but the result is :");
829 print_gimple_stmt (stderr
, phi
, 0, TDF_SLIM
);
830 internal_error ("SSA corruption");
834 remove_phi_node (&gsi
, true);
838 /* Also remove real PHIs with no uses. */
839 if (has_zero_uses (result
))
841 remove_gimple_phi_args (phi
);
842 remove_phi_node (&gsi
, true);
852 /* This function will rewrite the current program using the variable mapping
853 found in MAP. If the replacement vector VALUES is provided, any
854 occurrences of partitions with non-null entries in the vector will be
855 replaced with the expression in the vector instead of its mapped
859 rewrite_trees (var_map map ATTRIBUTE_UNUSED
)
861 #ifdef ENABLE_CHECKING
863 /* Search for PHIs where the destination has no partition, but one
864 or more arguments has a partition. This should not happen and can
865 create incorrect code. */
868 gimple_stmt_iterator gsi
;
869 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
871 gimple phi
= gsi_stmt (gsi
);
872 tree T0
= var_to_partition_to_var (map
, gimple_phi_result (phi
));
876 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
878 tree arg
= PHI_ARG_DEF (phi
, i
);
880 if (TREE_CODE (arg
) == SSA_NAME
881 && var_to_partition (map
, arg
) != NO_PARTITION
)
883 fprintf (stderr
, "Argument of PHI is in a partition :(");
884 print_generic_expr (stderr
, arg
, TDF_SLIM
);
885 fprintf (stderr
, "), but the result is not :");
886 print_gimple_stmt (stderr
, phi
, 0, TDF_SLIM
);
887 internal_error ("SSA corruption");
896 /* Given the out-of-ssa info object SA (with prepared partitions)
897 eliminate all phi nodes in all basic blocks. Afterwards no
898 basic block will have phi nodes anymore and there are possibly
899 some RTL instructions inserted on edges. */
902 expand_phi_nodes (struct ssaexpand
*sa
)
905 elim_graph g
= new_elim_graph (sa
->map
->num_partitions
);
908 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
, EXIT_BLOCK_PTR
, next_bb
)
909 if (!gimple_seq_empty_p (phi_nodes (bb
)))
913 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
914 eliminate_phi (e
, g
);
915 set_phi_nodes (bb
, NULL
);
916 /* We can't redirect EH edges in RTL land, so we need to do this
917 here. Redirection happens only when splitting is necessary,
918 which it is only for critical edges, normally. For EH edges
919 it might also be necessary when the successor has more than
920 one predecessor. In that case the edge is either required to
921 be fallthru (which EH edges aren't), or the predecessor needs
922 to end with a jump (which again, isn't the case with EH edges).
923 Hence, split all EH edges on which we inserted instructions
924 and whose successor has multiple predecessors. */
925 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
927 if (e
->insns
.r
&& (e
->flags
& EDGE_EH
)
928 && !single_pred_p (e
->dest
))
930 rtx insns
= e
->insns
.r
;
932 e
->insns
.r
= NULL_RTX
;
934 single_pred_edge (bb
)->insns
.r
= insns
;
941 delete_elim_graph (g
);
945 /* Remove the ssa-names in the current function and translate them into normal
946 compiler variables. PERFORM_TER is true if Temporary Expression Replacement
947 should also be used. */
950 remove_ssa_form (bool perform_ter
, struct ssaexpand
*sa
)
952 bitmap values
= NULL
;
956 map
= coalesce_ssa_name ();
958 /* Return to viewing the variable list as just all reference variables after
959 coalescing has been performed. */
960 partition_view_normal (map
, false);
962 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
964 fprintf (dump_file
, "After Coalescing:\n");
965 dump_var_map (dump_file
, map
);
970 values
= find_replaceable_exprs (map
);
971 if (values
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
972 dump_replaceable_exprs (dump_file
, values
);
979 sa
->partition_has_default_def
= BITMAP_ALLOC (NULL
);
980 for (i
= 1; i
< num_ssa_names
; i
++)
982 tree t
= ssa_name (i
);
983 if (t
&& SSA_NAME_IS_DEFAULT_DEF (t
))
985 int p
= var_to_partition (map
, t
);
986 if (p
!= NO_PARTITION
)
987 bitmap_set_bit (sa
->partition_has_default_def
, p
);
993 /* If not already done so for basic block BB, assign increasing uids
994 to each of its instructions. */
997 maybe_renumber_stmts_bb (basic_block bb
)
1000 gimple_stmt_iterator gsi
;
1005 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1007 gimple stmt
= gsi_stmt (gsi
);
1008 gimple_set_uid (stmt
, i
);
1014 /* Return true if we can determine that the SSA_NAMEs RESULT (a result
1015 of a PHI node) and ARG (one of its arguments) conflict. Return false
1016 otherwise, also when we simply aren't sure. */
1019 trivially_conflicts_p (basic_block bb
, tree result
, tree arg
)
1022 imm_use_iterator imm_iter
;
1023 gimple defa
= SSA_NAME_DEF_STMT (arg
);
1025 /* If ARG isn't defined in the same block it's too complicated for
1027 if (gimple_bb (defa
) != bb
)
1030 FOR_EACH_IMM_USE_FAST (use
, imm_iter
, result
)
1032 gimple use_stmt
= USE_STMT (use
);
1033 if (is_gimple_debug (use_stmt
))
1035 /* Now, if there's a use of RESULT that lies outside this basic block,
1036 then there surely is a conflict with ARG. */
1037 if (gimple_bb (use_stmt
) != bb
)
1039 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
1041 /* The use now is in a real stmt of BB, so if ARG was defined
1042 in a PHI node (like RESULT) both conflict. */
1043 if (gimple_code (defa
) == GIMPLE_PHI
)
1045 maybe_renumber_stmts_bb (bb
);
1046 /* If the use of RESULT occurs after the definition of ARG,
1047 the two conflict too. */
1048 if (gimple_uid (defa
) < gimple_uid (use_stmt
))
1056 /* Search every PHI node for arguments associated with backedges which
1057 we can trivially determine will need a copy (the argument is either
1058 not an SSA_NAME or the argument has a different underlying variable
1059 than the PHI result).
1061 Insert a copy from the PHI argument to a new destination at the
1062 end of the block with the backedge to the top of the loop. Update
1063 the PHI argument to reference this new destination. */
1066 insert_backedge_copies (void)
1069 gimple_stmt_iterator gsi
;
1071 mark_dfs_back_edges ();
1075 /* Mark block as possibly needing calculation of UIDs. */
1078 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1080 gimple phi
= gsi_stmt (gsi
);
1081 tree result
= gimple_phi_result (phi
);
1084 if (virtual_operand_p (result
))
1087 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1089 tree arg
= gimple_phi_arg_def (phi
, i
);
1090 edge e
= gimple_phi_arg_edge (phi
, i
);
1092 /* If the argument is not an SSA_NAME, then we will need a
1093 constant initialization. If the argument is an SSA_NAME with
1094 a different underlying variable then a copy statement will be
1096 if ((e
->flags
& EDGE_DFS_BACK
)
1097 && (TREE_CODE (arg
) != SSA_NAME
1098 || SSA_NAME_VAR (arg
) != SSA_NAME_VAR (result
)
1099 || trivially_conflicts_p (bb
, result
, arg
)))
1102 gimple stmt
, last
= NULL
;
1103 gimple_stmt_iterator gsi2
;
1105 gsi2
= gsi_last_bb (gimple_phi_arg_edge (phi
, i
)->src
);
1106 if (!gsi_end_p (gsi2
))
1107 last
= gsi_stmt (gsi2
);
1109 /* In theory the only way we ought to get back to the
1110 start of a loop should be with a COND_EXPR or GOTO_EXPR.
1111 However, better safe than sorry.
1112 If the block ends with a control statement or
1113 something that might throw, then we have to
1114 insert this assignment before the last
1115 statement. Else insert it after the last statement. */
1116 if (last
&& stmt_ends_bb_p (last
))
1118 /* If the last statement in the block is the definition
1119 site of the PHI argument, then we can't insert
1120 anything after it. */
1121 if (TREE_CODE (arg
) == SSA_NAME
1122 && SSA_NAME_DEF_STMT (arg
) == last
)
1126 /* Create a new instance of the underlying variable of the
1128 name
= copy_ssa_name (result
, NULL
);
1129 stmt
= gimple_build_assign (name
,
1130 gimple_phi_arg_def (phi
, i
));
1132 /* copy location if present. */
1133 if (gimple_phi_arg_has_location (phi
, i
))
1134 gimple_set_location (stmt
,
1135 gimple_phi_arg_location (phi
, i
));
1137 /* Insert the new statement into the block and update
1139 if (last
&& stmt_ends_bb_p (last
))
1140 gsi_insert_before (&gsi2
, stmt
, GSI_NEW_STMT
);
1142 gsi_insert_after (&gsi2
, stmt
, GSI_NEW_STMT
);
1143 SET_PHI_ARG_DEF (phi
, i
, name
);
1148 /* Unmark this block again. */
1153 /* Free all memory associated with going out of SSA form. SA is
1154 the outof-SSA info object. */
1157 finish_out_of_ssa (struct ssaexpand
*sa
)
1159 free (sa
->partition_to_pseudo
);
1161 BITMAP_FREE (sa
->values
);
1162 delete_var_map (sa
->map
);
1163 BITMAP_FREE (sa
->partition_has_default_def
);
1164 memset (sa
, 0, sizeof *sa
);
1167 /* Take the current function out of SSA form, translating PHIs as described in
1168 R. Morgan, ``Building an Optimizing Compiler'',
1169 Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */
1172 rewrite_out_of_ssa (struct ssaexpand
*sa
)
1174 /* If elimination of a PHI requires inserting a copy on a backedge,
1175 then we will have to split the backedge which has numerous
1176 undesirable performance effects.
1178 A significant number of such cases can be handled here by inserting
1179 copies into the loop itself. */
1180 insert_backedge_copies ();
1183 /* Eliminate PHIs which are of no use, such as virtual or dead phis. */
1184 eliminate_useless_phis ();
1186 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1187 gimple_dump_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);
1189 remove_ssa_form (flag_tree_ter
, sa
);
1191 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1192 gimple_dump_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);