1 /* Convert a program in SSA form into Normal form.
2 Copyright (C) 2004, 2005 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 2, 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 COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
24 #include "coretypes.h"
31 #include "langhooks.h"
32 #include "hard-reg-set.h"
33 #include "basic-block.h"
38 #include "diagnostic.h"
40 #include "tree-flow.h"
41 #include "tree-gimple.h"
42 #include "tree-inline.h"
46 #include "tree-dump.h"
47 #include "tree-ssa-live.h"
48 #include "tree-pass.h"
50 /* Flags to pass to remove_ssa_form. */
52 #define SSANORM_PERFORM_TER 0x1
53 #define SSANORM_COMBINE_TEMPS 0x2
54 #define SSANORM_COALESCE_PARTITIONS 0x4
55 #define SSANORM_USE_COALESCE_LIST 0x8
57 /* Used to hold all the components required to do SSA PHI elimination.
58 The node and pred/succ list is a simple linear list of nodes and
59 edges represented as pairs of nodes.
61 The predecessor and successor list: Nodes are entered in pairs, where
62 [0] ->PRED, [1]->SUCC. All the even indexes in the array represent
63 predecessors, all the odd elements are successors.
66 When implemented as bitmaps, very large programs SSA->Normal times were
67 being dominated by clearing the interference graph.
69 Typically this list of edges is extremely small since it only includes
70 PHI results and uses from a single edge which have not coalesced with
71 each other. This means that no virtual PHI nodes are included, and
72 empirical evidence suggests that the number of edges rarely exceed
73 3, and in a bootstrap of GCC, the maximum size encountered was 7.
74 This also limits the number of possible nodes that are involved to
75 rarely more than 6, and in the bootstrap of gcc, the maximum number
76 of nodes encountered was 12. */
78 typedef struct _elim_graph {
79 /* Size of the elimination vectors. */
82 /* List of nodes in the elimination graph. */
85 /* The predecessor and successor edge list. */
86 varray_type edge_list;
91 /* Stack for visited nodes. */
94 /* The variable partition map. */
97 /* Edge being eliminated by this graph. */
100 /* List of constant copies to emit. These are pushed on in pairs. */
101 varray_type const_copies;
105 /* Local functions. */
106 static tree create_temp (tree);
107 static void insert_copy_on_edge (edge, tree, tree);
108 static elim_graph new_elim_graph (int);
109 static inline void delete_elim_graph (elim_graph);
110 static inline void clear_elim_graph (elim_graph);
111 static inline int elim_graph_size (elim_graph);
112 static inline void elim_graph_add_node (elim_graph, tree);
113 static inline void elim_graph_add_edge (elim_graph, int, int);
114 static inline int elim_graph_remove_succ_edge (elim_graph, int);
116 static inline void eliminate_name (elim_graph, tree);
117 static void eliminate_build (elim_graph, basic_block);
118 static void elim_forward (elim_graph, int);
119 static int elim_unvisited_predecessor (elim_graph, int);
120 static void elim_backward (elim_graph, int);
121 static void elim_create (elim_graph, int);
122 static void eliminate_phi (edge, elim_graph);
123 static tree_live_info_p coalesce_ssa_name (var_map, int);
124 static void assign_vars (var_map);
125 static bool replace_use_variable (var_map, use_operand_p, tree *);
126 static bool replace_def_variable (var_map, def_operand_p, tree *);
127 static void eliminate_virtual_phis (void);
128 static void coalesce_abnormal_edges (var_map, conflict_graph, root_var_p);
129 static void print_exprs (FILE *, const char *, tree, const char *, tree,
131 static void print_exprs_edge (FILE *, edge, const char *, tree, const char *,
135 /* Create a temporary variable based on the type of variable T. Use T's name
142 const char *name = NULL;
145 if (TREE_CODE (t) == SSA_NAME)
146 t = SSA_NAME_VAR (t);
148 gcc_assert (TREE_CODE (t) == VAR_DECL || TREE_CODE (t) == PARM_DECL);
150 type = TREE_TYPE (t);
153 name = IDENTIFIER_POINTER (tmp);
157 tmp = create_tmp_var (type, name);
159 if (DECL_DEBUG_EXPR (t) && DECL_DEBUG_EXPR_IS_FROM (t))
161 DECL_DEBUG_EXPR (tmp) = DECL_DEBUG_EXPR (t);
162 DECL_DEBUG_EXPR_IS_FROM (tmp) = 1;
164 else if (!DECL_IGNORED_P (t))
166 DECL_DEBUG_EXPR (tmp) = t;
167 DECL_DEBUG_EXPR_IS_FROM (tmp) = 1;
169 DECL_ARTIFICIAL (tmp) = DECL_ARTIFICIAL (t);
170 DECL_IGNORED_P (tmp) = DECL_IGNORED_P (t);
171 add_referenced_tmp_var (tmp);
173 /* add_referenced_tmp_var will create the annotation and set up some
174 of the flags in the annotation. However, some flags we need to
175 inherit from our original variable. */
176 var_ann (tmp)->type_mem_tag = var_ann (t)->type_mem_tag;
177 if (is_call_clobbered (t))
178 mark_call_clobbered (tmp);
184 /* This helper function fill insert a copy from a constant or variable SRC to
185 variable DEST on edge E. */
188 insert_copy_on_edge (edge e, tree dest, tree src)
192 copy = build (MODIFY_EXPR, TREE_TYPE (dest), dest, src);
195 if (TREE_CODE (src) == ADDR_EXPR)
196 src = TREE_OPERAND (src, 0);
197 if (TREE_CODE (src) == VAR_DECL || TREE_CODE (src) == PARM_DECL)
200 if (dump_file && (dump_flags & TDF_DETAILS))
203 "Inserting a copy on edge BB%d->BB%d :",
206 print_generic_expr (dump_file, copy, dump_flags);
207 fprintf (dump_file, "\n");
210 bsi_insert_on_edge (e, copy);
214 /* Create an elimination graph with SIZE nodes and associated data
218 new_elim_graph (int size)
220 elim_graph g = (elim_graph) xmalloc (sizeof (struct _elim_graph));
222 VARRAY_TREE_INIT (g->nodes, 30, "Elimination Node List");
223 VARRAY_TREE_INIT (g->const_copies, 20, "Elimination Constant Copies");
224 VARRAY_INT_INIT (g->edge_list, 20, "Elimination Edge List");
225 VARRAY_INT_INIT (g->stack, 30, " Elimination Stack");
227 g->visited = sbitmap_alloc (size);
233 /* Empty elimination graph G. */
236 clear_elim_graph (elim_graph g)
238 VARRAY_POP_ALL (g->nodes);
239 VARRAY_POP_ALL (g->edge_list);
243 /* Delete elimination graph G. */
246 delete_elim_graph (elim_graph g)
248 sbitmap_free (g->visited);
253 /* Return the number of nodes in graph G. */
256 elim_graph_size (elim_graph g)
258 return VARRAY_ACTIVE_SIZE (g->nodes);
262 /* Add NODE to graph G, if it doesn't exist already. */
265 elim_graph_add_node (elim_graph g, tree node)
268 for (x = 0; x < elim_graph_size (g); x++)
269 if (VARRAY_TREE (g->nodes, x) == node)
271 VARRAY_PUSH_TREE (g->nodes, node);
275 /* Add the edge PRED->SUCC to graph G. */
278 elim_graph_add_edge (elim_graph g, int pred, int succ)
280 VARRAY_PUSH_INT (g->edge_list, pred);
281 VARRAY_PUSH_INT (g->edge_list, succ);
285 /* Remove an edge from graph G for which NODE is the predecessor, and
286 return the successor node. -1 is returned if there is no such edge. */
289 elim_graph_remove_succ_edge (elim_graph g, int node)
293 for (x = 0; x < VARRAY_ACTIVE_SIZE (g->edge_list); x += 2)
294 if (VARRAY_INT (g->edge_list, x) == node)
296 VARRAY_INT (g->edge_list, x) = -1;
297 y = VARRAY_INT (g->edge_list, x + 1);
298 VARRAY_INT (g->edge_list, x + 1) = -1;
305 /* Find all the nodes in GRAPH which are successors to NODE in the
306 edge list. VAR will hold the partition number found. CODE is the
307 code fragment executed for every node found. */
309 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, CODE) \
313 for (x_ = 0; x_ < VARRAY_ACTIVE_SIZE ((GRAPH)->edge_list); x_ += 2) \
315 y_ = VARRAY_INT ((GRAPH)->edge_list, x_); \
318 (VAR) = VARRAY_INT ((GRAPH)->edge_list, x_ + 1); \
324 /* Find all the nodes which are predecessors of NODE in the edge list for
325 GRAPH. VAR will hold the partition number found. CODE is the
326 code fragment executed for every node found. */
328 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, CODE) \
332 for (x_ = 0; x_ < VARRAY_ACTIVE_SIZE ((GRAPH)->edge_list); x_ += 2) \
334 y_ = VARRAY_INT ((GRAPH)->edge_list, x_ + 1); \
337 (VAR) = VARRAY_INT ((GRAPH)->edge_list, x_); \
343 /* Add T to elimination graph G. */
346 eliminate_name (elim_graph g, tree T)
348 elim_graph_add_node (g, T);
352 /* Build elimination graph G for basic block BB on incoming PHI edge
356 eliminate_build (elim_graph g, basic_block B)
362 clear_elim_graph (g);
364 for (phi = phi_nodes (B); phi; phi = PHI_CHAIN (phi))
366 T0 = var_to_partition_to_var (g->map, PHI_RESULT (phi));
368 /* Ignore results which are not in partitions. */
372 Ti = PHI_ARG_DEF (phi, g->e->dest_idx);
374 /* If this argument is a constant, or a SSA_NAME which is being
375 left in SSA form, just queue a copy to be emitted on this
377 if (!phi_ssa_name_p (Ti)
378 || (TREE_CODE (Ti) == SSA_NAME
379 && var_to_partition (g->map, Ti) == NO_PARTITION))
381 /* Save constant copies until all other copies have been emitted
383 VARRAY_PUSH_TREE (g->const_copies, T0);
384 VARRAY_PUSH_TREE (g->const_copies, Ti);
388 Ti = var_to_partition_to_var (g->map, Ti);
391 eliminate_name (g, T0);
392 eliminate_name (g, Ti);
393 p0 = var_to_partition (g->map, T0);
394 pi = var_to_partition (g->map, Ti);
395 elim_graph_add_edge (g, p0, pi);
402 /* Push successors of T onto the elimination stack for G. */
405 elim_forward (elim_graph g, int T)
408 SET_BIT (g->visited, T);
409 FOR_EACH_ELIM_GRAPH_SUCC (g, T, S,
411 if (!TEST_BIT (g->visited, S))
414 VARRAY_PUSH_INT (g->stack, T);
418 /* Return 1 if there unvisited predecessors of T in graph G. */
421 elim_unvisited_predecessor (elim_graph g, int T)
424 FOR_EACH_ELIM_GRAPH_PRED (g, T, P,
426 if (!TEST_BIT (g->visited, P))
432 /* Process predecessors first, and insert a copy. */
435 elim_backward (elim_graph g, int T)
438 SET_BIT (g->visited, T);
439 FOR_EACH_ELIM_GRAPH_PRED (g, T, P,
441 if (!TEST_BIT (g->visited, P))
443 elim_backward (g, P);
444 insert_copy_on_edge (g->e,
445 partition_to_var (g->map, P),
446 partition_to_var (g->map, T));
451 /* Insert required copies for T in graph G. Check for a strongly connected
452 region, and create a temporary to break the cycle if one is found. */
455 elim_create (elim_graph g, int T)
460 if (elim_unvisited_predecessor (g, T))
462 U = create_temp (partition_to_var (g->map, T));
463 insert_copy_on_edge (g->e, U, partition_to_var (g->map, T));
464 FOR_EACH_ELIM_GRAPH_PRED (g, T, P,
466 if (!TEST_BIT (g->visited, P))
468 elim_backward (g, P);
469 insert_copy_on_edge (g->e, partition_to_var (g->map, P), U);
475 S = elim_graph_remove_succ_edge (g, T);
478 SET_BIT (g->visited, T);
479 insert_copy_on_edge (g->e,
480 partition_to_var (g->map, T),
481 partition_to_var (g->map, S));
487 /* Eliminate all the phi nodes on edge E in graph G. */
490 eliminate_phi (edge e, elim_graph g)
494 basic_block B = e->dest;
496 gcc_assert (VARRAY_ACTIVE_SIZE (g->const_copies) == 0);
498 /* Abnormal edges already have everything coalesced, or the coalescer
499 would have aborted. */
500 if (e->flags & EDGE_ABNORMAL)
503 num_nodes = num_var_partitions (g->map);
506 eliminate_build (g, B);
508 if (elim_graph_size (g) != 0)
510 sbitmap_zero (g->visited);
511 VARRAY_POP_ALL (g->stack);
513 for (x = 0; x < elim_graph_size (g); x++)
515 tree var = VARRAY_TREE (g->nodes, x);
516 int p = var_to_partition (g->map, var);
517 if (!TEST_BIT (g->visited, p))
521 sbitmap_zero (g->visited);
522 while (VARRAY_ACTIVE_SIZE (g->stack) > 0)
524 x = VARRAY_TOP_INT (g->stack);
525 VARRAY_POP (g->stack);
526 if (!TEST_BIT (g->visited, x))
531 /* If there are any pending constant copies, issue them now. */
532 while (VARRAY_ACTIVE_SIZE (g->const_copies) > 0)
535 src = VARRAY_TOP_TREE (g->const_copies);
536 VARRAY_POP (g->const_copies);
537 dest = VARRAY_TOP_TREE (g->const_copies);
538 VARRAY_POP (g->const_copies);
539 insert_copy_on_edge (e, dest, src);
544 /* Shortcut routine to print messages to file F of the form:
545 "STR1 EXPR1 STR2 EXPR2 STR3." */
548 print_exprs (FILE *f, const char *str1, tree expr1, const char *str2,
549 tree expr2, const char *str3)
551 fprintf (f, "%s", str1);
552 print_generic_expr (f, expr1, TDF_SLIM);
553 fprintf (f, "%s", str2);
554 print_generic_expr (f, expr2, TDF_SLIM);
555 fprintf (f, "%s", str3);
559 /* Shortcut routine to print abnormal edge messages to file F of the form:
560 "STR1 EXPR1 STR2 EXPR2 across edge E. */
563 print_exprs_edge (FILE *f, edge e, const char *str1, tree expr1,
564 const char *str2, tree expr2)
566 print_exprs (f, str1, expr1, str2, expr2, " across an abnormal edge");
567 fprintf (f, " from BB%d->BB%d\n", e->src->index,
572 /* Coalesce partitions in MAP which are live across abnormal edges in GRAPH.
573 RV is the root variable groupings of the partitions in MAP. Since code
574 cannot be inserted on these edges, failure to coalesce something across
575 an abnormal edge is an error. */
578 coalesce_abnormal_edges (var_map map, conflict_graph graph, root_var_p rv)
586 /* Code cannot be inserted on abnormal edges. Look for all abnormal
587 edges, and coalesce any PHI results with their arguments across
591 FOR_EACH_EDGE (e, ei, bb->succs)
592 if (e->dest != EXIT_BLOCK_PTR && e->flags & EDGE_ABNORMAL)
593 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
595 /* Visit each PHI on the destination side of this abnormal
596 edge, and attempt to coalesce the argument with the result. */
597 var = PHI_RESULT (phi);
598 x = var_to_partition (map, var);
600 /* Ignore results which are not relevant. */
601 if (x == NO_PARTITION)
604 tmp = PHI_ARG_DEF (phi, e->dest_idx);
605 #ifdef ENABLE_CHECKING
606 if (!phi_ssa_name_p (tmp))
608 print_exprs_edge (stderr, e,
609 "\nConstant argument in PHI. Can't insert :",
611 internal_error ("SSA corruption");
614 gcc_assert (phi_ssa_name_p (tmp));
616 y = var_to_partition (map, tmp);
617 gcc_assert (x != NO_PARTITION);
618 gcc_assert (y != NO_PARTITION);
619 #ifdef ENABLE_CHECKING
620 if (root_var_find (rv, x) != root_var_find (rv, y))
622 print_exprs_edge (stderr, e, "\nDifferent root vars: ",
623 root_var (rv, root_var_find (rv, x)),
625 root_var (rv, root_var_find (rv, y)));
626 internal_error ("SSA corruption");
629 gcc_assert (root_var_find (rv, x) == root_var_find (rv, y));
634 #ifdef ENABLE_CHECKING
635 if (conflict_graph_conflict_p (graph, x, y))
637 print_exprs_edge (stderr, e, "\n Conflict ",
638 partition_to_var (map, x),
639 " and ", partition_to_var (map, y));
640 internal_error ("SSA corruption");
643 gcc_assert (!conflict_graph_conflict_p (graph, x, y));
646 /* Now map the partitions back to their real variables. */
647 var = partition_to_var (map, x);
648 tmp = partition_to_var (map, y);
649 if (dump_file && (dump_flags & TDF_DETAILS))
651 print_exprs_edge (dump_file, e,
652 "ABNORMAL: Coalescing ",
655 z = var_union (map, var, tmp);
656 #ifdef ENABLE_CHECKING
657 if (z == NO_PARTITION)
659 print_exprs_edge (stderr, e, "\nUnable to coalesce",
660 partition_to_var (map, x), " and ",
661 partition_to_var (map, y));
662 internal_error ("SSA corruption");
665 gcc_assert (z != NO_PARTITION);
667 gcc_assert (z == x || z == y);
669 conflict_graph_merge_regs (graph, x, y);
671 conflict_graph_merge_regs (graph, y, x);
677 /* Reduce the number of live ranges in MAP. Live range information is
678 returned if FLAGS indicates that we are combining temporaries, otherwise
679 NULL is returned. The only partitions which are associated with actual
680 variables at this point are those which are forced to be coalesced for
681 various reason. (live on entry, live across abnormal edges, etc.). */
683 static tree_live_info_p
684 coalesce_ssa_name (var_map map, int flags)
690 tree_live_info_p liveinfo;
692 conflict_graph graph;
694 coalesce_list_p cl = NULL;
696 if (num_var_partitions (map) <= 1)
699 /* If no preference given, use cheap coalescing of all partitions. */
700 if ((flags & (SSANORM_COALESCE_PARTITIONS | SSANORM_USE_COALESCE_LIST)) == 0)
701 flags |= SSANORM_COALESCE_PARTITIONS;
703 liveinfo = calculate_live_on_entry (map);
704 calculate_live_on_exit (liveinfo);
705 rv = root_var_init (map);
707 /* Remove single element variable from the list. */
708 root_var_compact (rv);
710 if (flags & SSANORM_USE_COALESCE_LIST)
712 cl = create_coalesce_list (map);
714 /* Add all potential copies via PHI arguments to the list. */
717 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
719 tree res = PHI_RESULT (phi);
720 int p = var_to_partition (map, res);
721 if (p == NO_PARTITION)
723 for (x = 0; x < (unsigned)PHI_NUM_ARGS (phi); x++)
725 tree arg = PHI_ARG_DEF (phi, x);
728 if (TREE_CODE (arg) != SSA_NAME)
730 if (SSA_NAME_VAR (res) != SSA_NAME_VAR (arg))
732 p2 = var_to_partition (map, PHI_ARG_DEF (phi, x));
733 if (p2 != NO_PARTITION)
734 add_coalesce (cl, p, p2, 1);
739 /* Coalesce all the result decls together. */
742 for (x = 0; x < num_var_partitions (map); x++)
744 tree p = partition_to_var (map, x);
745 if (TREE_CODE (SSA_NAME_VAR(p)) == RESULT_DECL)
747 if (var == NULL_TREE)
753 add_coalesce (cl, i, x, 1);
758 /* Build a conflict graph. */
759 graph = build_tree_conflict_graph (liveinfo, rv, cl);
763 if (dump_file && (dump_flags & TDF_DETAILS))
765 fprintf (dump_file, "Before sorting:\n");
766 dump_coalesce_list (dump_file, cl);
769 sort_coalesce_list (cl);
771 if (dump_file && (dump_flags & TDF_DETAILS))
773 fprintf (dump_file, "\nAfter sorting:\n");
774 dump_coalesce_list (dump_file, cl);
778 /* Put the single element variables back in. */
779 root_var_decompact (rv);
781 /* First, coalesce all live on entry variables to their root variable.
782 This will ensure the first use is coming from the correct location. */
784 live = sbitmap_alloc (num_var_partitions (map));
787 /* Set 'live' vector to indicate live on entry partitions. */
788 num = num_var_partitions (map);
789 for (x = 0 ; x < num; x++)
791 var = partition_to_var (map, x);
792 if (default_def (SSA_NAME_VAR (var)) == var)
796 if ((flags & SSANORM_COMBINE_TEMPS) == 0)
798 delete_tree_live_info (liveinfo);
802 /* Assign root variable as partition representative for each live on entry
804 EXECUTE_IF_SET_IN_SBITMAP (live, 0, x,
806 var = root_var (rv, root_var_find (rv, x));
808 /* If these aren't already coalesced... */
809 if (partition_to_var (map, x) != var)
811 /* This root variable should have not already been assigned
812 to another partition which is not coalesced with this one. */
813 gcc_assert (!ann->out_of_ssa_tag);
815 if (dump_file && (dump_flags & TDF_DETAILS))
817 print_exprs (dump_file, "Must coalesce ",
818 partition_to_var (map, x),
819 " with the root variable ", var, ".\n");
822 change_partition_var (map, var, x);
828 /* Coalesce partitions live across abnormal edges. */
829 coalesce_abnormal_edges (map, graph, rv);
831 if (dump_file && (dump_flags & TDF_DETAILS))
832 dump_var_map (dump_file, map);
834 /* Coalesce partitions. */
835 if (flags & SSANORM_USE_COALESCE_LIST)
836 coalesce_tpa_members (rv, graph, map, cl,
837 ((dump_flags & TDF_DETAILS) ? dump_file
841 if (flags & SSANORM_COALESCE_PARTITIONS)
842 coalesce_tpa_members (rv, graph, map, NULL,
843 ((dump_flags & TDF_DETAILS) ? dump_file
846 delete_coalesce_list (cl);
847 root_var_delete (rv);
848 conflict_graph_delete (graph);
854 /* Take the ssa-name var_map MAP, and assign real variables to each
858 assign_vars (var_map map)
865 rv = root_var_init (map);
869 /* Coalescing may already have forced some partitions to their root
870 variable. Find these and tag them. */
872 num = num_var_partitions (map);
873 for (x = 0; x < num; x++)
875 var = partition_to_var (map, x);
876 if (TREE_CODE (var) != SSA_NAME)
878 /* Coalescing will already have verified that more than one
879 partition doesn't have the same root variable. Simply marked
880 the variable as assigned. */
882 ann->out_of_ssa_tag = 1;
883 if (dump_file && (dump_flags & TDF_DETAILS))
885 fprintf (dump_file, "partition %d has variable ", x);
886 print_generic_expr (dump_file, var, TDF_SLIM);
887 fprintf (dump_file, " assigned to it.\n");
893 num = root_var_num (rv);
894 for (x = 0; x < num; x++)
896 var = root_var (rv, x);
898 for (i = root_var_first_partition (rv, x);
900 i = root_var_next_partition (rv, i))
902 t = partition_to_var (map, i);
904 if (t == var || TREE_CODE (t) != SSA_NAME)
907 rep = var_to_partition (map, t);
909 if (!ann->out_of_ssa_tag)
911 if (dump_file && (dump_flags & TDF_DETAILS))
912 print_exprs (dump_file, "", t, " --> ", var, "\n");
913 change_partition_var (map, var, rep);
917 if (dump_file && (dump_flags & TDF_DETAILS))
918 print_exprs (dump_file, "", t, " not coalesced with ", var,
921 var = create_temp (t);
922 change_partition_var (map, var, rep);
925 if (dump_file && (dump_flags & TDF_DETAILS))
927 fprintf (dump_file, " --> New temp: '");
928 print_generic_expr (dump_file, var, TDF_SLIM);
929 fprintf (dump_file, "'\n");
934 root_var_delete (rv);
938 /* Replace use operand P with whatever variable it has been rewritten to based
939 on the partitions in MAP. EXPR is an optional expression vector over SSA
940 versions which is used to replace P with an expression instead of a variable.
941 If the stmt is changed, return true. */
944 replace_use_variable (var_map map, use_operand_p p, tree *expr)
947 tree var = USE_FROM_PTR (p);
949 /* Check if we are replacing this variable with an expression. */
952 int version = SSA_NAME_VERSION (var);
955 tree new_expr = TREE_OPERAND (expr[version], 1);
956 SET_USE (p, new_expr);
957 /* Clear the stmt's RHS, or GC might bite us. */
958 TREE_OPERAND (expr[version], 1) = NULL_TREE;
963 new_var = var_to_partition_to_var (map, var);
966 SET_USE (p, new_var);
967 set_is_used (new_var);
974 /* Replace def operand DEF_P with whatever variable it has been rewritten to
975 based on the partitions in MAP. EXPR is an optional expression vector over
976 SSA versions which is used to replace DEF_P with an expression instead of a
977 variable. If the stmt is changed, return true. */
980 replace_def_variable (var_map map, def_operand_p def_p, tree *expr)
983 tree var = DEF_FROM_PTR (def_p);
985 /* Check if we are replacing this variable with an expression. */
988 int version = SSA_NAME_VERSION (var);
991 tree new_expr = TREE_OPERAND (expr[version], 1);
992 SET_DEF (def_p, new_expr);
993 /* Clear the stmt's RHS, or GC might bite us. */
994 TREE_OPERAND (expr[version], 1) = NULL_TREE;
999 new_var = var_to_partition_to_var (map, var);
1002 SET_DEF (def_p, new_var);
1003 set_is_used (new_var);
1010 /* Remove any PHI node which is a virtual PHI. */
1013 eliminate_virtual_phis (void)
1020 for (phi = phi_nodes (bb); phi; phi = next)
1022 next = PHI_CHAIN (phi);
1023 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
1025 #ifdef ENABLE_CHECKING
1027 /* There should be no arguments of this PHI which are in
1028 the partition list, or we get incorrect results. */
1029 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1031 tree arg = PHI_ARG_DEF (phi, i);
1032 if (TREE_CODE (arg) == SSA_NAME
1033 && is_gimple_reg (SSA_NAME_VAR (arg)))
1035 fprintf (stderr, "Argument of PHI is not virtual (");
1036 print_generic_expr (stderr, arg, TDF_SLIM);
1037 fprintf (stderr, "), but the result is :");
1038 print_generic_stmt (stderr, phi, TDF_SLIM);
1039 internal_error ("SSA corruption");
1043 remove_phi_node (phi, NULL_TREE, bb);
1050 /* This routine will coalesce variables in MAP of the same type which do not
1051 interfere with each other. LIVEINFO is the live range info for variables
1052 of interest. This will both reduce the memory footprint of the stack, and
1053 allow us to coalesce together local copies of globals and scalarized
1057 coalesce_vars (var_map map, tree_live_info_p liveinfo)
1064 conflict_graph graph;
1066 cl = create_coalesce_list (map);
1068 /* Merge all the live on entry vectors for coalesced partitions. */
1069 for (x = 0; x < num_var_partitions (map); x++)
1071 var = partition_to_var (map, x);
1072 p = var_to_partition (map, var);
1074 live_merge_and_clear (liveinfo, p, x);
1077 /* When PHI nodes are turned into copies, the result of each PHI node
1078 becomes live on entry to the block. Mark these now. */
1084 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1086 p = var_to_partition (map, PHI_RESULT (phi));
1088 /* Skip virtual PHI nodes. */
1089 if (p == (unsigned)NO_PARTITION)
1092 make_live_on_entry (liveinfo, bb, p);
1094 /* Each argument is a potential copy operation. Add any arguments
1095 which are not coalesced to the result to the coalesce list. */
1096 for (x = 0; x < (unsigned)PHI_NUM_ARGS (phi); x++)
1098 arg = PHI_ARG_DEF (phi, x);
1099 if (!phi_ssa_name_p (arg))
1101 p2 = var_to_partition (map, arg);
1102 if (p2 == (unsigned)NO_PARTITION)
1105 add_coalesce (cl, p, p2, 1);
1111 /* Re-calculate live on exit info. */
1112 calculate_live_on_exit (liveinfo);
1114 if (dump_file && (dump_flags & TDF_DETAILS))
1116 fprintf (dump_file, "Live range info for variable memory coalescing.\n");
1117 dump_live_info (dump_file, liveinfo, LIVEDUMP_ALL);
1119 fprintf (dump_file, "Coalesce list from phi nodes:\n");
1120 dump_coalesce_list (dump_file, cl);
1124 tv = type_var_init (map);
1126 type_var_dump (dump_file, tv);
1127 type_var_compact (tv);
1129 type_var_dump (dump_file, tv);
1131 graph = build_tree_conflict_graph (liveinfo, tv, cl);
1133 type_var_decompact (tv);
1134 if (dump_file && (dump_flags & TDF_DETAILS))
1136 fprintf (dump_file, "type var list now looks like:n");
1137 type_var_dump (dump_file, tv);
1139 fprintf (dump_file, "Coalesce list after conflict graph build:\n");
1140 dump_coalesce_list (dump_file, cl);
1143 sort_coalesce_list (cl);
1144 if (dump_file && (dump_flags & TDF_DETAILS))
1146 fprintf (dump_file, "Coalesce list after sorting:\n");
1147 dump_coalesce_list (dump_file, cl);
1150 coalesce_tpa_members (tv, graph, map, cl,
1151 ((dump_flags & TDF_DETAILS) ? dump_file : NULL));
1153 type_var_delete (tv);
1154 delete_coalesce_list (cl);
1158 /* Temporary Expression Replacement (TER)
1160 Replace SSA version variables during out-of-ssa with their defining
1161 expression if there is only one use of the variable.
1163 A pass is made through the function, one block at a time. No cross block
1164 information is tracked.
1166 Variables which only have one use, and whose defining stmt is considered
1167 a replaceable expression (see check_replaceable) are entered into
1168 consideration by adding a list of dependent partitions to the version_info
1169 vector for that ssa_name_version. This information comes from the partition
1170 mapping for each USE. At the same time, the partition_dep_list vector for
1171 these partitions have this version number entered into their lists.
1173 When the use of a replaceable ssa_variable is encountered, the dependence
1174 list in version_info[] is moved to the "pending_dependence" list in case
1175 the current expression is also replaceable. (To be determined later in
1176 processing this stmt.) version_info[] for the version is then updated to
1177 point to the defining stmt and the 'replaceable' bit is set.
1179 Any partition which is defined by a statement 'kills' any expression which
1180 is dependent on this partition. Every ssa version in the partitions'
1181 dependence list is removed from future consideration.
1183 All virtual references are lumped together. Any expression which is
1184 dependent on any virtual variable (via a VUSE) has a dependence added
1185 to the special partition defined by VIRTUAL_PARTITION.
1187 Whenever a V_MAY_DEF is seen, all expressions dependent this
1188 VIRTUAL_PARTITION are removed from consideration.
1190 At the end of a basic block, all expression are removed from consideration
1191 in preparation for the next block.
1193 The end result is a vector over SSA_NAME_VERSION which is passed back to
1194 rewrite_out_of_ssa. As the SSA variables are being rewritten, instead of
1195 replacing the SSA_NAME tree element with the partition it was assigned,
1196 it is replaced with the RHS of the defining expression. */
1199 /* Dependency list element. This can contain either a partition index or a
1200 version number, depending on which list it is in. */
1202 typedef struct value_expr_d
1205 struct value_expr_d *next;
1209 /* Temporary Expression Replacement (TER) table information. */
1211 typedef struct temp_expr_table_d
1214 void **version_info;
1215 value_expr_p *partition_dep_list;
1217 bool saw_replaceable;
1218 int virtual_partition;
1219 bitmap partition_in_use;
1220 value_expr_p free_list;
1221 value_expr_p pending_dependence;
1222 } *temp_expr_table_p;
1224 /* Used to indicate a dependency on V_MAY_DEFs. */
1225 #define VIRTUAL_PARTITION(table) (table->virtual_partition)
1227 static temp_expr_table_p new_temp_expr_table (var_map);
1228 static tree *free_temp_expr_table (temp_expr_table_p);
1229 static inline value_expr_p new_value_expr (temp_expr_table_p);
1230 static inline void free_value_expr (temp_expr_table_p, value_expr_p);
1231 static inline value_expr_p find_value_in_list (value_expr_p, int,
1233 static inline void add_value_to_list (temp_expr_table_p, value_expr_p *, int);
1234 static inline void add_info_to_list (temp_expr_table_p, value_expr_p *,
1236 static value_expr_p remove_value_from_list (value_expr_p *, int);
1237 static void add_dependance (temp_expr_table_p, int, tree);
1238 static bool check_replaceable (temp_expr_table_p, tree);
1239 static void finish_expr (temp_expr_table_p, int, bool);
1240 static void mark_replaceable (temp_expr_table_p, tree);
1241 static inline void kill_expr (temp_expr_table_p, int, bool);
1242 static inline void kill_virtual_exprs (temp_expr_table_p, bool);
1243 static void find_replaceable_in_bb (temp_expr_table_p, basic_block);
1244 static tree *find_replaceable_exprs (var_map);
1245 static void dump_replaceable_exprs (FILE *, tree *);
1248 /* Create a new TER table for MAP. */
1250 static temp_expr_table_p
1251 new_temp_expr_table (var_map map)
1253 temp_expr_table_p t;
1255 t = (temp_expr_table_p) xmalloc (sizeof (struct temp_expr_table_d));
1258 t->version_info = xcalloc (num_ssa_names + 1, sizeof (void *));
1259 t->partition_dep_list = xcalloc (num_var_partitions (map) + 1,
1260 sizeof (value_expr_p));
1262 t->replaceable = BITMAP_ALLOC (NULL);
1263 t->partition_in_use = BITMAP_ALLOC (NULL);
1265 t->saw_replaceable = false;
1266 t->virtual_partition = num_var_partitions (map);
1267 t->free_list = NULL;
1268 t->pending_dependence = NULL;
1274 /* Free TER table T. If there are valid replacements, return the expression
1278 free_temp_expr_table (temp_expr_table_p t)
1283 #ifdef ENABLE_CHECKING
1285 for (x = 0; x <= num_var_partitions (t->map); x++)
1286 gcc_assert (!t->partition_dep_list[x]);
1289 while ((p = t->free_list))
1291 t->free_list = p->next;
1295 BITMAP_FREE (t->partition_in_use);
1296 BITMAP_FREE (t->replaceable);
1298 free (t->partition_dep_list);
1299 if (t->saw_replaceable)
1300 ret = (tree *)t->version_info;
1302 free (t->version_info);
1309 /* Allocate a new value list node. Take it from the free list in TABLE if
1312 static inline value_expr_p
1313 new_value_expr (temp_expr_table_p table)
1316 if (table->free_list)
1318 p = table->free_list;
1319 table->free_list = p->next;
1322 p = (value_expr_p) xmalloc (sizeof (struct value_expr_d));
1328 /* Add value list node P to the free list in TABLE. */
1331 free_value_expr (temp_expr_table_p table, value_expr_p p)
1333 p->next = table->free_list;
1334 table->free_list = p;
1338 /* Find VALUE if it's in LIST. Return a pointer to the list object if found,
1339 else return NULL. If LAST_PTR is provided, it will point to the previous
1340 item upon return, or NULL if this is the first item in the list. */
1342 static inline value_expr_p
1343 find_value_in_list (value_expr_p list, int value, value_expr_p *last_ptr)
1346 value_expr_p last = NULL;
1348 for (curr = list; curr; last = curr, curr = curr->next)
1350 if (curr->value == value)
1359 /* Add VALUE to LIST, if it isn't already present. TAB is the expression
1363 add_value_to_list (temp_expr_table_p tab, value_expr_p *list, int value)
1367 if (!find_value_in_list (*list, value, NULL))
1369 info = new_value_expr (tab);
1370 info->value = value;
1377 /* Add value node INFO if it's value isn't already in LIST. Free INFO if
1378 it is already in the list. TAB is the expression table. */
1381 add_info_to_list (temp_expr_table_p tab, value_expr_p *list, value_expr_p info)
1383 if (find_value_in_list (*list, info->value, NULL))
1384 free_value_expr (tab, info);
1393 /* Look for VALUE in LIST. If found, remove it from the list and return it's
1397 remove_value_from_list (value_expr_p *list, int value)
1399 value_expr_p info, last;
1401 info = find_value_in_list (*list, value, &last);
1407 last->next = info->next;
1413 /* Add a dependency between the def of ssa VERSION and VAR. If VAR is
1414 replaceable by an expression, add a dependence each of the elements of the
1415 expression. These are contained in the pending list. TAB is the
1416 expression table. */
1419 add_dependance (temp_expr_table_p tab, int version, tree var)
1424 i = SSA_NAME_VERSION (var);
1425 if (bitmap_bit_p (tab->replaceable, i))
1427 /* This variable is being substituted, so use whatever dependences
1428 were queued up when we marked this as replaceable earlier. */
1429 while ((info = tab->pending_dependence))
1431 tab->pending_dependence = info->next;
1432 /* Get the partition this variable was dependent on. Reuse this
1433 object to represent the current expression instead. */
1435 info->value = version;
1436 add_info_to_list (tab, &(tab->partition_dep_list[x]), info);
1437 add_value_to_list (tab,
1438 (value_expr_p *)&(tab->version_info[version]), x);
1439 bitmap_set_bit (tab->partition_in_use, x);
1444 i = var_to_partition (tab->map, var);
1445 gcc_assert (i != NO_PARTITION);
1446 add_value_to_list (tab, &(tab->partition_dep_list[i]), version);
1447 add_value_to_list (tab,
1448 (value_expr_p *)&(tab->version_info[version]), i);
1449 bitmap_set_bit (tab->partition_in_use, i);
1454 /* Check if expression STMT is suitable for replacement in table TAB. If so,
1455 create an expression entry. Return true if this stmt is replaceable. */
1458 check_replaceable (temp_expr_table_p tab, tree stmt)
1461 vuse_optype vuseops;
1465 int num_use_ops, version;
1466 var_map map = tab->map;
1470 if (TREE_CODE (stmt) != MODIFY_EXPR)
1473 ann = stmt_ann (stmt);
1474 defs = DEF_OPS (ann);
1476 /* Punt if there is more than 1 def, or more than 1 use. */
1477 if (NUM_DEFS (defs) != 1)
1479 def = DEF_OP (defs, 0);
1480 if (version_ref_count (map, def) != 1)
1483 /* There must be no V_MAY_DEFS. */
1484 if (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) != 0)
1487 /* There must be no V_MUST_DEFS. */
1488 if (NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) != 0)
1491 /* Float expressions must go through memory if float-store is on. */
1492 if (flag_float_store && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1))))
1495 /* Calls to functions with side-effects cannot be replaced. */
1496 if ((call_expr = get_call_expr_in (stmt)) != NULL_TREE)
1498 int call_flags = call_expr_flags (call_expr);
1499 if (TREE_SIDE_EFFECTS (call_expr)
1500 && !(call_flags & (ECF_PURE | ECF_CONST | ECF_NORETURN)))
1504 uses = USE_OPS (ann);
1505 num_use_ops = NUM_USES (uses);
1506 vuseops = VUSE_OPS (ann);
1508 /* Any expression which has no virtual operands and no real operands
1509 should have been propagated if it's possible to do anything with them.
1510 If this happens here, it probably exists that way for a reason, so we
1511 won't touch it. An example is:
1513 There are no virtual uses nor any real uses, so we just leave this
1514 alone to be safe. */
1516 if (num_use_ops == 0 && NUM_VUSES (vuseops) == 0)
1519 version = SSA_NAME_VERSION (def);
1521 /* Add this expression to the dependency list for each use partition. */
1522 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
1524 add_dependance (tab, version, var);
1527 /* If there are VUSES, add a dependence on virtual defs. */
1528 if (NUM_VUSES (vuseops) != 0)
1530 add_value_to_list (tab, (value_expr_p *)&(tab->version_info[version]),
1531 VIRTUAL_PARTITION (tab));
1532 add_value_to_list (tab,
1533 &(tab->partition_dep_list[VIRTUAL_PARTITION (tab)]),
1535 bitmap_set_bit (tab->partition_in_use, VIRTUAL_PARTITION (tab));
1542 /* This function will remove the expression for VERSION from replacement
1543 consideration.n table TAB If 'replace' is true, it is marked as
1544 replaceable, otherwise not. */
1547 finish_expr (temp_expr_table_p tab, int version, bool replace)
1549 value_expr_p info, tmp;
1552 /* Remove this expression from its dependent lists. The partition dependence
1553 list is retained and transfered later to whomever uses this version. */
1554 for (info = (value_expr_p) tab->version_info[version]; info; info = tmp)
1556 partition = info->value;
1557 gcc_assert (tab->partition_dep_list[partition]);
1558 tmp = remove_value_from_list (&(tab->partition_dep_list[partition]),
1561 free_value_expr (tab, tmp);
1562 /* Only clear the bit when the dependency list is emptied via
1563 a replacement. Otherwise kill_expr will take care of it. */
1564 if (!(tab->partition_dep_list[partition]) && replace)
1565 bitmap_clear_bit (tab->partition_in_use, partition);
1568 free_value_expr (tab, info);
1573 tab->saw_replaceable = true;
1574 bitmap_set_bit (tab->replaceable, version);
1578 gcc_assert (!bitmap_bit_p (tab->replaceable, version));
1579 tab->version_info[version] = NULL;
1584 /* Mark the expression associated with VAR as replaceable, and enter
1585 the defining stmt into the version_info table TAB. */
1588 mark_replaceable (temp_expr_table_p tab, tree var)
1591 int version = SSA_NAME_VERSION (var);
1592 finish_expr (tab, version, true);
1594 /* Move the dependence list to the pending list. */
1595 if (tab->version_info[version])
1597 info = (value_expr_p) tab->version_info[version];
1598 for ( ; info->next; info = info->next)
1600 info->next = tab->pending_dependence;
1601 tab->pending_dependence = (value_expr_p)tab->version_info[version];
1604 tab->version_info[version] = SSA_NAME_DEF_STMT (var);
1608 /* This function marks any expression in TAB which is dependent on PARTITION
1609 as NOT replaceable. CLEAR_BIT is used to determine whether partition_in_use
1610 should have its bit cleared. Since this routine can be called within an
1611 EXECUTE_IF_SET_IN_BITMAP, the bit can't always be cleared. */
1614 kill_expr (temp_expr_table_p tab, int partition, bool clear_bit)
1618 /* Mark every active expr dependent on this var as not replaceable. */
1619 while ((ptr = tab->partition_dep_list[partition]) != NULL)
1620 finish_expr (tab, ptr->value, false);
1623 bitmap_clear_bit (tab->partition_in_use, partition);
1627 /* This function kills all expressions in TAB which are dependent on virtual
1628 DEFs. CLEAR_BIT determines whether partition_in_use gets cleared. */
1631 kill_virtual_exprs (temp_expr_table_p tab, bool clear_bit)
1633 kill_expr (tab, VIRTUAL_PARTITION (tab), clear_bit);
1637 /* This function processes basic block BB, and looks for variables which can
1638 be replaced by their expressions. Results are stored in TAB. */
1641 find_replaceable_in_bb (temp_expr_table_p tab, basic_block bb)
1643 block_stmt_iterator bsi;
1647 var_map map = tab->map;
1651 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1653 stmt = bsi_stmt (bsi);
1654 ann = stmt_ann (stmt);
1656 /* Determine if this stmt finishes an existing expression. */
1657 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_USE)
1659 if (tab->version_info[SSA_NAME_VERSION (def)])
1661 bool same_root_var = false;
1665 /* See if the root variables are the same. If they are, we
1666 do not want to do the replacement to avoid problems with
1667 code size, see PR tree-optimization/17549. */
1668 FOR_EACH_SSA_TREE_OPERAND (def2, stmt, iter2, SSA_OP_DEF)
1669 if (SSA_NAME_VAR (def) == SSA_NAME_VAR (def2))
1671 same_root_var = true;
1675 /* Mark expression as replaceable unless stmt is volatile
1676 or DEF sets the same root variable as STMT. */
1677 if (!ann->has_volatile_ops && !same_root_var)
1678 mark_replaceable (tab, def);
1680 finish_expr (tab, SSA_NAME_VERSION (def), false);
1684 /* Next, see if this stmt kills off an active expression. */
1685 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
1687 partition = var_to_partition (map, def);
1688 if (partition != NO_PARTITION && tab->partition_dep_list[partition])
1689 kill_expr (tab, partition, true);
1692 /* Now see if we are creating a new expression or not. */
1693 if (!ann->has_volatile_ops)
1694 check_replaceable (tab, stmt);
1696 /* Free any unused dependency lists. */
1697 while ((p = tab->pending_dependence))
1699 tab->pending_dependence = p->next;
1700 free_value_expr (tab, p);
1703 /* A V_MAY_DEF kills any expression using a virtual operand. */
1704 if (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) > 0)
1705 kill_virtual_exprs (tab, true);
1707 /* A V_MUST_DEF kills any expression using a virtual operand. */
1708 if (NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) > 0)
1709 kill_virtual_exprs (tab, true);
1714 /* This function is the driver routine for replacement of temporary expressions
1715 in the SSA->normal phase, operating on MAP. If there are replaceable
1716 expressions, a table is returned which maps SSA versions to the
1717 expressions they should be replaced with. A NULL_TREE indicates no
1718 replacement should take place. If there are no replacements at all,
1719 NULL is returned by the function, otherwise an expression vector indexed
1720 by SSA_NAME version numbers. */
1723 find_replaceable_exprs (var_map map)
1727 temp_expr_table_p table;
1730 table = new_temp_expr_table (map);
1735 find_replaceable_in_bb (table, bb);
1736 EXECUTE_IF_SET_IN_BITMAP ((table->partition_in_use), 0, i, bi)
1738 kill_expr (table, i, false);
1742 ret = free_temp_expr_table (table);
1747 /* Dump TER expression table EXPR to file F. */
1750 dump_replaceable_exprs (FILE *f, tree *expr)
1754 fprintf (f, "\nReplacing Expressions\n");
1755 for (x = 0; x < (int)num_ssa_names + 1; x++)
1759 var = DEF_OP (STMT_DEF_OPS (stmt), 0);
1760 print_generic_expr (f, var, TDF_SLIM);
1761 fprintf (f, " replace with --> ");
1762 print_generic_expr (f, TREE_OPERAND (stmt, 1), TDF_SLIM);
1769 /* Helper function for discover_nonconstant_array_refs.
1770 Look for ARRAY_REF nodes with non-constant indexes and mark them
1774 discover_nonconstant_array_refs_r (tree * tp, int *walk_subtrees,
1775 void *data ATTRIBUTE_UNUSED)
1779 if (IS_TYPE_OR_DECL_P (t))
1781 else if (TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
1783 while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
1784 && is_gimple_min_invariant (TREE_OPERAND (t, 1))
1785 && (!TREE_OPERAND (t, 2)
1786 || is_gimple_min_invariant (TREE_OPERAND (t, 2))))
1787 || (TREE_CODE (t) == COMPONENT_REF
1788 && (!TREE_OPERAND (t,2)
1789 || is_gimple_min_invariant (TREE_OPERAND (t, 2))))
1790 || TREE_CODE (t) == BIT_FIELD_REF
1791 || TREE_CODE (t) == REALPART_EXPR
1792 || TREE_CODE (t) == IMAGPART_EXPR
1793 || TREE_CODE (t) == VIEW_CONVERT_EXPR
1794 || TREE_CODE (t) == NOP_EXPR
1795 || TREE_CODE (t) == CONVERT_EXPR)
1796 t = TREE_OPERAND (t, 0);
1798 if (TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
1800 t = get_base_address (t);
1801 if (t && DECL_P (t))
1802 TREE_ADDRESSABLE (t) = 1;
1812 /* RTL expansion is not able to compile array references with variable
1813 offsets for arrays stored in single register. Discover such
1814 expressions and mark variables as addressable to avoid this
1818 discover_nonconstant_array_refs (void)
1821 block_stmt_iterator bsi;
1825 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1826 walk_tree (bsi_stmt_ptr (bsi), discover_nonconstant_array_refs_r,
1832 /* This function will rewrite the current program using the variable mapping
1833 found in MAP. If the replacement vector VALUES is provided, any
1834 occurrences of partitions with non-null entries in the vector will be
1835 replaced with the expression in the vector instead of its mapped
1839 rewrite_trees (var_map map, tree *values)
1843 block_stmt_iterator si;
1848 #ifdef ENABLE_CHECKING
1849 /* Search for PHIs where the destination has no partition, but one
1850 or more arguments has a partition. This should not happen and can
1851 create incorrect code. */
1856 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1858 tree T0 = var_to_partition_to_var (map, PHI_RESULT (phi));
1860 if (T0 == NULL_TREE)
1864 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1866 tree arg = PHI_ARG_DEF (phi, i);
1868 if (TREE_CODE (arg) == SSA_NAME
1869 && var_to_partition (map, arg) != NO_PARTITION)
1871 fprintf (stderr, "Argument of PHI is in a partition :(");
1872 print_generic_expr (stderr, arg, TDF_SLIM);
1873 fprintf (stderr, "), but the result is not :");
1874 print_generic_stmt (stderr, phi, TDF_SLIM);
1875 internal_error ("SSA corruption");
1883 /* Replace PHI nodes with any required copies. */
1884 g = new_elim_graph (map->num_partitions);
1888 for (si = bsi_start (bb); !bsi_end_p (si); )
1890 size_t num_uses, num_defs;
1893 tree stmt = bsi_stmt (si);
1894 use_operand_p use_p;
1895 def_operand_p def_p;
1896 int remove = 0, is_copy = 0;
1900 get_stmt_operands (stmt);
1901 ann = stmt_ann (stmt);
1904 if (TREE_CODE (stmt) == MODIFY_EXPR
1905 && (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME))
1908 uses = USE_OPS (ann);
1909 num_uses = NUM_USES (uses);
1910 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1912 if (replace_use_variable (map, use_p, values))
1916 defs = DEF_OPS (ann);
1917 num_defs = NUM_DEFS (defs);
1919 /* Mark this stmt for removal if it is the list of replaceable
1921 if (values && num_defs == 1)
1923 tree def = DEF_OP (defs, 0);
1925 val = values[SSA_NAME_VERSION (def)];
1931 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
1933 if (replace_def_variable (map, def_p, NULL))
1936 /* If both SSA_NAMEs coalesce to the same variable,
1937 mark the now redundant copy for removal. */
1940 && (DEF_FROM_PTR (def_p) == USE_OP (uses, 0)))
1943 if (changed & !remove)
1947 /* Remove any stmts marked for removal. */
1954 phi = phi_nodes (bb);
1958 FOR_EACH_EDGE (e, ei, bb->preds)
1959 eliminate_phi (e, g);
1963 delete_elim_graph (g);
1967 /* These are the local work structures used to determine the best place to
1968 insert the copies that were placed on edges by the SSA->normal pass.. */
1969 static varray_type edge_leader = NULL;
1970 static varray_type GTY(()) stmt_list = NULL;
1971 static bitmap leader_has_match = NULL;
1972 static edge leader_match = NULL;
1975 /* Pass this function to make_forwarder_block so that all the edges with
1976 matching PENDING_STMT lists to 'curr_stmt_list' get redirected. */
1978 same_stmt_list_p (edge e)
1980 return (e->aux == (PTR) leader_match) ? true : false;
1984 /* Return TRUE if S1 and S2 are equivalent copies. */
1986 identical_copies_p (tree s1, tree s2)
1988 #ifdef ENABLE_CHECKING
1989 gcc_assert (TREE_CODE (s1) == MODIFY_EXPR);
1990 gcc_assert (TREE_CODE (s2) == MODIFY_EXPR);
1991 gcc_assert (DECL_P (TREE_OPERAND (s1, 0)));
1992 gcc_assert (DECL_P (TREE_OPERAND (s2, 0)));
1995 if (TREE_OPERAND (s1, 0) != TREE_OPERAND (s2, 0))
1998 s1 = TREE_OPERAND (s1, 1);
1999 s2 = TREE_OPERAND (s2, 1);
2008 /* Compare the PENDING_STMT list for two edges, and return true if the lists
2009 contain the same sequence of copies. */
2012 identical_stmt_lists_p (edge e1, edge e2)
2014 tree t1 = PENDING_STMT (e1);
2015 tree t2 = PENDING_STMT (e2);
2016 tree_stmt_iterator tsi1, tsi2;
2018 gcc_assert (TREE_CODE (t1) == STATEMENT_LIST);
2019 gcc_assert (TREE_CODE (t2) == STATEMENT_LIST);
2021 for (tsi1 = tsi_start (t1), tsi2 = tsi_start (t2);
2022 !tsi_end_p (tsi1) && !tsi_end_p (tsi2);
2023 tsi_next (&tsi1), tsi_next (&tsi2))
2025 if (!identical_copies_p (tsi_stmt (tsi1), tsi_stmt (tsi2)))
2029 if (!tsi_end_p (tsi1) || ! tsi_end_p (tsi2))
2036 /* Look at all the incoming edges to block BB, and decide where the best place
2037 to insert the stmts on each edge are, and perform those insertions. Output
2038 any debug information to DEBUG_FILE. Return true if anything other than a
2039 standard edge insertion is done. */
2042 analyze_edges_for_bb (basic_block bb, FILE *debug_file)
2048 bool have_opportunity;
2049 block_stmt_iterator bsi;
2051 edge single_edge = NULL;
2056 /* Blocks which contain at least one abnormal edge cannot use
2057 make_forwarder_block. Look for these blocks, and commit any PENDING_STMTs
2058 found on edges in these block. */
2059 have_opportunity = true;
2060 FOR_EACH_EDGE (e, ei, bb->preds)
2061 if (e->flags & EDGE_ABNORMAL)
2063 have_opportunity = false;
2067 if (!have_opportunity)
2069 FOR_EACH_EDGE (e, ei, bb->preds)
2070 if (PENDING_STMT (e))
2071 bsi_commit_one_edge_insert (e, NULL);
2074 /* Find out how many edges there are with interesting pending stmts on them.
2075 Commit the stmts on edges we are not interested in. */
2076 FOR_EACH_EDGE (e, ei, bb->preds)
2078 if (PENDING_STMT (e))
2080 gcc_assert (!(e->flags & EDGE_ABNORMAL));
2081 if (e->flags & EDGE_FALLTHRU)
2083 bsi = bsi_start (e->src);
2084 if (!bsi_end_p (bsi))
2086 stmt = bsi_stmt (bsi);
2088 gcc_assert (stmt != NULL_TREE);
2089 is_label = (TREE_CODE (stmt) == LABEL_EXPR);
2090 /* Punt if it has non-label stmts, or isn't local. */
2091 if (!is_label || DECL_NONLOCAL (TREE_OPERAND (stmt, 0))
2092 || !bsi_end_p (bsi))
2094 bsi_commit_one_edge_insert (e, NULL);
2104 /* If there aren't at least 2 edges, no sharing will happen. */
2108 bsi_commit_one_edge_insert (single_edge, NULL);
2112 /* Ensure that we have empty worklists. */
2113 if (edge_leader == NULL)
2115 VARRAY_EDGE_INIT (edge_leader, 25, "edge_leader");
2116 VARRAY_TREE_INIT (stmt_list, 25, "stmt_list");
2117 leader_has_match = BITMAP_ALLOC (NULL);
2121 #ifdef ENABLE_CHECKING
2122 gcc_assert (VARRAY_ACTIVE_SIZE (edge_leader) == 0);
2123 gcc_assert (VARRAY_ACTIVE_SIZE (stmt_list) == 0);
2124 gcc_assert (bitmap_empty_p (leader_has_match));
2128 /* Find the "leader" block for each set of unique stmt lists. Preference is
2129 given to FALLTHRU blocks since they would need a GOTO to arrive at another
2130 block. The leader edge destination is the block which all the other edges
2131 with the same stmt list will be redirected to. */
2132 have_opportunity = false;
2133 FOR_EACH_EDGE (e, ei, bb->preds)
2135 if (PENDING_STMT (e))
2139 /* Look for the same stmt list in edge leaders list. */
2140 for (x = 0; x < VARRAY_ACTIVE_SIZE (edge_leader); x++)
2142 edge leader = VARRAY_EDGE (edge_leader, x);
2143 if (identical_stmt_lists_p (leader, e))
2145 /* Give this edge the same stmt list pointer. */
2146 PENDING_STMT (e) = NULL;
2148 bitmap_set_bit (leader_has_match, x);
2149 have_opportunity = found = true;
2154 /* If no similar stmt list, add this edge to the leader list. */
2157 VARRAY_PUSH_EDGE (edge_leader, e);
2158 VARRAY_PUSH_TREE (stmt_list, PENDING_STMT (e));
2163 /* If there are no similar lists, just issue the stmts. */
2164 if (!have_opportunity)
2166 for (x = 0; x < VARRAY_ACTIVE_SIZE (edge_leader); x++)
2167 bsi_commit_one_edge_insert (VARRAY_EDGE (edge_leader, x), NULL);
2168 VARRAY_POP_ALL (edge_leader);
2169 VARRAY_POP_ALL (stmt_list);
2170 bitmap_clear (leader_has_match);
2176 fprintf (debug_file, "\nOpportunities in BB %d for stmt/block reduction:\n",
2180 /* For each common list, create a forwarding block and issue the stmt's
2182 for (x = 0 ; x < VARRAY_ACTIVE_SIZE (edge_leader); x++)
2183 if (bitmap_bit_p (leader_has_match, x))
2185 edge new_edge, leader_edge;
2186 block_stmt_iterator bsi;
2187 tree curr_stmt_list;
2189 leader_match = leader_edge = VARRAY_EDGE (edge_leader, x);
2191 /* The tree_* cfg manipulation routines use the PENDING_EDGE field
2192 for various PHI manipulations, so it gets cleared whhen calls are
2193 made to make_forwarder_block(). So make sure the edge is clear,
2194 and use the saved stmt list. */
2195 PENDING_STMT (leader_edge) = NULL;
2196 leader_edge->aux = leader_edge;
2197 curr_stmt_list = VARRAY_TREE (stmt_list, x);
2199 new_edge = make_forwarder_block (leader_edge->dest, same_stmt_list_p,
2201 bb = new_edge->dest;
2204 fprintf (debug_file, "Splitting BB %d for Common stmt list. ",
2205 leader_edge->dest->index);
2206 fprintf (debug_file, "Original block is now BB%d.\n", bb->index);
2207 print_generic_stmt (debug_file, curr_stmt_list, TDF_VOPS);
2210 FOR_EACH_EDGE (e, ei, new_edge->src->preds)
2214 fprintf (debug_file, " Edge (%d->%d) lands here.\n",
2215 e->src->index, e->dest->index);
2218 bsi = bsi_last (leader_edge->dest);
2219 bsi_insert_after (&bsi, curr_stmt_list, BSI_NEW_STMT);
2221 leader_match = NULL;
2222 /* We should never get a new block now. */
2226 e = VARRAY_EDGE (edge_leader, x);
2227 PENDING_STMT (e) = VARRAY_TREE (stmt_list, x);
2228 bsi_commit_one_edge_insert (e, NULL);
2232 /* Clear the working data structures. */
2233 VARRAY_POP_ALL (edge_leader);
2234 VARRAY_POP_ALL (stmt_list);
2235 bitmap_clear (leader_has_match);
2241 /* This function will analyze the insertions which were performed on edges,
2242 and decide whether they should be left on that edge, or whether it is more
2243 efficient to emit some subset of them in a single block. All stmts are
2244 inserted somewhere, and if non-NULL, debug information is printed via
2248 perform_edge_inserts (FILE *dump_file)
2251 bool changed = false;
2254 fprintf(dump_file, "Analyzing Edge Insertions.\n");
2257 changed |= analyze_edges_for_bb (bb, dump_file);
2259 changed |= analyze_edges_for_bb (EXIT_BLOCK_PTR, dump_file);
2261 /* Clear out any tables which were created. */
2263 BITMAP_FREE (leader_has_match);
2267 free_dominance_info (CDI_DOMINATORS);
2268 free_dominance_info (CDI_POST_DOMINATORS);
2271 #ifdef ENABLE_CHECKING
2277 FOR_EACH_EDGE (e, ei, bb->preds)
2279 if (PENDING_STMT (e))
2280 error (" Pending stmts not issued on PRED edge (%d, %d)\n",
2281 e->src->index, e->dest->index);
2283 FOR_EACH_EDGE (e, ei, bb->succs)
2285 if (PENDING_STMT (e))
2286 error (" Pending stmts not issued on SUCC edge (%d, %d)\n",
2287 e->src->index, e->dest->index);
2290 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2292 if (PENDING_STMT (e))
2293 error (" Pending stmts not issued on ENTRY edge (%d, %d)\n",
2294 e->src->index, e->dest->index);
2296 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
2298 if (PENDING_STMT (e))
2299 error (" Pending stmts not issued on EXIT edge (%d, %d)\n",
2300 e->src->index, e->dest->index);
2307 /* Remove the variables specified in MAP from SSA form. Any debug information
2308 is sent to DUMP. FLAGS indicate what options should be used. */
2311 remove_ssa_form (FILE *dump, var_map map, int flags)
2313 tree_live_info_p liveinfo;
2317 tree *values = NULL;
2322 /* If we are not combining temps, don't calculate live ranges for variables
2323 with only one SSA version. */
2324 if ((flags & SSANORM_COMBINE_TEMPS) == 0)
2325 compact_var_map (map, VARMAP_NO_SINGLE_DEFS);
2327 compact_var_map (map, VARMAP_NORMAL);
2329 if (dump_file && (dump_flags & TDF_DETAILS))
2330 dump_var_map (dump_file, map);
2332 liveinfo = coalesce_ssa_name (map, flags);
2334 /* Make sure even single occurrence variables are in the list now. */
2335 if ((flags & SSANORM_COMBINE_TEMPS) == 0)
2336 compact_var_map (map, VARMAP_NORMAL);
2338 if (dump_file && (dump_flags & TDF_DETAILS))
2340 fprintf (dump_file, "After Coalescing:\n");
2341 dump_var_map (dump_file, map);
2344 if (flags & SSANORM_PERFORM_TER)
2346 values = find_replaceable_exprs (map);
2347 if (values && dump_file && (dump_flags & TDF_DETAILS))
2348 dump_replaceable_exprs (dump_file, values);
2351 /* Assign real variables to the partitions now. */
2354 if (dump_file && (dump_flags & TDF_DETAILS))
2356 fprintf (dump_file, "After Root variable replacement:\n");
2357 dump_var_map (dump_file, map);
2360 if ((flags & SSANORM_COMBINE_TEMPS) && liveinfo)
2362 coalesce_vars (map, liveinfo);
2363 if (dump_file && (dump_flags & TDF_DETAILS))
2365 fprintf (dump_file, "After variable memory coalescing:\n");
2366 dump_var_map (dump_file, map);
2371 delete_tree_live_info (liveinfo);
2373 rewrite_trees (map, values);
2378 /* Remove phi nodes which have been translated back to real variables. */
2381 for (phi = phi_nodes (bb); phi; phi = next)
2383 next = PHI_CHAIN (phi);
2384 remove_phi_node (phi, NULL_TREE, bb);
2388 /* If any copies were inserted on edges, analyze and insert them now. */
2389 perform_edge_inserts (dump_file);
2394 /* Search every PHI node for arguments associated with backedges which
2395 we can trivially determine will need a copy (the argument is either
2396 not an SSA_NAME or the argument has a different underlying variable
2397 than the PHI result).
2399 Insert a copy from the PHI argument to a new destination at the
2400 end of the block with the backedge to the top of the loop. Update
2401 the PHI argument to reference this new destination. */
2404 insert_backedge_copies (void)
2412 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2414 tree result = PHI_RESULT (phi);
2418 if (!is_gimple_reg (result))
2421 result_var = SSA_NAME_VAR (result);
2422 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
2424 tree arg = PHI_ARG_DEF (phi, i);
2425 edge e = PHI_ARG_EDGE (phi, i);
2427 /* If the argument is not an SSA_NAME, then we will
2428 need a constant initialization. If the argument is
2429 an SSA_NAME with a different underlying variable and
2430 we are not combining temporaries, then we will
2431 need a copy statement. */
2432 if ((e->flags & EDGE_DFS_BACK)
2433 && (TREE_CODE (arg) != SSA_NAME
2434 || (!flag_tree_combine_temps
2435 && SSA_NAME_VAR (arg) != result_var)))
2437 tree stmt, name, last = NULL;
2438 block_stmt_iterator bsi;
2440 bsi = bsi_last (PHI_ARG_EDGE (phi, i)->src);
2441 if (!bsi_end_p (bsi))
2442 last = bsi_stmt (bsi);
2444 /* In theory the only way we ought to get back to the
2445 start of a loop should be with a COND_EXPR or GOTO_EXPR.
2446 However, better safe than sorry.
2448 If the block ends with a control statement or
2449 something that might throw, then we have to
2450 insert this assignment before the last
2451 statement. Else insert it after the last statement. */
2452 if (last && stmt_ends_bb_p (last))
2454 /* If the last statement in the block is the definition
2455 site of the PHI argument, then we can't insert
2456 anything after it. */
2457 if (TREE_CODE (arg) == SSA_NAME
2458 && SSA_NAME_DEF_STMT (arg) == last)
2462 /* Create a new instance of the underlying
2463 variable of the PHI result. */
2464 stmt = build (MODIFY_EXPR, TREE_TYPE (result_var),
2465 NULL, PHI_ARG_DEF (phi, i));
2466 name = make_ssa_name (result_var, stmt);
2467 TREE_OPERAND (stmt, 0) = name;
2469 /* Insert the new statement into the block and update
2471 if (last && stmt_ends_bb_p (last))
2472 bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
2474 bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
2476 SET_PHI_ARG_DEF (phi, i, name);
2483 /* Take the current function out of SSA form, as described in
2484 R. Morgan, ``Building an Optimizing Compiler'',
2485 Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */
2488 rewrite_out_of_ssa (void)
2492 int ssa_flags = SSANORM_USE_COALESCE_LIST;
2494 /* If elimination of a PHI requires inserting a copy on a backedge,
2495 then we will have to split the backedge which has numerous
2496 undesirable performance effects.
2498 A significant number of such cases can be handled here by inserting
2499 copies into the loop itself. */
2500 insert_backedge_copies ();
2502 if (!flag_tree_live_range_split)
2503 ssa_flags |= SSANORM_COALESCE_PARTITIONS;
2505 eliminate_virtual_phis ();
2507 if (dump_file && (dump_flags & TDF_DETAILS))
2508 dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
2510 /* We cannot allow unssa to un-gimplify trees before we instrument them. */
2511 if (flag_tree_ter && !flag_mudflap)
2512 var_flags = SSA_VAR_MAP_REF_COUNT;
2514 map = create_ssa_var_map (var_flags);
2516 if (flag_tree_combine_temps)
2517 ssa_flags |= SSANORM_COMBINE_TEMPS;
2518 if (flag_tree_ter && !flag_mudflap)
2519 ssa_flags |= SSANORM_PERFORM_TER;
2521 remove_ssa_form (dump_file, map, ssa_flags);
2523 if (dump_file && (dump_flags & TDF_DETAILS))
2524 dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
2526 /* Do some cleanups which reduce the amount of data the
2527 tree->rtl expanders deal with. */
2528 cfg_remove_useless_stmts ();
2530 /* Flush out flow graph and SSA data. */
2531 delete_var_map (map);
2533 /* Mark arrays indexed with non-constant indices with TREE_ADDRESSABLE. */
2534 discover_nonconstant_array_refs ();
2538 /* Define the parameters of the out of SSA pass. */
2540 struct tree_opt_pass pass_del_ssa =
2542 "optimized", /* name */
2544 rewrite_out_of_ssa, /* execute */
2547 0, /* static_pass_number */
2548 TV_TREE_SSA_TO_NORMAL, /* tv_id */
2549 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
2550 0, /* properties_provided */
2551 /* ??? If TER is enabled, we also kill gimple. */
2552 PROP_ssa, /* properties_destroyed */
2553 TODO_verify_ssa | TODO_verify_flow
2554 | TODO_verify_stmts, /* todo_flags_start */
2555 TODO_dump_func | TODO_ggc_collect, /* todo_flags_finish */