1 /* Convert a program in SSA form into Normal form.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008 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 DECL_GIMPLE_REG_P (tmp) = DECL_GIMPLE_REG_P (t);
123 add_referenced_var (tmp);
125 /* add_referenced_var will create the annotation and set up some
126 of the flags in the annotation. However, some flags we need to
127 inherit from our original variable. */
128 set_symbol_mem_tag (tmp, symbol_mem_tag (t));
129 if (is_call_clobbered (t))
130 mark_call_clobbered (tmp, var_ann (t)->escape_mask);
131 if (bitmap_bit_p (gimple_call_used_vars (cfun), DECL_UID (t)))
132 bitmap_set_bit (gimple_call_used_vars (cfun), DECL_UID (tmp));
138 /* This helper function fill insert a copy from a constant or variable SRC to
139 variable DEST on edge E. */
142 insert_copy_on_edge (edge e, tree dest, tree src)
146 copy = gimple_build_assign (dest, src);
149 if (TREE_CODE (src) == ADDR_EXPR)
150 src = TREE_OPERAND (src, 0);
151 if (TREE_CODE (src) == VAR_DECL || TREE_CODE (src) == PARM_DECL)
154 if (dump_file && (dump_flags & TDF_DETAILS))
157 "Inserting a copy on edge BB%d->BB%d :",
160 print_gimple_stmt (dump_file, copy, 0, dump_flags);
161 fprintf (dump_file, "\n");
164 gsi_insert_on_edge (e, copy);
168 /* Create an elimination graph with SIZE nodes and associated data
172 new_elim_graph (int size)
174 elim_graph g = (elim_graph) xmalloc (sizeof (struct _elim_graph));
176 g->nodes = VEC_alloc (tree, heap, 30);
177 g->const_copies = VEC_alloc (tree, heap, 20);
178 g->edge_list = VEC_alloc (int, heap, 20);
179 g->stack = VEC_alloc (int, heap, 30);
181 g->visited = sbitmap_alloc (size);
187 /* Empty elimination graph G. */
190 clear_elim_graph (elim_graph g)
192 VEC_truncate (tree, g->nodes, 0);
193 VEC_truncate (int, g->edge_list, 0);
197 /* Delete elimination graph G. */
200 delete_elim_graph (elim_graph g)
202 sbitmap_free (g->visited);
203 VEC_free (int, heap, g->stack);
204 VEC_free (int, heap, g->edge_list);
205 VEC_free (tree, heap, g->const_copies);
206 VEC_free (tree, heap, g->nodes);
211 /* Return the number of nodes in graph G. */
214 elim_graph_size (elim_graph g)
216 return VEC_length (tree, g->nodes);
220 /* Add NODE to graph G, if it doesn't exist already. */
223 elim_graph_add_node (elim_graph g, tree node)
228 for (x = 0; VEC_iterate (tree, g->nodes, x, t); x++)
231 VEC_safe_push (tree, heap, g->nodes, node);
235 /* Add the edge PRED->SUCC to graph G. */
238 elim_graph_add_edge (elim_graph g, int pred, int succ)
240 VEC_safe_push (int, heap, g->edge_list, pred);
241 VEC_safe_push (int, heap, g->edge_list, succ);
245 /* Remove an edge from graph G for which NODE is the predecessor, and
246 return the successor node. -1 is returned if there is no such edge. */
249 elim_graph_remove_succ_edge (elim_graph g, int node)
253 for (x = 0; x < VEC_length (int, g->edge_list); x += 2)
254 if (VEC_index (int, g->edge_list, x) == node)
256 VEC_replace (int, g->edge_list, x, -1);
257 y = VEC_index (int, g->edge_list, x + 1);
258 VEC_replace (int, g->edge_list, x + 1, -1);
265 /* Find all the nodes in GRAPH which are successors to NODE in the
266 edge list. VAR will hold the partition number found. CODE is the
267 code fragment executed for every node found. */
269 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, CODE) \
273 for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2) \
275 y_ = VEC_index (int, (GRAPH)->edge_list, x_); \
278 (VAR) = VEC_index (int, (GRAPH)->edge_list, x_ + 1); \
284 /* Find all the nodes which are predecessors of NODE in the edge list for
285 GRAPH. VAR will hold the partition number found. CODE is the
286 code fragment executed for every node found. */
288 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, CODE) \
292 for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2) \
294 y_ = VEC_index (int, (GRAPH)->edge_list, x_ + 1); \
297 (VAR) = VEC_index (int, (GRAPH)->edge_list, x_); \
303 /* Add T to elimination graph G. */
306 eliminate_name (elim_graph g, tree T)
308 elim_graph_add_node (g, T);
312 /* Build elimination graph G for basic block BB on incoming PHI edge
316 eliminate_build (elim_graph g, basic_block B)
320 gimple_stmt_iterator gsi;
322 clear_elim_graph (g);
324 for (gsi = gsi_start_phis (B); !gsi_end_p (gsi); gsi_next (&gsi))
326 gimple phi = gsi_stmt (gsi);
328 T0 = var_to_partition_to_var (g->map, gimple_phi_result (phi));
330 /* Ignore results which are not in partitions. */
334 Ti = PHI_ARG_DEF (phi, g->e->dest_idx);
336 /* If this argument is a constant, or a SSA_NAME which is being
337 left in SSA form, just queue a copy to be emitted on this
339 if (!phi_ssa_name_p (Ti)
340 || (TREE_CODE (Ti) == SSA_NAME
341 && var_to_partition (g->map, Ti) == NO_PARTITION))
343 /* Save constant copies until all other copies have been emitted
345 VEC_safe_push (tree, heap, g->const_copies, T0);
346 VEC_safe_push (tree, heap, g->const_copies, Ti);
350 Ti = var_to_partition_to_var (g->map, Ti);
353 eliminate_name (g, T0);
354 eliminate_name (g, Ti);
355 p0 = var_to_partition (g->map, T0);
356 pi = var_to_partition (g->map, Ti);
357 elim_graph_add_edge (g, p0, pi);
364 /* Push successors of T onto the elimination stack for G. */
367 elim_forward (elim_graph g, int T)
370 SET_BIT (g->visited, T);
371 FOR_EACH_ELIM_GRAPH_SUCC (g, T, S,
373 if (!TEST_BIT (g->visited, S))
376 VEC_safe_push (int, heap, g->stack, T);
380 /* Return 1 if there unvisited predecessors of T in graph G. */
383 elim_unvisited_predecessor (elim_graph g, int T)
386 FOR_EACH_ELIM_GRAPH_PRED (g, T, P,
388 if (!TEST_BIT (g->visited, P))
394 /* Process predecessors first, and insert a copy. */
397 elim_backward (elim_graph g, int T)
400 SET_BIT (g->visited, T);
401 FOR_EACH_ELIM_GRAPH_PRED (g, T, P,
403 if (!TEST_BIT (g->visited, P))
405 elim_backward (g, P);
406 insert_copy_on_edge (g->e,
407 partition_to_var (g->map, P),
408 partition_to_var (g->map, T));
413 /* Insert required copies for T in graph G. Check for a strongly connected
414 region, and create a temporary to break the cycle if one is found. */
417 elim_create (elim_graph g, int T)
422 if (elim_unvisited_predecessor (g, T))
424 U = create_temp (partition_to_var (g->map, T));
425 insert_copy_on_edge (g->e, U, partition_to_var (g->map, T));
426 FOR_EACH_ELIM_GRAPH_PRED (g, T, P,
428 if (!TEST_BIT (g->visited, P))
430 elim_backward (g, P);
431 insert_copy_on_edge (g->e, partition_to_var (g->map, P), U);
437 S = elim_graph_remove_succ_edge (g, T);
440 SET_BIT (g->visited, T);
441 insert_copy_on_edge (g->e,
442 partition_to_var (g->map, T),
443 partition_to_var (g->map, S));
450 /* Eliminate all the phi nodes on edge E in graph G. */
453 eliminate_phi (edge e, elim_graph g)
456 basic_block B = e->dest;
458 gcc_assert (VEC_length (tree, g->const_copies) == 0);
460 /* Abnormal edges already have everything coalesced. */
461 if (e->flags & EDGE_ABNORMAL)
466 eliminate_build (g, B);
468 if (elim_graph_size (g) != 0)
472 sbitmap_zero (g->visited);
473 VEC_truncate (int, g->stack, 0);
475 for (x = 0; VEC_iterate (tree, g->nodes, x, var); x++)
477 int p = var_to_partition (g->map, var);
478 if (!TEST_BIT (g->visited, p))
482 sbitmap_zero (g->visited);
483 while (VEC_length (int, g->stack) > 0)
485 x = VEC_pop (int, g->stack);
486 if (!TEST_BIT (g->visited, x))
491 /* If there are any pending constant copies, issue them now. */
492 while (VEC_length (tree, g->const_copies) > 0)
495 src = VEC_pop (tree, g->const_copies);
496 dest = VEC_pop (tree, g->const_copies);
497 insert_copy_on_edge (e, dest, src);
502 /* Take the ssa-name var_map MAP, and assign real variables to each
506 assign_vars (var_map map)
512 num = num_var_partitions (map);
513 for (x = 0; x < num; x++)
515 var = partition_to_var (map, x);
516 if (TREE_CODE (var) != SSA_NAME)
519 /* It must already be coalesced. */
520 gcc_assert (ann->out_of_ssa_tag == 1);
521 if (dump_file && (dump_flags & TDF_DETAILS))
523 fprintf (dump_file, "partition %d already has variable ", x);
524 print_generic_expr (dump_file, var, TDF_SLIM);
525 fprintf (dump_file, " assigned to it.\n");
530 root = SSA_NAME_VAR (var);
531 ann = var_ann (root);
532 /* If ROOT is already associated, create a new one. */
533 if (ann->out_of_ssa_tag)
535 root = create_temp (root);
536 ann = var_ann (root);
538 /* ROOT has not been coalesced yet, so use it. */
539 if (dump_file && (dump_flags & TDF_DETAILS))
541 fprintf (dump_file, "Partition %d is assigned to var ", x);
542 print_generic_stmt (dump_file, root, TDF_SLIM);
544 change_partition_var (map, root, x);
550 /* Replace use operand P with whatever variable it has been rewritten to based
551 on the partitions in MAP. EXPR is an optional expression vector over SSA
552 versions which is used to replace P with an expression instead of a variable.
553 If the stmt is changed, return true. */
556 replace_use_variable (var_map map, use_operand_p p, gimple *expr)
559 tree var = USE_FROM_PTR (p);
561 /* Check if we are replacing this variable with an expression. */
564 int version = SSA_NAME_VERSION (var);
567 SET_USE (p, gimple_assign_rhs_to_tree (expr[version]));
572 new_var = var_to_partition_to_var (map, var);
575 SET_USE (p, new_var);
576 set_is_used (new_var);
583 /* Replace def operand DEF_P with whatever variable it has been rewritten to
584 based on the partitions in MAP. EXPR is an optional expression vector over
585 SSA versions which is used to replace DEF_P with an expression instead of a
586 variable. If the stmt is changed, return true. */
589 replace_def_variable (var_map map, def_operand_p def_p, tree *expr)
592 tree var = DEF_FROM_PTR (def_p);
594 /* Do nothing if we are replacing this variable with an expression. */
595 if (expr && expr[SSA_NAME_VERSION (var)])
598 new_var = var_to_partition_to_var (map, var);
601 SET_DEF (def_p, new_var);
602 set_is_used (new_var);
609 /* Remove any PHI node which is a virtual PHI. */
612 eliminate_virtual_phis (void)
615 gimple_stmt_iterator gsi;
619 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
621 gimple phi = gsi_stmt (gsi);
622 if (!is_gimple_reg (SSA_NAME_VAR (gimple_phi_result (phi))))
624 #ifdef ENABLE_CHECKING
626 /* There should be no arguments of this PHI which are in
627 the partition list, or we get incorrect results. */
628 for (i = 0; i < gimple_phi_num_args (phi); i++)
630 tree arg = PHI_ARG_DEF (phi, i);
631 if (TREE_CODE (arg) == SSA_NAME
632 && is_gimple_reg (SSA_NAME_VAR (arg)))
634 fprintf (stderr, "Argument of PHI is not virtual (");
635 print_generic_expr (stderr, arg, TDF_SLIM);
636 fprintf (stderr, "), but the result is :");
637 print_gimple_stmt (stderr, phi, 0, TDF_SLIM);
638 internal_error ("SSA corruption");
642 remove_phi_node (&gsi, true);
651 /* This function will rewrite the current program using the variable mapping
652 found in MAP. If the replacement vector VALUES is provided, any
653 occurrences of partitions with non-null entries in the vector will be
654 replaced with the expression in the vector instead of its mapped
658 rewrite_trees (var_map map, gimple *values)
662 gimple_stmt_iterator gsi;
667 #ifdef ENABLE_CHECKING
668 /* Search for PHIs where the destination has no partition, but one
669 or more arguments has a partition. This should not happen and can
670 create incorrect code. */
673 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
675 gimple phi = gsi_stmt (gsi);
676 tree T0 = var_to_partition_to_var (map, gimple_phi_result (phi));
680 for (i = 0; i < gimple_phi_num_args (phi); i++)
682 tree arg = PHI_ARG_DEF (phi, i);
684 if (TREE_CODE (arg) == SSA_NAME
685 && var_to_partition (map, arg) != NO_PARTITION)
687 fprintf (stderr, "Argument of PHI is in a partition :(");
688 print_generic_expr (stderr, arg, TDF_SLIM);
689 fprintf (stderr, "), but the result is not :");
690 print_gimple_stmt (stderr, phi, 0, TDF_SLIM);
691 internal_error ("SSA corruption");
699 /* Replace PHI nodes with any required copies. */
700 g = new_elim_graph (map->num_partitions);
704 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
706 gimple stmt = gsi_stmt (gsi);
707 use_operand_p use_p, copy_use_p;
709 bool remove = false, is_copy = false;
715 if (gimple_assign_copy_p (stmt))
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 gsi_remove (&gsi, true);
763 if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
764 gimple_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(gimple_seq,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_gimple s1, const_gimple s2)
805 #ifdef ENABLE_CHECKING
806 gcc_assert (is_gimple_assign (s1));
807 gcc_assert (is_gimple_assign (s2));
808 gcc_assert (DECL_P (gimple_assign_lhs (s1)));
809 gcc_assert (DECL_P (gimple_assign_lhs (s2)));
812 if (gimple_assign_lhs (s1) != gimple_assign_lhs (s2))
815 if (gimple_assign_rhs1 (s1) != gimple_assign_rhs1 (s2))
822 /* Compare the PENDING_STMT list for edges E1 and E2. Return true if the lists
823 contain the same sequence of copies. */
826 identical_stmt_lists_p (const_edge e1, const_edge e2)
828 gimple_seq t1 = PENDING_STMT (e1);
829 gimple_seq t2 = PENDING_STMT (e2);
830 gimple_stmt_iterator gsi1, gsi2;
832 for (gsi1 = gsi_start (t1), gsi2 = gsi_start (t2);
833 !gsi_end_p (gsi1) && !gsi_end_p (gsi2);
834 gsi_next (&gsi1), gsi_next (&gsi2))
836 if (!identical_copies_p (gsi_stmt (gsi1), gsi_stmt (gsi2)))
840 if (!gsi_end_p (gsi1) || !gsi_end_p (gsi2))
847 /* Allocate data structures used in analyze_edges_for_bb. */
850 init_analyze_edges_for_bb (void)
852 edge_leader = VEC_alloc (edge, heap, 25);
853 stmt_list = VEC_alloc (gimple_seq, heap, 25);
854 leader_has_match = BITMAP_ALLOC (NULL);
858 /* Free data structures used in analyze_edges_for_bb. */
861 fini_analyze_edges_for_bb (void)
863 VEC_free (edge, heap, edge_leader);
864 VEC_free (gimple_seq, heap, stmt_list);
865 BITMAP_FREE (leader_has_match);
868 /* A helper function to be called via walk_tree. Return DATA if it is
869 contained in subtree TP. */
872 contains_tree_r (tree * tp, int *walk_subtrees, void *data)
883 /* A threshold for the number of insns contained in the latch block.
884 It is used to prevent blowing the loop with too many copies from
886 #define MAX_STMTS_IN_LATCH 2
888 /* Return TRUE if the stmts on SINGLE-EDGE can be moved to the
889 body of the loop. This should be permitted only if SINGLE-EDGE is a
890 single-basic-block latch edge and thus cleaning the latch will help
891 to create a single-basic-block loop. Otherwise return FALSE. */
894 process_single_block_loop_latch (edge single_edge)
897 basic_block b_exit, b_pheader, b_loop = single_edge->src;
900 gimple_stmt_iterator gsi, gsi_exit;
901 gimple_stmt_iterator tsi;
904 unsigned int count = 0;
906 if (single_edge == NULL || (single_edge->dest != single_edge->src)
907 || (EDGE_COUNT (b_loop->succs) != 2)
908 || (EDGE_COUNT (b_loop->preds) != 2))
911 /* Get the stmts on the latch edge. */
912 stmts = PENDING_STMT (single_edge);
914 /* Find the successor edge which is not the latch edge. */
915 FOR_EACH_EDGE (e, ei, b_loop->succs)
916 if (e->dest != b_loop)
921 /* Check that the exit block has only the loop as a predecessor,
922 and that there are no pending stmts on that edge as well. */
923 if (EDGE_COUNT (b_exit->preds) != 1 || PENDING_STMT (e))
926 /* Find the predecessor edge which is not the latch edge. */
927 FOR_EACH_EDGE (e, ei, b_loop->preds)
928 if (e->src != b_loop)
933 if (b_exit == b_pheader || b_exit == b_loop || b_pheader == b_loop)
936 gsi_exit = gsi_after_labels (b_exit);
938 /* Get the last stmt in the loop body. */
939 gsi = gsi_last_bb (single_edge->src);
940 stmt = gsi_stmt (gsi);
942 if (gimple_code (stmt) != GIMPLE_COND)
946 expr = build2 (gimple_cond_code (stmt), boolean_type_node,
947 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
948 /* Iterate over the insns on the latch and count them. */
949 for (tsi = gsi_start (stmts); !gsi_end_p (tsi); gsi_next (&tsi))
951 gimple stmt1 = gsi_stmt (tsi);
955 /* Check that the condition does not contain any new definition
956 created in the latch as the stmts from the latch intended
958 if (gimple_code (stmt1) != GIMPLE_ASSIGN)
960 var = gimple_assign_lhs (stmt1);
961 if (TREE_THIS_VOLATILE (var)
962 || TYPE_VOLATILE (TREE_TYPE (var))
963 || walk_tree (&expr, contains_tree_r, var, NULL))
966 /* Check that the latch does not contain more than MAX_STMTS_IN_LATCH
967 insns. The purpose of this restriction is to prevent blowing the
968 loop with too many copies from the latch. */
969 if (count > MAX_STMTS_IN_LATCH)
972 /* Apply the transformation - clean up the latch block:
977 if (cond) goto L2 else goto L3;
991 if (cond) goto L1 else goto L2;
996 for (tsi = gsi_start (stmts); !gsi_end_p (tsi); gsi_next (&tsi))
998 gimple stmt1 = gsi_stmt (tsi);
1002 /* Create a new variable to load back the value of var in case
1003 we exit the loop. */
1004 var = gimple_assign_lhs (stmt1);
1005 tmp_var = create_temp (var);
1006 copy = gimple_build_assign (tmp_var, var);
1007 set_is_used (tmp_var);
1008 gsi_insert_before (&gsi, copy, GSI_SAME_STMT);
1009 copy = gimple_build_assign (var, tmp_var);
1010 gsi_insert_before (&gsi_exit, copy, GSI_SAME_STMT);
1013 PENDING_STMT (single_edge) = 0;
1014 /* Insert the new stmts to the loop body. */
1015 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
1019 "\nCleaned-up latch block of loop with single BB: %d\n\n",
1020 single_edge->dest->index);
1025 /* Look at all the incoming edges to block BB, and decide where the best place
1026 to insert the stmts on each edge are, and perform those insertions. */
1029 analyze_edges_for_bb (basic_block bb)
1035 bool have_opportunity;
1036 gimple_stmt_iterator gsi;
1038 edge single_edge = NULL;
1044 /* Blocks which contain at least one abnormal edge cannot use
1045 make_forwarder_block. Look for these blocks, and commit any PENDING_STMTs
1046 found on edges in these block. */
1047 have_opportunity = true;
1048 FOR_EACH_EDGE (e, ei, bb->preds)
1049 if (e->flags & EDGE_ABNORMAL)
1051 have_opportunity = false;
1055 if (!have_opportunity)
1057 FOR_EACH_EDGE (e, ei, bb->preds)
1058 if (PENDING_STMT (e))
1059 gsi_commit_one_edge_insert (e, NULL);
1063 /* Find out how many edges there are with interesting pending stmts on them.
1064 Commit the stmts on edges we are not interested in. */
1065 FOR_EACH_EDGE (e, ei, bb->preds)
1067 if (PENDING_STMT (e))
1069 gcc_assert (!(e->flags & EDGE_ABNORMAL));
1070 if (e->flags & EDGE_FALLTHRU)
1072 gsi = gsi_start_bb (e->src);
1073 if (!gsi_end_p (gsi))
1075 stmt = gsi_stmt (gsi);
1077 gcc_assert (stmt != NULL);
1078 is_label = (gimple_code (stmt) == GIMPLE_LABEL);
1079 /* Punt if it has non-label stmts, or isn't local. */
1081 || DECL_NONLOCAL (gimple_label_label (stmt))
1082 || !gsi_end_p (gsi))
1084 gsi_commit_one_edge_insert (e, NULL);
1094 /* If there aren't at least 2 edges, no sharing will happen. */
1099 /* Add stmts to the edge unless processed specially as a
1100 single-block loop latch edge. */
1101 if (!process_single_block_loop_latch (single_edge))
1102 gsi_commit_one_edge_insert (single_edge, NULL);
1107 /* Ensure that we have empty worklists. */
1108 #ifdef ENABLE_CHECKING
1109 gcc_assert (VEC_length (edge, edge_leader) == 0);
1110 gcc_assert (VEC_length (gimple_seq, stmt_list) == 0);
1111 gcc_assert (bitmap_empty_p (leader_has_match));
1114 /* Find the "leader" block for each set of unique stmt lists. Preference is
1115 given to FALLTHRU blocks since they would need a GOTO to arrive at another
1116 block. The leader edge destination is the block which all the other edges
1117 with the same stmt list will be redirected to. */
1118 have_opportunity = false;
1119 FOR_EACH_EDGE (e, ei, bb->preds)
1121 if (PENDING_STMT (e))
1125 /* Look for the same stmt list in edge leaders list. */
1126 for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
1128 if (identical_stmt_lists_p (leader, e))
1130 /* Give this edge the same stmt list pointer. */
1131 PENDING_STMT (e) = NULL;
1133 bitmap_set_bit (leader_has_match, x);
1134 have_opportunity = found = true;
1139 /* If no similar stmt list, add this edge to the leader list. */
1142 VEC_safe_push (edge, heap, edge_leader, e);
1143 VEC_safe_push (gimple_seq, heap, stmt_list, PENDING_STMT (e));
1148 /* If there are no similar lists, just issue the stmts. */
1149 if (!have_opportunity)
1151 for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
1152 gsi_commit_one_edge_insert (leader, NULL);
1153 VEC_truncate (edge, edge_leader, 0);
1154 VEC_truncate (gimple_seq, stmt_list, 0);
1155 bitmap_clear (leader_has_match);
1160 fprintf (dump_file, "\nOpportunities in BB %d for stmt/block reduction:\n",
1163 /* For each common list, create a forwarding block and issue the stmt's
1165 for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
1166 if (bitmap_bit_p (leader_has_match, x))
1169 gimple_stmt_iterator gsi;
1170 gimple_seq curr_stmt_list;
1172 leader_match = leader;
1174 /* The tree_* cfg manipulation routines use the PENDING_EDGE field
1175 for various PHI manipulations, so it gets cleared when calls are
1176 made to make_forwarder_block(). So make sure the edge is clear,
1177 and use the saved stmt list. */
1178 PENDING_STMT (leader) = NULL;
1179 leader->aux = leader;
1180 curr_stmt_list = VEC_index (gimple_seq, stmt_list, x);
1182 new_edge = make_forwarder_block (leader->dest, same_stmt_list_p,
1184 bb = new_edge->dest;
1187 fprintf (dump_file, "Splitting BB %d for Common stmt list. ",
1188 leader->dest->index);
1189 fprintf (dump_file, "Original block is now BB%d.\n", bb->index);
1190 print_gimple_seq (dump_file, curr_stmt_list, 0, TDF_VOPS);
1193 FOR_EACH_EDGE (e, ei, new_edge->src->preds)
1197 fprintf (dump_file, " Edge (%d->%d) lands here.\n",
1198 e->src->index, e->dest->index);
1201 gsi = gsi_last_bb (leader->dest);
1202 gsi_insert_seq_after (&gsi, curr_stmt_list, GSI_NEW_STMT);
1204 leader_match = NULL;
1205 /* We should never get a new block now. */
1209 PENDING_STMT (leader) = VEC_index (gimple_seq, stmt_list, x);
1210 gsi_commit_one_edge_insert (leader, NULL);
1214 /* Clear the working data structures. */
1215 VEC_truncate (edge, edge_leader, 0);
1216 VEC_truncate (gimple_seq, stmt_list, 0);
1217 bitmap_clear (leader_has_match);
1221 /* This function will analyze the insertions which were performed on edges,
1222 and decide whether they should be left on that edge, or whether it is more
1223 efficient to emit some subset of them in a single block. All stmts are
1224 inserted somewhere. */
1227 perform_edge_inserts (void)
1232 fprintf(dump_file, "Analyzing Edge Insertions.\n");
1234 /* analyze_edges_for_bb calls make_forwarder_block, which tries to
1235 incrementally update the dominator information. Since we don't
1236 need dominator information after this pass, go ahead and free the
1237 dominator information. */
1238 free_dominance_info (CDI_DOMINATORS);
1239 free_dominance_info (CDI_POST_DOMINATORS);
1241 /* Allocate data structures used in analyze_edges_for_bb. */
1242 init_analyze_edges_for_bb ();
1245 analyze_edges_for_bb (bb);
1247 analyze_edges_for_bb (EXIT_BLOCK_PTR);
1249 /* Free data structures used in analyze_edges_for_bb. */
1250 fini_analyze_edges_for_bb ();
1252 #ifdef ENABLE_CHECKING
1258 FOR_EACH_EDGE (e, ei, bb->preds)
1260 if (PENDING_STMT (e))
1261 error (" Pending stmts not issued on PRED edge (%d, %d)\n",
1262 e->src->index, e->dest->index);
1264 FOR_EACH_EDGE (e, ei, bb->succs)
1266 if (PENDING_STMT (e))
1267 error (" Pending stmts not issued on SUCC edge (%d, %d)\n",
1268 e->src->index, e->dest->index);
1271 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
1273 if (PENDING_STMT (e))
1274 error (" Pending stmts not issued on ENTRY edge (%d, %d)\n",
1275 e->src->index, e->dest->index);
1277 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1279 if (PENDING_STMT (e))
1280 error (" Pending stmts not issued on EXIT edge (%d, %d)\n",
1281 e->src->index, e->dest->index);
1288 /* Remove the ssa-names in the current function and translate them into normal
1289 compiler variables. PERFORM_TER is true if Temporary Expression Replacement
1290 should also be used. */
1293 remove_ssa_form (bool perform_ter)
1296 gimple *values = NULL;
1298 gimple_stmt_iterator gsi;
1300 map = coalesce_ssa_name ();
1302 /* Return to viewing the variable list as just all reference variables after
1303 coalescing has been performed. */
1304 partition_view_normal (map, false);
1306 if (dump_file && (dump_flags & TDF_DETAILS))
1308 fprintf (dump_file, "After Coalescing:\n");
1309 dump_var_map (dump_file, map);
1314 values = find_replaceable_exprs (map);
1315 if (values && dump_file && (dump_flags & TDF_DETAILS))
1316 dump_replaceable_exprs (dump_file, values);
1319 /* Assign real variables to the partitions now. */
1322 if (dump_file && (dump_flags & TDF_DETAILS))
1324 fprintf (dump_file, "After Base variable replacement:\n");
1325 dump_var_map (dump_file, map);
1328 rewrite_trees (map, values);
1333 /* Remove PHI nodes which have been translated back to real variables. */
1335 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);)
1336 remove_phi_node (&gsi, true);
1338 /* If any copies were inserted on edges, analyze and insert them now. */
1339 perform_edge_inserts ();
1341 delete_var_map (map);
1345 /* Search every PHI node for arguments associated with backedges which
1346 we can trivially determine will need a copy (the argument is either
1347 not an SSA_NAME or the argument has a different underlying variable
1348 than the PHI result).
1350 Insert a copy from the PHI argument to a new destination at the
1351 end of the block with the backedge to the top of the loop. Update
1352 the PHI argument to reference this new destination. */
1355 insert_backedge_copies (void)
1358 gimple_stmt_iterator gsi;
1362 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1364 gimple phi = gsi_stmt (gsi);
1365 tree result = gimple_phi_result (phi);
1369 if (!is_gimple_reg (result))
1372 result_var = SSA_NAME_VAR (result);
1373 for (i = 0; i < gimple_phi_num_args (phi); i++)
1375 tree arg = gimple_phi_arg_def (phi, i);
1376 edge e = gimple_phi_arg_edge (phi, i);
1378 /* If the argument is not an SSA_NAME, then we will need a
1379 constant initialization. If the argument is an SSA_NAME with
1380 a different underlying variable then a copy statement will be
1382 if ((e->flags & EDGE_DFS_BACK)
1383 && (TREE_CODE (arg) != SSA_NAME
1384 || SSA_NAME_VAR (arg) != result_var))
1387 gimple stmt, last = NULL;
1388 gimple_stmt_iterator gsi2;
1390 gsi2 = gsi_last_bb (gimple_phi_arg_edge (phi, i)->src);
1391 if (!gsi_end_p (gsi2))
1392 last = gsi_stmt (gsi2);
1394 /* In theory the only way we ought to get back to the
1395 start of a loop should be with a COND_EXPR or GOTO_EXPR.
1396 However, better safe than sorry.
1397 If the block ends with a control statement or
1398 something that might throw, then we have to
1399 insert this assignment before the last
1400 statement. Else insert it after the last statement. */
1401 if (last && stmt_ends_bb_p (last))
1403 /* If the last statement in the block is the definition
1404 site of the PHI argument, then we can't insert
1405 anything after it. */
1406 if (TREE_CODE (arg) == SSA_NAME
1407 && SSA_NAME_DEF_STMT (arg) == last)
1411 /* Create a new instance of the underlying variable of the
1413 stmt = gimple_build_assign (result_var,
1414 gimple_phi_arg_def (phi, i));
1415 name = make_ssa_name (result_var, stmt);
1416 gimple_assign_set_lhs (stmt, name);
1418 /* Insert the new statement into the block and update
1420 if (last && stmt_ends_bb_p (last))
1421 gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT);
1423 gsi_insert_after (&gsi2, stmt, GSI_NEW_STMT);
1424 SET_PHI_ARG_DEF (phi, i, name);
1431 /* Take the current function out of SSA form, translating PHIs as described in
1432 R. Morgan, ``Building an Optimizing Compiler'',
1433 Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */
1436 rewrite_out_of_ssa (void)
1438 /* If elimination of a PHI requires inserting a copy on a backedge,
1439 then we will have to split the backedge which has numerous
1440 undesirable performance effects.
1442 A significant number of such cases can be handled here by inserting
1443 copies into the loop itself. */
1444 insert_backedge_copies ();
1446 eliminate_virtual_phis ();
1448 if (dump_file && (dump_flags & TDF_DETAILS))
1449 gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
1451 remove_ssa_form (flag_tree_ter && !flag_mudflap);
1453 if (dump_file && (dump_flags & TDF_DETAILS))
1454 gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
1456 cfun->gimple_df->in_ssa_p = false;
1461 /* Define the parameters of the out of SSA pass. */
1463 struct gimple_opt_pass pass_del_ssa =
1467 "optimized", /* name */
1469 rewrite_out_of_ssa, /* execute */
1472 0, /* static_pass_number */
1473 TV_TREE_SSA_TO_NORMAL, /* tv_id */
1474 PROP_cfg | PROP_ssa, /* properties_required */
1475 0, /* properties_provided */
1476 /* ??? If TER is enabled, we also kill gimple. */
1477 PROP_ssa, /* properties_destroyed */
1478 TODO_verify_ssa | TODO_verify_flow
1479 | TODO_verify_stmts, /* todo_flags_start */
1482 | TODO_remove_unused_locals /* todo_flags_finish */