1 /* Convert a program in SSA form into Normal form.
2 Copyright (C) 2004, 2005, 2006, 2007 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 "diagnostic.h"
30 #include "tree-flow.h"
32 #include "tree-dump.h"
33 #include "tree-ssa-live.h"
34 #include "tree-pass.h"
38 /* Used to hold all the components required to do SSA PHI elimination.
39 The node and pred/succ list is a simple linear list of nodes and
40 edges represented as pairs of nodes.
42 The predecessor and successor list: Nodes are entered in pairs, where
43 [0] ->PRED, [1]->SUCC. All the even indexes in the array represent
44 predecessors, all the odd elements are successors.
47 When implemented as bitmaps, very large programs SSA->Normal times were
48 being dominated by clearing the interference graph.
50 Typically this list of edges is extremely small since it only includes
51 PHI results and uses from a single edge which have not coalesced with
52 each other. This means that no virtual PHI nodes are included, and
53 empirical evidence suggests that the number of edges rarely exceed
54 3, and in a bootstrap of GCC, the maximum size encountered was 7.
55 This also limits the number of possible nodes that are involved to
56 rarely more than 6, and in the bootstrap of gcc, the maximum number
57 of nodes encountered was 12. */
59 typedef struct _elim_graph
{
60 /* Size of the elimination vectors. */
63 /* List of nodes in the elimination graph. */
64 VEC(tree
,heap
) *nodes
;
66 /* The predecessor and successor edge list. */
67 VEC(int,heap
) *edge_list
;
72 /* Stack for visited nodes. */
75 /* The variable partition map. */
78 /* Edge being eliminated by this graph. */
81 /* List of constant copies to emit. These are pushed on in pairs. */
82 VEC(tree
,heap
) *const_copies
;
86 /* Create a temporary variable based on the type of variable T. Use T's name
93 const char *name
= NULL
;
96 if (TREE_CODE (t
) == SSA_NAME
)
99 gcc_assert (TREE_CODE (t
) == VAR_DECL
|| TREE_CODE (t
) == PARM_DECL
);
101 type
= TREE_TYPE (t
);
104 name
= IDENTIFIER_POINTER (tmp
);
108 tmp
= create_tmp_var (type
, name
);
110 if (DECL_DEBUG_EXPR_IS_FROM (t
) && DECL_DEBUG_EXPR (t
))
112 SET_DECL_DEBUG_EXPR (tmp
, DECL_DEBUG_EXPR (t
));
113 DECL_DEBUG_EXPR_IS_FROM (tmp
) = 1;
115 else if (!DECL_IGNORED_P (t
))
117 SET_DECL_DEBUG_EXPR (tmp
, t
);
118 DECL_DEBUG_EXPR_IS_FROM (tmp
) = 1;
120 DECL_ARTIFICIAL (tmp
) = DECL_ARTIFICIAL (t
);
121 DECL_IGNORED_P (tmp
) = DECL_IGNORED_P (t
);
122 add_referenced_var (tmp
);
124 /* add_referenced_var will create the annotation and set up some
125 of the flags in the annotation. However, some flags we need to
126 inherit from our original variable. */
127 set_symbol_mem_tag (tmp
, symbol_mem_tag (t
));
128 if (is_call_clobbered (t
))
129 mark_call_clobbered (tmp
, var_ann (t
)->escape_mask
);
135 /* This helper function fill insert a copy from a constant or variable SRC to
136 variable DEST on edge E. */
139 insert_copy_on_edge (edge e
, tree dest
, tree src
)
143 copy
= build_gimple_modify_stmt (dest
, src
);
146 if (TREE_CODE (src
) == ADDR_EXPR
)
147 src
= TREE_OPERAND (src
, 0);
148 if (TREE_CODE (src
) == VAR_DECL
|| TREE_CODE (src
) == PARM_DECL
)
151 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
154 "Inserting a copy on edge BB%d->BB%d :",
157 print_generic_expr (dump_file
, copy
, dump_flags
);
158 fprintf (dump_file
, "\n");
161 bsi_insert_on_edge (e
, copy
);
165 /* Create an elimination graph with SIZE nodes and associated data
169 new_elim_graph (int size
)
171 elim_graph g
= (elim_graph
) xmalloc (sizeof (struct _elim_graph
));
173 g
->nodes
= VEC_alloc (tree
, heap
, 30);
174 g
->const_copies
= VEC_alloc (tree
, heap
, 20);
175 g
->edge_list
= VEC_alloc (int, heap
, 20);
176 g
->stack
= VEC_alloc (int, heap
, 30);
178 g
->visited
= sbitmap_alloc (size
);
184 /* Empty elimination graph G. */
187 clear_elim_graph (elim_graph g
)
189 VEC_truncate (tree
, g
->nodes
, 0);
190 VEC_truncate (int, g
->edge_list
, 0);
194 /* Delete elimination graph G. */
197 delete_elim_graph (elim_graph g
)
199 sbitmap_free (g
->visited
);
200 VEC_free (int, heap
, g
->stack
);
201 VEC_free (int, heap
, g
->edge_list
);
202 VEC_free (tree
, heap
, g
->const_copies
);
203 VEC_free (tree
, heap
, g
->nodes
);
208 /* Return the number of nodes in graph G. */
211 elim_graph_size (elim_graph g
)
213 return VEC_length (tree
, g
->nodes
);
217 /* Add NODE to graph G, if it doesn't exist already. */
220 elim_graph_add_node (elim_graph g
, tree node
)
225 for (x
= 0; VEC_iterate (tree
, g
->nodes
, x
, t
); x
++)
228 VEC_safe_push (tree
, heap
, g
->nodes
, node
);
232 /* Add the edge PRED->SUCC to graph G. */
235 elim_graph_add_edge (elim_graph g
, int pred
, int succ
)
237 VEC_safe_push (int, heap
, g
->edge_list
, pred
);
238 VEC_safe_push (int, heap
, g
->edge_list
, succ
);
242 /* Remove an edge from graph G for which NODE is the predecessor, and
243 return the successor node. -1 is returned if there is no such edge. */
246 elim_graph_remove_succ_edge (elim_graph g
, int node
)
250 for (x
= 0; x
< VEC_length (int, g
->edge_list
); x
+= 2)
251 if (VEC_index (int, g
->edge_list
, x
) == node
)
253 VEC_replace (int, g
->edge_list
, x
, -1);
254 y
= VEC_index (int, g
->edge_list
, x
+ 1);
255 VEC_replace (int, g
->edge_list
, x
+ 1, -1);
262 /* Find all the nodes in GRAPH which are successors to NODE in the
263 edge list. VAR will hold the partition number found. CODE is the
264 code fragment executed for every node found. */
266 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, CODE) \
270 for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2) \
272 y_ = VEC_index (int, (GRAPH)->edge_list, x_); \
275 (VAR) = VEC_index (int, (GRAPH)->edge_list, x_ + 1); \
281 /* Find all the nodes which are predecessors of NODE in the edge list for
282 GRAPH. VAR will hold the partition number found. CODE is the
283 code fragment executed for every node found. */
285 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, CODE) \
289 for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2) \
291 y_ = VEC_index (int, (GRAPH)->edge_list, x_ + 1); \
294 (VAR) = VEC_index (int, (GRAPH)->edge_list, x_); \
300 /* Add T to elimination graph G. */
303 eliminate_name (elim_graph g
, tree T
)
305 elim_graph_add_node (g
, T
);
309 /* Build elimination graph G for basic block BB on incoming PHI edge
313 eliminate_build (elim_graph g
, basic_block B
)
319 clear_elim_graph (g
);
321 for (phi
= phi_nodes (B
); phi
; phi
= PHI_CHAIN (phi
))
323 T0
= var_to_partition_to_var (g
->map
, PHI_RESULT (phi
));
325 /* Ignore results which are not in partitions. */
329 Ti
= PHI_ARG_DEF (phi
, g
->e
->dest_idx
);
331 /* If this argument is a constant, or a SSA_NAME which is being
332 left in SSA form, just queue a copy to be emitted on this
334 if (!phi_ssa_name_p (Ti
)
335 || (TREE_CODE (Ti
) == SSA_NAME
336 && var_to_partition (g
->map
, Ti
) == NO_PARTITION
))
338 /* Save constant copies until all other copies have been emitted
340 VEC_safe_push (tree
, heap
, g
->const_copies
, T0
);
341 VEC_safe_push (tree
, heap
, g
->const_copies
, Ti
);
345 Ti
= var_to_partition_to_var (g
->map
, Ti
);
348 eliminate_name (g
, T0
);
349 eliminate_name (g
, Ti
);
350 p0
= var_to_partition (g
->map
, T0
);
351 pi
= var_to_partition (g
->map
, Ti
);
352 elim_graph_add_edge (g
, p0
, pi
);
359 /* Push successors of T onto the elimination stack for G. */
362 elim_forward (elim_graph g
, int T
)
365 SET_BIT (g
->visited
, T
);
366 FOR_EACH_ELIM_GRAPH_SUCC (g
, T
, S
,
368 if (!TEST_BIT (g
->visited
, S
))
371 VEC_safe_push (int, heap
, g
->stack
, T
);
375 /* Return 1 if there unvisited predecessors of T in graph G. */
378 elim_unvisited_predecessor (elim_graph g
, int T
)
381 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
,
383 if (!TEST_BIT (g
->visited
, P
))
389 /* Process predecessors first, and insert a copy. */
392 elim_backward (elim_graph g
, int T
)
395 SET_BIT (g
->visited
, T
);
396 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
,
398 if (!TEST_BIT (g
->visited
, P
))
400 elim_backward (g
, P
);
401 insert_copy_on_edge (g
->e
,
402 partition_to_var (g
->map
, P
),
403 partition_to_var (g
->map
, T
));
408 /* Insert required copies for T in graph G. Check for a strongly connected
409 region, and create a temporary to break the cycle if one is found. */
412 elim_create (elim_graph g
, int T
)
417 if (elim_unvisited_predecessor (g
, T
))
419 U
= create_temp (partition_to_var (g
->map
, T
));
420 insert_copy_on_edge (g
->e
, U
, partition_to_var (g
->map
, T
));
421 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
,
423 if (!TEST_BIT (g
->visited
, P
))
425 elim_backward (g
, P
);
426 insert_copy_on_edge (g
->e
, partition_to_var (g
->map
, P
), U
);
432 S
= elim_graph_remove_succ_edge (g
, T
);
435 SET_BIT (g
->visited
, T
);
436 insert_copy_on_edge (g
->e
,
437 partition_to_var (g
->map
, T
),
438 partition_to_var (g
->map
, S
));
445 /* Eliminate all the phi nodes on edge E in graph G. */
448 eliminate_phi (edge e
, elim_graph g
)
451 basic_block B
= e
->dest
;
453 gcc_assert (VEC_length (tree
, g
->const_copies
) == 0);
455 /* Abnormal edges already have everything coalesced. */
456 if (e
->flags
& EDGE_ABNORMAL
)
461 eliminate_build (g
, B
);
463 if (elim_graph_size (g
) != 0)
467 sbitmap_zero (g
->visited
);
468 VEC_truncate (int, g
->stack
, 0);
470 for (x
= 0; VEC_iterate (tree
, g
->nodes
, x
, var
); x
++)
472 int p
= var_to_partition (g
->map
, var
);
473 if (!TEST_BIT (g
->visited
, p
))
477 sbitmap_zero (g
->visited
);
478 while (VEC_length (int, g
->stack
) > 0)
480 x
= VEC_pop (int, g
->stack
);
481 if (!TEST_BIT (g
->visited
, x
))
486 /* If there are any pending constant copies, issue them now. */
487 while (VEC_length (tree
, g
->const_copies
) > 0)
490 src
= VEC_pop (tree
, g
->const_copies
);
491 dest
= VEC_pop (tree
, g
->const_copies
);
492 insert_copy_on_edge (e
, dest
, src
);
497 /* Take the ssa-name var_map MAP, and assign real variables to each
501 assign_vars (var_map map
)
507 num
= num_var_partitions (map
);
508 for (x
= 0; x
< num
; x
++)
510 var
= partition_to_var (map
, x
);
511 if (TREE_CODE (var
) != SSA_NAME
)
514 /* It must already be coalesced. */
515 gcc_assert (ann
->out_of_ssa_tag
== 1);
516 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
518 fprintf (dump_file
, "partition %d already has variable ", x
);
519 print_generic_expr (dump_file
, var
, TDF_SLIM
);
520 fprintf (dump_file
, " assigned to it.\n");
525 root
= SSA_NAME_VAR (var
);
526 ann
= var_ann (root
);
527 /* If ROOT is already associated, create a new one. */
528 if (ann
->out_of_ssa_tag
)
530 root
= create_temp (root
);
531 ann
= var_ann (root
);
533 /* ROOT has not been coalesced yet, so use it. */
534 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
536 fprintf (dump_file
, "Partition %d is assigned to var ", x
);
537 print_generic_stmt (dump_file
, root
, TDF_SLIM
);
539 change_partition_var (map
, root
, x
);
545 /* Replace use operand P with whatever variable it has been rewritten to based
546 on the partitions in MAP. EXPR is an optional expression vector over SSA
547 versions which is used to replace P with an expression instead of a variable.
548 If the stmt is changed, return true. */
551 replace_use_variable (var_map map
, use_operand_p p
, tree
*expr
)
554 tree var
= USE_FROM_PTR (p
);
556 /* Check if we are replacing this variable with an expression. */
559 int version
= SSA_NAME_VERSION (var
);
562 tree new_expr
= GIMPLE_STMT_OPERAND (expr
[version
], 1);
563 SET_USE (p
, new_expr
);
565 /* Clear the stmt's RHS, or GC might bite us. */
566 GIMPLE_STMT_OPERAND (expr
[version
], 1) = NULL_TREE
;
571 new_var
= var_to_partition_to_var (map
, var
);
574 SET_USE (p
, new_var
);
575 set_is_used (new_var
);
582 /* Replace def operand DEF_P with whatever variable it has been rewritten to
583 based on the partitions in MAP. EXPR is an optional expression vector over
584 SSA versions which is used to replace DEF_P with an expression instead of a
585 variable. If the stmt is changed, return true. */
588 replace_def_variable (var_map map
, def_operand_p def_p
, tree
*expr
)
591 tree var
= DEF_FROM_PTR (def_p
);
593 /* Do nothing if we are replacing this variable with an expression. */
594 if (expr
&& expr
[SSA_NAME_VERSION (var
)])
597 new_var
= var_to_partition_to_var (map
, var
);
600 SET_DEF (def_p
, new_var
);
601 set_is_used (new_var
);
608 /* Remove any PHI node which is a virtual PHI. */
611 eliminate_virtual_phis (void)
618 for (phi
= phi_nodes (bb
); phi
; phi
= next
)
620 next
= PHI_CHAIN (phi
);
621 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi
))))
623 #ifdef ENABLE_CHECKING
625 /* There should be no arguments of this PHI which are in
626 the partition list, or we get incorrect results. */
627 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
629 tree arg
= PHI_ARG_DEF (phi
, i
);
630 if (TREE_CODE (arg
) == SSA_NAME
631 && is_gimple_reg (SSA_NAME_VAR (arg
)))
633 fprintf (stderr
, "Argument of PHI is not virtual (");
634 print_generic_expr (stderr
, arg
, TDF_SLIM
);
635 fprintf (stderr
, "), but the result is :");
636 print_generic_stmt (stderr
, phi
, TDF_SLIM
);
637 internal_error ("SSA corruption");
641 remove_phi_node (phi
, NULL_TREE
, true);
648 /* This function will rewrite the current program using the variable mapping
649 found in MAP. If the replacement vector VALUES is provided, any
650 occurrences of partitions with non-null entries in the vector will be
651 replaced with the expression in the vector instead of its mapped
655 rewrite_trees (var_map map
, tree
*values
)
659 block_stmt_iterator si
;
664 #ifdef ENABLE_CHECKING
665 /* Search for PHIs where the destination has no partition, but one
666 or more arguments has a partition. This should not happen and can
667 create incorrect code. */
671 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
673 tree T0
= var_to_partition_to_var (map
, PHI_RESULT (phi
));
677 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
679 tree arg
= PHI_ARG_DEF (phi
, i
);
681 if (TREE_CODE (arg
) == SSA_NAME
682 && var_to_partition (map
, arg
) != NO_PARTITION
)
684 fprintf (stderr
, "Argument of PHI is in a partition :(");
685 print_generic_expr (stderr
, arg
, TDF_SLIM
);
686 fprintf (stderr
, "), but the result is not :");
687 print_generic_stmt (stderr
, phi
, TDF_SLIM
);
688 internal_error ("SSA corruption");
696 /* Replace PHI nodes with any required copies. */
697 g
= new_elim_graph (map
->num_partitions
);
701 for (si
= bsi_start (bb
); !bsi_end_p (si
); )
703 tree stmt
= bsi_stmt (si
);
704 use_operand_p use_p
, copy_use_p
;
706 bool remove
= false, is_copy
= false;
711 ann
= stmt_ann (stmt
);
714 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
715 && (TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1)) == SSA_NAME
))
718 copy_use_p
= NULL_USE_OPERAND_P
;
719 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
721 if (replace_use_variable (map
, use_p
, values
))
730 def_p
= SINGLE_SSA_DEF_OPERAND (stmt
, SSA_OP_DEF
);
734 /* Mark this stmt for removal if it is the list of replaceable
736 if (values
&& values
[SSA_NAME_VERSION (DEF_FROM_PTR (def_p
))])
740 if (replace_def_variable (map
, def_p
, NULL
))
742 /* If both SSA_NAMEs coalesce to the same variable,
743 mark the now redundant copy for removal. */
746 gcc_assert (copy_use_p
!= NULL_USE_OPERAND_P
);
747 if (DEF_FROM_PTR (def_p
) == USE_FROM_PTR (copy_use_p
))
753 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, iter
, SSA_OP_DEF
)
754 if (replace_def_variable (map
, def_p
, NULL
))
757 /* Remove any stmts marked for removal. */
759 bsi_remove (&si
, true);
763 if (maybe_clean_or_replace_eh_stmt (stmt
, stmt
))
764 tree_purge_dead_eh_edges (bb
);
769 phi
= phi_nodes (bb
);
773 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
774 eliminate_phi (e
, g
);
778 delete_elim_graph (g
);
781 /* These are the local work structures used to determine the best place to
782 insert the copies that were placed on edges by the SSA->normal pass.. */
783 static VEC(edge
,heap
) *edge_leader
;
784 static VEC(tree
,heap
) *stmt_list
;
785 static bitmap leader_has_match
= NULL
;
786 static edge leader_match
= NULL
;
789 /* Pass this function to make_forwarder_block so that all the edges with
790 matching PENDING_STMT lists to 'curr_stmt_list' get redirected. E is the
791 edge to test for a match. */
794 same_stmt_list_p (edge e
)
796 return (e
->aux
== (PTR
) leader_match
) ? true : false;
800 /* Return TRUE if S1 and S2 are equivalent copies. */
803 identical_copies_p (const_tree s1
, const_tree s2
)
805 #ifdef ENABLE_CHECKING
806 gcc_assert (TREE_CODE (s1
) == GIMPLE_MODIFY_STMT
);
807 gcc_assert (TREE_CODE (s2
) == GIMPLE_MODIFY_STMT
);
808 gcc_assert (DECL_P (GIMPLE_STMT_OPERAND (s1
, 0)));
809 gcc_assert (DECL_P (GIMPLE_STMT_OPERAND (s2
, 0)));
812 if (GIMPLE_STMT_OPERAND (s1
, 0) != GIMPLE_STMT_OPERAND (s2
, 0))
815 s1
= GIMPLE_STMT_OPERAND (s1
, 1);
816 s2
= GIMPLE_STMT_OPERAND (s2
, 1);
825 /* Compare the PENDING_STMT list for edges E1 and E2. Return true if the lists
826 contain the same sequence of copies. */
829 identical_stmt_lists_p (const_edge e1
, const_edge e2
)
831 tree t1
= PENDING_STMT (e1
);
832 tree t2
= PENDING_STMT (e2
);
833 tree_stmt_iterator tsi1
, tsi2
;
835 gcc_assert (TREE_CODE (t1
) == STATEMENT_LIST
);
836 gcc_assert (TREE_CODE (t2
) == STATEMENT_LIST
);
838 for (tsi1
= tsi_start (t1
), tsi2
= tsi_start (t2
);
839 !tsi_end_p (tsi1
) && !tsi_end_p (tsi2
);
840 tsi_next (&tsi1
), tsi_next (&tsi2
))
842 if (!identical_copies_p (tsi_stmt (tsi1
), tsi_stmt (tsi2
)))
846 if (!tsi_end_p (tsi1
) || ! tsi_end_p (tsi2
))
853 /* Allocate data structures used in analyze_edges_for_bb. */
856 init_analyze_edges_for_bb (void)
858 edge_leader
= VEC_alloc (edge
, heap
, 25);
859 stmt_list
= VEC_alloc (tree
, heap
, 25);
860 leader_has_match
= BITMAP_ALLOC (NULL
);
864 /* Free data structures used in analyze_edges_for_bb. */
867 fini_analyze_edges_for_bb (void)
869 VEC_free (edge
, heap
, edge_leader
);
870 VEC_free (tree
, heap
, stmt_list
);
871 BITMAP_FREE (leader_has_match
);
875 /* Look at all the incoming edges to block BB, and decide where the best place
876 to insert the stmts on each edge are, and perform those insertions. */
879 analyze_edges_for_bb (basic_block bb
)
885 bool have_opportunity
;
886 block_stmt_iterator bsi
;
888 edge single_edge
= NULL
;
894 /* Blocks which contain at least one abnormal edge cannot use
895 make_forwarder_block. Look for these blocks, and commit any PENDING_STMTs
896 found on edges in these block. */
897 have_opportunity
= true;
898 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
899 if (e
->flags
& EDGE_ABNORMAL
)
901 have_opportunity
= false;
905 if (!have_opportunity
)
907 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
908 if (PENDING_STMT (e
))
909 bsi_commit_one_edge_insert (e
, NULL
);
913 /* Find out how many edges there are with interesting pending stmts on them.
914 Commit the stmts on edges we are not interested in. */
915 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
917 if (PENDING_STMT (e
))
919 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
920 if (e
->flags
& EDGE_FALLTHRU
)
922 bsi
= bsi_start (e
->src
);
923 if (!bsi_end_p (bsi
))
925 stmt
= bsi_stmt (bsi
);
927 gcc_assert (stmt
!= NULL_TREE
);
928 is_label
= (TREE_CODE (stmt
) == LABEL_EXPR
);
929 /* Punt if it has non-label stmts, or isn't local. */
930 if (!is_label
|| DECL_NONLOCAL (TREE_OPERAND (stmt
, 0))
933 bsi_commit_one_edge_insert (e
, NULL
);
943 /* If there aren't at least 2 edges, no sharing will happen. */
947 bsi_commit_one_edge_insert (single_edge
, NULL
);
951 /* Ensure that we have empty worklists. */
952 #ifdef ENABLE_CHECKING
953 gcc_assert (VEC_length (edge
, edge_leader
) == 0);
954 gcc_assert (VEC_length (tree
, stmt_list
) == 0);
955 gcc_assert (bitmap_empty_p (leader_has_match
));
958 /* Find the "leader" block for each set of unique stmt lists. Preference is
959 given to FALLTHRU blocks since they would need a GOTO to arrive at another
960 block. The leader edge destination is the block which all the other edges
961 with the same stmt list will be redirected to. */
962 have_opportunity
= false;
963 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
965 if (PENDING_STMT (e
))
969 /* Look for the same stmt list in edge leaders list. */
970 for (x
= 0; VEC_iterate (edge
, edge_leader
, x
, leader
); x
++)
972 if (identical_stmt_lists_p (leader
, e
))
974 /* Give this edge the same stmt list pointer. */
975 PENDING_STMT (e
) = NULL
;
977 bitmap_set_bit (leader_has_match
, x
);
978 have_opportunity
= found
= true;
983 /* If no similar stmt list, add this edge to the leader list. */
986 VEC_safe_push (edge
, heap
, edge_leader
, e
);
987 VEC_safe_push (tree
, heap
, stmt_list
, PENDING_STMT (e
));
992 /* If there are no similar lists, just issue the stmts. */
993 if (!have_opportunity
)
995 for (x
= 0; VEC_iterate (edge
, edge_leader
, x
, leader
); x
++)
996 bsi_commit_one_edge_insert (leader
, NULL
);
997 VEC_truncate (edge
, edge_leader
, 0);
998 VEC_truncate (tree
, stmt_list
, 0);
999 bitmap_clear (leader_has_match
);
1004 fprintf (dump_file
, "\nOpportunities in BB %d for stmt/block reduction:\n",
1007 /* For each common list, create a forwarding block and issue the stmt's
1009 for (x
= 0; VEC_iterate (edge
, edge_leader
, x
, leader
); x
++)
1010 if (bitmap_bit_p (leader_has_match
, x
))
1013 block_stmt_iterator bsi
;
1014 tree curr_stmt_list
;
1016 leader_match
= leader
;
1018 /* The tree_* cfg manipulation routines use the PENDING_EDGE field
1019 for various PHI manipulations, so it gets cleared when calls are
1020 made to make_forwarder_block(). So make sure the edge is clear,
1021 and use the saved stmt list. */
1022 PENDING_STMT (leader
) = NULL
;
1023 leader
->aux
= leader
;
1024 curr_stmt_list
= VEC_index (tree
, stmt_list
, x
);
1026 new_edge
= make_forwarder_block (leader
->dest
, same_stmt_list_p
,
1028 bb
= new_edge
->dest
;
1031 fprintf (dump_file
, "Splitting BB %d for Common stmt list. ",
1032 leader
->dest
->index
);
1033 fprintf (dump_file
, "Original block is now BB%d.\n", bb
->index
);
1034 print_generic_stmt (dump_file
, curr_stmt_list
, TDF_VOPS
);
1037 FOR_EACH_EDGE (e
, ei
, new_edge
->src
->preds
)
1041 fprintf (dump_file
, " Edge (%d->%d) lands here.\n",
1042 e
->src
->index
, e
->dest
->index
);
1045 bsi
= bsi_last (leader
->dest
);
1046 bsi_insert_after (&bsi
, curr_stmt_list
, BSI_NEW_STMT
);
1048 leader_match
= NULL
;
1049 /* We should never get a new block now. */
1053 PENDING_STMT (leader
) = VEC_index (tree
, stmt_list
, x
);
1054 bsi_commit_one_edge_insert (leader
, NULL
);
1058 /* Clear the working data structures. */
1059 VEC_truncate (edge
, edge_leader
, 0);
1060 VEC_truncate (tree
, stmt_list
, 0);
1061 bitmap_clear (leader_has_match
);
1065 /* This function will analyze the insertions which were performed on edges,
1066 and decide whether they should be left on that edge, or whether it is more
1067 efficient to emit some subset of them in a single block. All stmts are
1068 inserted somewhere. */
1071 perform_edge_inserts (void)
1076 fprintf(dump_file
, "Analyzing Edge Insertions.\n");
1078 /* analyze_edges_for_bb calls make_forwarder_block, which tries to
1079 incrementally update the dominator information. Since we don't
1080 need dominator information after this pass, go ahead and free the
1081 dominator information. */
1082 free_dominance_info (CDI_DOMINATORS
);
1083 free_dominance_info (CDI_POST_DOMINATORS
);
1085 /* Allocate data structures used in analyze_edges_for_bb. */
1086 init_analyze_edges_for_bb ();
1089 analyze_edges_for_bb (bb
);
1091 analyze_edges_for_bb (EXIT_BLOCK_PTR
);
1093 /* Free data structures used in analyze_edges_for_bb. */
1094 fini_analyze_edges_for_bb ();
1096 #ifdef ENABLE_CHECKING
1102 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1104 if (PENDING_STMT (e
))
1105 error (" Pending stmts not issued on PRED edge (%d, %d)\n",
1106 e
->src
->index
, e
->dest
->index
);
1108 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1110 if (PENDING_STMT (e
))
1111 error (" Pending stmts not issued on SUCC edge (%d, %d)\n",
1112 e
->src
->index
, e
->dest
->index
);
1115 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
1117 if (PENDING_STMT (e
))
1118 error (" Pending stmts not issued on ENTRY edge (%d, %d)\n",
1119 e
->src
->index
, e
->dest
->index
);
1121 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
1123 if (PENDING_STMT (e
))
1124 error (" Pending stmts not issued on EXIT edge (%d, %d)\n",
1125 e
->src
->index
, e
->dest
->index
);
1132 /* Remove the ssa-names in the current function and translate them into normal
1133 compiler variables. PERFORM_TER is true if Temporary Expression Replacement
1134 should also be used. */
1137 remove_ssa_form (bool perform_ter
)
1141 tree
*values
= NULL
;
1144 map
= coalesce_ssa_name ();
1146 /* Return to viewing the variable list as just all reference variables after
1147 coalescing has been performed. */
1148 partition_view_normal (map
, false);
1150 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1152 fprintf (dump_file
, "After Coalescing:\n");
1153 dump_var_map (dump_file
, map
);
1158 values
= find_replaceable_exprs (map
);
1159 if (values
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
1160 dump_replaceable_exprs (dump_file
, values
);
1163 /* Assign real variables to the partitions now. */
1166 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1168 fprintf (dump_file
, "After Base variable replacement:\n");
1169 dump_var_map (dump_file
, map
);
1172 rewrite_trees (map
, values
);
1177 /* Remove PHI nodes which have been translated back to real variables. */
1180 for (phi
= phi_nodes (bb
); phi
; phi
= next
)
1182 next
= PHI_CHAIN (phi
);
1183 remove_phi_node (phi
, NULL_TREE
, true);
1187 /* If any copies were inserted on edges, analyze and insert them now. */
1188 perform_edge_inserts ();
1190 delete_var_map (map
);
1194 /* Search every PHI node for arguments associated with backedges which
1195 we can trivially determine will need a copy (the argument is either
1196 not an SSA_NAME or the argument has a different underlying variable
1197 than the PHI result).
1199 Insert a copy from the PHI argument to a new destination at the
1200 end of the block with the backedge to the top of the loop. Update
1201 the PHI argument to reference this new destination. */
1204 insert_backedge_copies (void)
1212 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1214 tree result
= PHI_RESULT (phi
);
1218 if (!is_gimple_reg (result
))
1221 result_var
= SSA_NAME_VAR (result
);
1222 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
1224 tree arg
= PHI_ARG_DEF (phi
, i
);
1225 edge e
= PHI_ARG_EDGE (phi
, i
);
1227 /* If the argument is not an SSA_NAME, then we will need a
1228 constant initialization. If the argument is an SSA_NAME with
1229 a different underlying variable then a copy statement will be
1231 if ((e
->flags
& EDGE_DFS_BACK
)
1232 && (TREE_CODE (arg
) != SSA_NAME
1233 || SSA_NAME_VAR (arg
) != result_var
))
1235 tree stmt
, name
, last
= NULL
;
1236 block_stmt_iterator bsi
;
1238 bsi
= bsi_last (PHI_ARG_EDGE (phi
, i
)->src
);
1239 if (!bsi_end_p (bsi
))
1240 last
= bsi_stmt (bsi
);
1242 /* In theory the only way we ought to get back to the
1243 start of a loop should be with a COND_EXPR or GOTO_EXPR.
1244 However, better safe than sorry.
1245 If the block ends with a control statement or
1246 something that might throw, then we have to
1247 insert this assignment before the last
1248 statement. Else insert it after the last statement. */
1249 if (last
&& stmt_ends_bb_p (last
))
1251 /* If the last statement in the block is the definition
1252 site of the PHI argument, then we can't insert
1253 anything after it. */
1254 if (TREE_CODE (arg
) == SSA_NAME
1255 && SSA_NAME_DEF_STMT (arg
) == last
)
1259 /* Create a new instance of the underlying variable of the
1261 stmt
= build_gimple_modify_stmt (NULL_TREE
,
1262 PHI_ARG_DEF (phi
, i
));
1263 name
= make_ssa_name (result_var
, stmt
);
1264 GIMPLE_STMT_OPERAND (stmt
, 0) = name
;
1266 /* Insert the new statement into the block and update
1268 if (last
&& stmt_ends_bb_p (last
))
1269 bsi_insert_before (&bsi
, stmt
, BSI_NEW_STMT
);
1271 bsi_insert_after (&bsi
, stmt
, BSI_NEW_STMT
);
1272 SET_PHI_ARG_DEF (phi
, i
, name
);
1279 /* Take the current function out of SSA form, translating PHIs as described in
1280 R. Morgan, ``Building an Optimizing Compiler'',
1281 Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */
1284 rewrite_out_of_ssa (void)
1286 /* If elimination of a PHI requires inserting a copy on a backedge,
1287 then we will have to split the backedge which has numerous
1288 undesirable performance effects.
1290 A significant number of such cases can be handled here by inserting
1291 copies into the loop itself. */
1292 insert_backedge_copies ();
1294 eliminate_virtual_phis ();
1296 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1297 dump_tree_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);
1299 remove_ssa_form (flag_tree_ter
&& !flag_mudflap
);
1301 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1302 dump_tree_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);
1304 cfun
->gimple_df
->in_ssa_p
= false;
1309 /* Define the parameters of the out of SSA pass. */
1311 struct tree_opt_pass pass_del_ssa
=
1313 "optimized", /* name */
1315 rewrite_out_of_ssa
, /* execute */
1318 0, /* static_pass_number */
1319 TV_TREE_SSA_TO_NORMAL
, /* tv_id */
1320 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
1321 0, /* properties_provided */
1322 /* ??? If TER is enabled, we also kill gimple. */
1323 PROP_ssa
, /* properties_destroyed */
1324 TODO_verify_ssa
| TODO_verify_flow
1325 | TODO_verify_stmts
, /* todo_flags_start */
1328 | TODO_remove_unused_locals
, /* todo_flags_finish */