1 /* Convert a program in SSA form into Normal form.
2 Copyright (C) 2004 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_REMOVE_ALL_PHIS 0x4
55 #define SSANORM_COALESCE_PARTITIONS 0x8
56 #define SSANORM_USE_COALESCE_LIST 0x10
58 /* Used to hold all the components required to do SSA PHI elimination.
59 The node and pred/succ list is a simple linear list of nodes and
60 edges represented as pairs of nodes.
62 The predecessor and successor list: Nodes are entered in pairs, where
63 [0] ->PRED, [1]->SUCC. All the even indexes in the array represent
64 predecessors, all the odd elements are successors.
67 When implemented as bitmaps, very large programs SSA->Normal times were
68 being dominated by clearing the interference graph.
70 Typically this list of edges is extremely small since it only includes
71 PHI results and uses from a single edge which have not coalesced with
72 each other. This means that no virtual PHI nodes are included, and
73 empirical evidence suggests that the number of edges rarely exceed
74 3, and in a bootstrap of GCC, the maximum size encountered was 7.
75 This also limits the number of possible nodes that are involved to
76 rarely more than 6, and in the bootstrap of gcc, the maximum number
77 of nodes encountered was 12. */
79 typedef struct _elim_graph
{
80 /* Size of the elimination vectors. */
83 /* List of nodes in the elimination graph. */
86 /* The predecessor and successor edge list. */
87 varray_type edge_list
;
92 /* Stack for visited nodes. */
95 /* The variable partition map. */
98 /* Edge being eliminated by this graph. */
101 /* List of constant copies to emit. These are pushed on in pairs. */
102 varray_type const_copies
;
106 /* Local functions. */
107 static tree
create_temp (tree
);
108 static void insert_copy_on_edge (edge
, tree
, tree
);
109 static elim_graph
new_elim_graph (int);
110 static inline void delete_elim_graph (elim_graph
);
111 static inline void clear_elim_graph (elim_graph
);
112 static inline int elim_graph_size (elim_graph
);
113 static inline void elim_graph_add_node (elim_graph
, tree
);
114 static inline void elim_graph_add_edge (elim_graph
, int, int);
115 static inline int elim_graph_remove_succ_edge (elim_graph
, int);
117 static inline void eliminate_name (elim_graph
, tree
);
118 static void eliminate_build (elim_graph
, basic_block
, int);
119 static void elim_forward (elim_graph
, int);
120 static int elim_unvisited_predecessor (elim_graph
, int);
121 static void elim_backward (elim_graph
, int);
122 static void elim_create (elim_graph
, int);
123 static void eliminate_phi (edge
, int, elim_graph
);
124 static tree_live_info_p
coalesce_ssa_name (var_map
, int);
125 static void assign_vars (var_map
);
126 static bool replace_use_variable (var_map
, use_operand_p
, tree
*);
127 static bool replace_def_variable (var_map
, def_operand_p
, tree
*);
128 static void eliminate_virtual_phis (void);
129 static void coalesce_abnormal_edges (var_map
, conflict_graph
, root_var_p
);
130 static void print_exprs (FILE *, const char *, tree
, const char *, tree
,
132 static void print_exprs_edge (FILE *, edge
, const char *, tree
, const char *,
136 /* Create a temporary variable based on the type of variable T. Use T's name
143 const char *name
= NULL
;
146 if (TREE_CODE (t
) == SSA_NAME
)
147 t
= SSA_NAME_VAR (t
);
149 gcc_assert (TREE_CODE (t
) == VAR_DECL
|| TREE_CODE (t
) == PARM_DECL
);
151 type
= TREE_TYPE (t
);
154 name
= IDENTIFIER_POINTER (tmp
);
158 tmp
= create_tmp_var (type
, name
);
159 DECL_ARTIFICIAL (tmp
) = DECL_ARTIFICIAL (t
);
160 add_referenced_tmp_var (tmp
);
162 /* add_referenced_tmp_var will create the annotation and set up some
163 of the flags in the annotation. However, some flags we need to
164 inherit from our original variable. */
165 var_ann (tmp
)->type_mem_tag
= var_ann (t
)->type_mem_tag
;
166 if (is_call_clobbered (t
))
167 mark_call_clobbered (tmp
);
173 /* This helper function fill insert a copy from a constant or variable SRC to
174 variable DEST on edge E. */
177 insert_copy_on_edge (edge e
, tree dest
, tree src
)
181 copy
= build (MODIFY_EXPR
, TREE_TYPE (dest
), dest
, src
);
184 if (TREE_CODE (src
) == ADDR_EXPR
)
185 src
= TREE_OPERAND (src
, 0);
186 if (TREE_CODE (src
) == VAR_DECL
|| TREE_CODE (src
) == PARM_DECL
)
189 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
192 "Inserting a copy on edge BB%d->BB%d :",
195 print_generic_expr (dump_file
, copy
, dump_flags
);
196 fprintf (dump_file
, "\n");
199 bsi_insert_on_edge (e
, copy
);
203 /* Create an elimination graph with SIZE nodes and associated data
207 new_elim_graph (int size
)
209 elim_graph g
= (elim_graph
) xmalloc (sizeof (struct _elim_graph
));
211 VARRAY_TREE_INIT (g
->nodes
, 30, "Elimination Node List");
212 VARRAY_TREE_INIT (g
->const_copies
, 20, "Elimination Constant Copies");
213 VARRAY_INT_INIT (g
->edge_list
, 20, "Elimination Edge List");
214 VARRAY_INT_INIT (g
->stack
, 30, " Elimination Stack");
216 g
->visited
= sbitmap_alloc (size
);
222 /* Empty elimination graph G. */
225 clear_elim_graph (elim_graph g
)
227 VARRAY_POP_ALL (g
->nodes
);
228 VARRAY_POP_ALL (g
->edge_list
);
232 /* Delete elimination graph G. */
235 delete_elim_graph (elim_graph g
)
237 sbitmap_free (g
->visited
);
242 /* Return the number of nodes in graph G. */
245 elim_graph_size (elim_graph g
)
247 return VARRAY_ACTIVE_SIZE (g
->nodes
);
251 /* Add NODE to graph G, if it doesn't exist already. */
254 elim_graph_add_node (elim_graph g
, tree node
)
257 for (x
= 0; x
< elim_graph_size (g
); x
++)
258 if (VARRAY_TREE (g
->nodes
, x
) == node
)
260 VARRAY_PUSH_TREE (g
->nodes
, node
);
264 /* Add the edge PRED->SUCC to graph G. */
267 elim_graph_add_edge (elim_graph g
, int pred
, int succ
)
269 VARRAY_PUSH_INT (g
->edge_list
, pred
);
270 VARRAY_PUSH_INT (g
->edge_list
, succ
);
274 /* Remove an edge from graph G for which NODE is the predecessor, and
275 return the successor node. -1 is returned if there is no such edge. */
278 elim_graph_remove_succ_edge (elim_graph g
, int node
)
282 for (x
= 0; x
< VARRAY_ACTIVE_SIZE (g
->edge_list
); x
+= 2)
283 if (VARRAY_INT (g
->edge_list
, x
) == node
)
285 VARRAY_INT (g
->edge_list
, x
) = -1;
286 y
= VARRAY_INT (g
->edge_list
, x
+ 1);
287 VARRAY_INT (g
->edge_list
, x
+ 1) = -1;
294 /* Find all the nodes in GRAPH which are successors to NODE in the
295 edge list. VAR will hold the partition number found. CODE is the
296 code fragment executed for every node found. */
298 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, CODE) \
302 for (x_ = 0; x_ < VARRAY_ACTIVE_SIZE ((GRAPH)->edge_list); x_ += 2) \
304 y_ = VARRAY_INT ((GRAPH)->edge_list, x_); \
307 (VAR) = VARRAY_INT ((GRAPH)->edge_list, x_ + 1); \
313 /* Find all the nodes which are predecessors of NODE in the edge list for
314 GRAPH. VAR will hold the partition number found. CODE is the
315 code fragment executed for every node found. */
317 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, CODE) \
321 for (x_ = 0; x_ < VARRAY_ACTIVE_SIZE ((GRAPH)->edge_list); x_ += 2) \
323 y_ = VARRAY_INT ((GRAPH)->edge_list, x_ + 1); \
326 (VAR) = VARRAY_INT ((GRAPH)->edge_list, x_); \
332 /* Add T to elimination graph G. */
335 eliminate_name (elim_graph g
, tree T
)
337 elim_graph_add_node (g
, T
);
341 /* Build elimination graph G for basic block BB on incoming PHI edge I. */
344 eliminate_build (elim_graph g
, basic_block B
, int i
)
350 clear_elim_graph (g
);
352 for (phi
= phi_nodes (B
); phi
; phi
= PHI_CHAIN (phi
))
354 T0
= var_to_partition_to_var (g
->map
, PHI_RESULT (phi
));
356 /* Ignore results which are not in partitions. */
360 if (PHI_ARG_EDGE (phi
, i
) == g
->e
)
361 Ti
= PHI_ARG_DEF (phi
, i
);
364 /* On rare occasions, a PHI node may not have the arguments
365 in the same order as all of the other PHI nodes. If they don't
366 match, find the appropriate index here. */
367 pi
= phi_arg_from_edge (phi
, g
->e
);
368 gcc_assert (pi
!= -1);
369 Ti
= PHI_ARG_DEF (phi
, pi
);
372 /* If this argument is a constant, or a SSA_NAME which is being
373 left in SSA form, just queue a copy to be emitted on this
375 if (!phi_ssa_name_p (Ti
)
376 || (TREE_CODE (Ti
) == SSA_NAME
377 && var_to_partition (g
->map
, Ti
) == NO_PARTITION
))
379 /* Save constant copies until all other copies have been emitted
381 VARRAY_PUSH_TREE (g
->const_copies
, T0
);
382 VARRAY_PUSH_TREE (g
->const_copies
, Ti
);
386 Ti
= var_to_partition_to_var (g
->map
, Ti
);
389 eliminate_name (g
, T0
);
390 eliminate_name (g
, Ti
);
391 p0
= var_to_partition (g
->map
, T0
);
392 pi
= var_to_partition (g
->map
, Ti
);
393 elim_graph_add_edge (g
, p0
, pi
);
400 /* Push successors of T onto the elimination stack for G. */
403 elim_forward (elim_graph g
, int T
)
406 SET_BIT (g
->visited
, T
);
407 FOR_EACH_ELIM_GRAPH_SUCC (g
, T
, S
,
409 if (!TEST_BIT (g
->visited
, S
))
412 VARRAY_PUSH_INT (g
->stack
, T
);
416 /* Return 1 if there unvisited predecessors of T in graph G. */
419 elim_unvisited_predecessor (elim_graph g
, int T
)
422 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
,
424 if (!TEST_BIT (g
->visited
, P
))
430 /* Process predecessors first, and insert a copy. */
433 elim_backward (elim_graph g
, int T
)
436 SET_BIT (g
->visited
, T
);
437 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
,
439 if (!TEST_BIT (g
->visited
, P
))
441 elim_backward (g
, P
);
442 insert_copy_on_edge (g
->e
,
443 partition_to_var (g
->map
, P
),
444 partition_to_var (g
->map
, T
));
449 /* Insert required copies for T in graph G. Check for a strongly connected
450 region, and create a temporary to break the cycle if one is found. */
453 elim_create (elim_graph g
, int T
)
458 if (elim_unvisited_predecessor (g
, T
))
460 U
= create_temp (partition_to_var (g
->map
, T
));
461 insert_copy_on_edge (g
->e
, U
, partition_to_var (g
->map
, T
));
462 FOR_EACH_ELIM_GRAPH_PRED (g
, T
, P
,
464 if (!TEST_BIT (g
->visited
, P
))
466 elim_backward (g
, P
);
467 insert_copy_on_edge (g
->e
, partition_to_var (g
->map
, P
), U
);
473 S
= elim_graph_remove_succ_edge (g
, T
);
476 SET_BIT (g
->visited
, T
);
477 insert_copy_on_edge (g
->e
,
478 partition_to_var (g
->map
, T
),
479 partition_to_var (g
->map
, S
));
485 /* Eliminate all the phi nodes on edge E in graph G. I is the usual PHI
486 index that edge E's values are found on. */
489 eliminate_phi (edge e
, int i
, elim_graph g
)
493 basic_block B
= e
->dest
;
495 gcc_assert (i
!= -1);
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
, i
);
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
)
585 /* Code cannot be inserted on abnormal edges. Look for all abnormal
586 edges, and coalesce any PHI results with their arguments across
590 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
591 if (e
->dest
!= EXIT_BLOCK_PTR
&& e
->flags
& EDGE_ABNORMAL
)
592 for (phi
= phi_nodes (e
->dest
); phi
; phi
= PHI_CHAIN (phi
))
594 /* Visit each PHI on the destination side of this abnormal
595 edge, and attempt to coalesce the argument with the result. */
596 var
= PHI_RESULT (phi
);
597 x
= var_to_partition (map
, var
);
599 /* Ignore results which are not relevant. */
600 if (x
== NO_PARTITION
)
603 y
= phi_arg_from_edge (phi
, e
);
604 gcc_assert (y
!= -1);
606 tmp
= PHI_ARG_DEF (phi
, y
);
607 #ifdef ENABLE_CHECKING
608 if (!phi_ssa_name_p (tmp
))
610 print_exprs_edge (stderr
, e
,
611 "\nConstant argument in PHI. Can't insert :",
613 internal_error ("SSA corruption");
616 gcc_assert (phi_ssa_name_p (tmp
));
618 y
= var_to_partition (map
, tmp
);
619 gcc_assert (x
!= NO_PARTITION
);
620 gcc_assert (y
!= NO_PARTITION
);
621 #ifdef ENABLE_CHECKING
622 if (root_var_find (rv
, x
) != root_var_find (rv
, y
))
624 print_exprs_edge (stderr
, e
, "\nDifferent root vars: ",
625 root_var (rv
, root_var_find (rv
, x
)),
627 root_var (rv
, root_var_find (rv
, y
)));
628 internal_error ("SSA corruption");
631 gcc_assert (root_var_find (rv
, x
) == root_var_find (rv
, y
));
636 #ifdef ENABLE_CHECKING
637 if (conflict_graph_conflict_p (graph
, x
, y
))
639 print_exprs_edge (stderr
, e
, "\n Conflict ",
640 partition_to_var (map
, x
),
641 " and ", partition_to_var (map
, y
));
642 internal_error ("SSA corruption");
645 gcc_assert (!conflict_graph_conflict_p (graph
, x
, y
));
648 /* Now map the partitions back to their real variables. */
649 var
= partition_to_var (map
, x
);
650 tmp
= partition_to_var (map
, y
);
651 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
653 print_exprs_edge (dump_file
, e
,
654 "ABNORMAL: Coalescing ",
657 #ifdef ENABLE_CHECKING
658 if (var_union (map
, var
, tmp
) == NO_PARTITION
)
660 print_exprs_edge (stderr
, e
, "\nUnable to coalesce",
661 partition_to_var (map
, x
), " and ",
662 partition_to_var (map
, y
));
663 internal_error ("SSA corruption");
666 gcc_assert (var_union (map
, var
, tmp
) != NO_PARTITION
);
668 conflict_graph_merge_regs (graph
, x
, y
);
674 /* Reduce the number of live ranges in MAP. Live range information is
675 returned if FLAGS indicates that we are combining temporaries, otherwise
676 NULL is returned. The only partitions which are associated with actual
677 variables at this point are those which are forced to be coalesced for
678 various reason. (live on entry, live across abnormal edges, etc.). */
680 static tree_live_info_p
681 coalesce_ssa_name (var_map map
, int flags
)
687 tree_live_info_p liveinfo
;
689 conflict_graph graph
;
691 coalesce_list_p cl
= NULL
;
693 if (num_var_partitions (map
) <= 1)
696 /* If no preference given, use cheap coalescing of all partitions. */
697 if ((flags
& (SSANORM_COALESCE_PARTITIONS
| SSANORM_USE_COALESCE_LIST
)) == 0)
698 flags
|= SSANORM_COALESCE_PARTITIONS
;
700 liveinfo
= calculate_live_on_entry (map
);
701 calculate_live_on_exit (liveinfo
);
702 rv
= root_var_init (map
);
704 /* Remove single element variable from the list. */
705 root_var_compact (rv
);
707 if (flags
& SSANORM_USE_COALESCE_LIST
)
709 cl
= create_coalesce_list (map
);
711 /* Add all potential copies via PHI arguments to the list. */
714 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
716 tree res
= PHI_RESULT (phi
);
717 int p
= var_to_partition (map
, res
);
718 if (p
== NO_PARTITION
)
720 for (x
= 0; x
< PHI_NUM_ARGS (phi
); x
++)
722 tree arg
= PHI_ARG_DEF (phi
, x
);
725 if (TREE_CODE (arg
) != SSA_NAME
)
727 if (SSA_NAME_VAR (res
) != SSA_NAME_VAR (arg
))
729 p2
= var_to_partition (map
, PHI_ARG_DEF (phi
, x
));
730 if (p2
!= NO_PARTITION
)
731 add_coalesce (cl
, p
, p2
, 1);
736 /* Coalesce all the result decls together. */
739 for (x
= 0; x
< num_var_partitions (map
); x
++)
741 tree p
= partition_to_var (map
, x
);
742 if (TREE_CODE (SSA_NAME_VAR(p
)) == RESULT_DECL
)
744 if (var
== NULL_TREE
)
750 add_coalesce (cl
, i
, x
, 1);
755 /* Build a conflict graph. */
756 graph
= build_tree_conflict_graph (liveinfo
, rv
, cl
);
760 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
762 fprintf (dump_file
, "Before sorting:\n");
763 dump_coalesce_list (dump_file
, cl
);
766 sort_coalesce_list (cl
);
768 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
770 fprintf (dump_file
, "\nAfter sorting:\n");
771 dump_coalesce_list (dump_file
, cl
);
775 /* Put the single element variables back in. */
776 root_var_decompact (rv
);
778 /* First, coalesce all live on entry variables to their root variable.
779 This will ensure the first use is coming from the correct location. */
781 live
= sbitmap_alloc (num_var_partitions (map
));
784 /* Set 'live' vector to indicate live on entry partitions. */
785 num
= num_var_partitions (map
);
786 for (x
= 0 ; x
< num
; x
++)
788 var
= partition_to_var (map
, x
);
789 if (default_def (SSA_NAME_VAR (var
)) == var
)
793 if ((flags
& SSANORM_COMBINE_TEMPS
) == 0)
795 delete_tree_live_info (liveinfo
);
799 /* Assign root variable as partition representative for each live on entry
801 EXECUTE_IF_SET_IN_SBITMAP (live
, 0, x
,
803 var
= root_var (rv
, root_var_find (rv
, x
));
805 /* If these aren't already coalesced... */
806 if (partition_to_var (map
, x
) != var
)
808 /* This root variable should have not already been assigned
809 to another partition which is not coalesced with this one. */
810 gcc_assert (!ann
->out_of_ssa_tag
);
812 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
814 print_exprs (dump_file
, "Must coalesce ",
815 partition_to_var (map
, x
),
816 " with the root variable ", var
, ".\n");
819 change_partition_var (map
, var
, x
);
825 /* Coalesce partitions live across abnormal edges. */
826 coalesce_abnormal_edges (map
, graph
, rv
);
828 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
829 dump_var_map (dump_file
, map
);
831 /* Coalesce partitions. */
832 if (flags
& SSANORM_USE_COALESCE_LIST
)
833 coalesce_tpa_members (rv
, graph
, map
, cl
,
834 ((dump_flags
& TDF_DETAILS
) ? dump_file
838 if (flags
& SSANORM_COALESCE_PARTITIONS
)
839 coalesce_tpa_members (rv
, graph
, map
, NULL
,
840 ((dump_flags
& TDF_DETAILS
) ? dump_file
843 delete_coalesce_list (cl
);
844 root_var_delete (rv
);
845 conflict_graph_delete (graph
);
851 /* Take the ssa-name var_map MAP, and assign real variables to each
855 assign_vars (var_map map
)
862 rv
= root_var_init (map
);
866 /* Coalescing may already have forced some partitions to their root
867 variable. Find these and tag them. */
869 num
= num_var_partitions (map
);
870 for (x
= 0; x
< num
; x
++)
872 var
= partition_to_var (map
, x
);
873 if (TREE_CODE (var
) != SSA_NAME
)
875 /* Coalescing will already have verified that more than one
876 partition doesn't have the same root variable. Simply marked
877 the variable as assigned. */
879 ann
->out_of_ssa_tag
= 1;
880 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
882 fprintf (dump_file
, "partition %d has variable ", x
);
883 print_generic_expr (dump_file
, var
, TDF_SLIM
);
884 fprintf (dump_file
, " assigned to it.\n");
890 num
= root_var_num (rv
);
891 for (x
= 0; x
< num
; x
++)
893 var
= root_var (rv
, x
);
895 for (i
= root_var_first_partition (rv
, x
);
897 i
= root_var_next_partition (rv
, i
))
899 t
= partition_to_var (map
, i
);
901 if (t
== var
|| TREE_CODE (t
) != SSA_NAME
)
904 rep
= var_to_partition (map
, t
);
906 if (!ann
->out_of_ssa_tag
)
908 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
909 print_exprs (dump_file
, "", t
, " --> ", var
, "\n");
910 change_partition_var (map
, var
, rep
);
914 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
915 print_exprs (dump_file
, "", t
, " not coalesced with ", var
,
918 var
= create_temp (t
);
919 change_partition_var (map
, var
, rep
);
922 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
924 fprintf (dump_file
, " --> New temp: '");
925 print_generic_expr (dump_file
, var
, TDF_SLIM
);
926 fprintf (dump_file
, "'\n");
931 root_var_delete (rv
);
935 /* Replace use operand P with whatever variable it has been rewritten to based
936 on the partitions in MAP. EXPR is an optional expression vector over SSA
937 versions which is used to replace P with an expression instead of a variable.
938 If the stmt is changed, return true. */
941 replace_use_variable (var_map map
, use_operand_p p
, tree
*expr
)
944 tree var
= USE_FROM_PTR (p
);
946 /* Check if we are replacing this variable with an expression. */
949 int version
= SSA_NAME_VERSION (var
);
952 tree new_expr
= TREE_OPERAND (expr
[version
], 1);
953 SET_USE (p
, new_expr
);
954 /* Clear the stmt's RHS, or GC might bite us. */
955 TREE_OPERAND (expr
[version
], 1) = NULL_TREE
;
960 new_var
= var_to_partition_to_var (map
, var
);
963 SET_USE (p
, new_var
);
964 set_is_used (new_var
);
971 /* Replace def operand DEF_P with whatever variable it has been rewritten to
972 based on the partitions in MAP. EXPR is an optional expression vector over
973 SSA versions which is used to replace DEF_P with an expression instead of a
974 variable. If the stmt is changed, return true. */
977 replace_def_variable (var_map map
, def_operand_p def_p
, tree
*expr
)
980 tree var
= DEF_FROM_PTR (def_p
);
982 /* Check if we are replacing this variable with an expression. */
985 int version
= SSA_NAME_VERSION (var
);
988 tree new_expr
= TREE_OPERAND (expr
[version
], 1);
989 SET_DEF (def_p
, new_expr
);
990 /* Clear the stmt's RHS, or GC might bite us. */
991 TREE_OPERAND (expr
[version
], 1) = NULL_TREE
;
996 new_var
= var_to_partition_to_var (map
, var
);
999 SET_DEF (def_p
, new_var
);
1000 set_is_used (new_var
);
1007 /* Remove any PHI node which is a virtual PHI. */
1010 eliminate_virtual_phis (void)
1017 for (phi
= phi_nodes (bb
); phi
; phi
= next
)
1019 next
= PHI_CHAIN (phi
);
1020 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi
))))
1022 #ifdef ENABLE_CHECKING
1024 /* There should be no arguments of this PHI which are in
1025 the partition list, or we get incorrect results. */
1026 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
1028 tree arg
= PHI_ARG_DEF (phi
, i
);
1029 if (TREE_CODE (arg
) == SSA_NAME
1030 && is_gimple_reg (SSA_NAME_VAR (arg
)))
1032 fprintf (stderr
, "Argument of PHI is not virtual (");
1033 print_generic_expr (stderr
, arg
, TDF_SLIM
);
1034 fprintf (stderr
, "), but the result is :");
1035 print_generic_stmt (stderr
, phi
, TDF_SLIM
);
1036 internal_error ("SSA corruption");
1040 remove_phi_node (phi
, NULL_TREE
, bb
);
1047 /* This routine will coalesce variables in MAP of the same type which do not
1048 interfere with each other. LIVEINFO is the live range info for variables
1049 of interest. This will both reduce the memory footprint of the stack, and
1050 allow us to coalesce together local copies of globals and scalarized
1054 coalesce_vars (var_map map
, tree_live_info_p liveinfo
)
1061 conflict_graph graph
;
1063 cl
= create_coalesce_list (map
);
1065 /* Merge all the live on entry vectors for coalesced partitions. */
1066 for (x
= 0; x
< num_var_partitions (map
); x
++)
1068 var
= partition_to_var (map
, x
);
1069 p
= var_to_partition (map
, var
);
1071 live_merge_and_clear (liveinfo
, p
, x
);
1074 /* When PHI nodes are turned into copies, the result of each PHI node
1075 becomes live on entry to the block. Mark these now. */
1080 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1082 p
= var_to_partition (map
, PHI_RESULT (phi
));
1084 /* Skip virtual PHI nodes. */
1085 if (p
== NO_PARTITION
)
1088 make_live_on_entry (liveinfo
, bb
, p
);
1090 /* Each argument is a potential copy operation. Add any arguments
1091 which are not coalesced to the result to the coalesce list. */
1092 for (x
= 0; x
< PHI_NUM_ARGS (phi
); x
++)
1094 arg
= PHI_ARG_DEF (phi
, x
);
1095 if (!phi_ssa_name_p (arg
))
1097 p2
= var_to_partition (map
, arg
);
1098 if (p2
== NO_PARTITION
)
1101 add_coalesce (cl
, p
, p2
, 1);
1107 /* Re-calculate live on exit info. */
1108 calculate_live_on_exit (liveinfo
);
1110 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1112 fprintf (dump_file
, "Live range info for variable memory coalescing.\n");
1113 dump_live_info (dump_file
, liveinfo
, LIVEDUMP_ALL
);
1115 fprintf (dump_file
, "Coalesce list from phi nodes:\n");
1116 dump_coalesce_list (dump_file
, cl
);
1120 tv
= type_var_init (map
);
1122 type_var_dump (dump_file
, tv
);
1123 type_var_compact (tv
);
1125 type_var_dump (dump_file
, tv
);
1127 graph
= build_tree_conflict_graph (liveinfo
, tv
, cl
);
1129 type_var_decompact (tv
);
1130 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1132 fprintf (dump_file
, "type var list now looks like:n");
1133 type_var_dump (dump_file
, tv
);
1135 fprintf (dump_file
, "Coalesce list after conflict graph build:\n");
1136 dump_coalesce_list (dump_file
, cl
);
1139 sort_coalesce_list (cl
);
1140 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1142 fprintf (dump_file
, "Coalesce list after sorting:\n");
1143 dump_coalesce_list (dump_file
, cl
);
1146 coalesce_tpa_members (tv
, graph
, map
, cl
,
1147 ((dump_flags
& TDF_DETAILS
) ? dump_file
: NULL
));
1149 type_var_delete (tv
);
1150 delete_coalesce_list (cl
);
1154 /* Temporary Expression Replacement (TER)
1156 Replace SSA version variables during out-of-ssa with their defining
1157 expression if there is only one use of the variable.
1159 A pass is made through the function, one block at a time. No cross block
1160 information is tracked.
1162 Variables which only have one use, and whose defining stmt is considered
1163 a replaceable expression (see check_replaceable) are entered into
1164 consideration by adding a list of dependent partitions to the version_info
1165 vector for that ssa_name_version. This information comes from the partition
1166 mapping for each USE. At the same time, the partition_dep_list vector for
1167 these partitions have this version number entered into their lists.
1169 When the use of a replaceable ssa_variable is encountered, the dependence
1170 list in version_info[] is moved to the "pending_dependence" list in case
1171 the current expression is also replaceable. (To be determined later in
1172 processing this stmt.) version_info[] for the version is then updated to
1173 point to the defining stmt and the 'replaceable' bit is set.
1175 Any partition which is defined by a statement 'kills' any expression which
1176 is dependent on this partition. Every ssa version in the partitions'
1177 dependence list is removed from future consideration.
1179 All virtual references are lumped together. Any expression which is
1180 dependent on any virtual variable (via a VUSE) has a dependence added
1181 to the special partition defined by VIRTUAL_PARTITION.
1183 Whenever a V_MAY_DEF is seen, all expressions dependent this
1184 VIRTUAL_PARTITION are removed from consideration.
1186 At the end of a basic block, all expression are removed from consideration
1187 in preparation for the next block.
1189 The end result is a vector over SSA_NAME_VERSION which is passed back to
1190 rewrite_out_of_ssa. As the SSA variables are being rewritten, instead of
1191 replacing the SSA_NAME tree element with the partition it was assigned,
1192 it is replaced with the RHS of the defining expression. */
1195 /* Dependency list element. This can contain either a partition index or a
1196 version number, depending on which list it is in. */
1198 typedef struct value_expr_d
1201 struct value_expr_d
*next
;
1205 /* Temporary Expression Replacement (TER) table information. */
1207 typedef struct temp_expr_table_d
1210 void **version_info
;
1211 value_expr_p
*partition_dep_list
;
1213 bool saw_replaceable
;
1214 int virtual_partition
;
1215 bitmap partition_in_use
;
1216 value_expr_p free_list
;
1217 value_expr_p pending_dependence
;
1218 } *temp_expr_table_p
;
1220 /* Used to indicate a dependency on V_MAY_DEFs. */
1221 #define VIRTUAL_PARTITION(table) (table->virtual_partition)
1223 static temp_expr_table_p
new_temp_expr_table (var_map
);
1224 static tree
*free_temp_expr_table (temp_expr_table_p
);
1225 static inline value_expr_p
new_value_expr (temp_expr_table_p
);
1226 static inline void free_value_expr (temp_expr_table_p
, value_expr_p
);
1227 static inline value_expr_p
find_value_in_list (value_expr_p
, int,
1229 static inline void add_value_to_list (temp_expr_table_p
, value_expr_p
*, int);
1230 static inline void add_info_to_list (temp_expr_table_p
, value_expr_p
*,
1232 static value_expr_p
remove_value_from_list (value_expr_p
*, int);
1233 static void add_dependance (temp_expr_table_p
, int, tree
);
1234 static bool check_replaceable (temp_expr_table_p
, tree
);
1235 static void finish_expr (temp_expr_table_p
, int, bool);
1236 static void mark_replaceable (temp_expr_table_p
, tree
);
1237 static inline void kill_expr (temp_expr_table_p
, int, bool);
1238 static inline void kill_virtual_exprs (temp_expr_table_p
, bool);
1239 static void find_replaceable_in_bb (temp_expr_table_p
, basic_block
);
1240 static tree
*find_replaceable_exprs (var_map
);
1241 static void dump_replaceable_exprs (FILE *, tree
*);
1244 /* Create a new TER table for MAP. */
1246 static temp_expr_table_p
1247 new_temp_expr_table (var_map map
)
1249 temp_expr_table_p t
;
1251 t
= (temp_expr_table_p
) xmalloc (sizeof (struct temp_expr_table_d
));
1254 t
->version_info
= xcalloc (num_ssa_names
+ 1, sizeof (void *));
1255 t
->partition_dep_list
= xcalloc (num_var_partitions (map
) + 1,
1256 sizeof (value_expr_p
));
1258 t
->replaceable
= BITMAP_XMALLOC ();
1259 t
->partition_in_use
= BITMAP_XMALLOC ();
1261 t
->saw_replaceable
= false;
1262 t
->virtual_partition
= num_var_partitions (map
);
1263 t
->free_list
= NULL
;
1264 t
->pending_dependence
= NULL
;
1270 /* Free TER table T. If there are valid replacements, return the expression
1274 free_temp_expr_table (temp_expr_table_p t
)
1279 #ifdef ENABLE_CHECKING
1281 for (x
= 0; x
<= num_var_partitions (t
->map
); x
++)
1282 gcc_assert (!t
->partition_dep_list
[x
]);
1285 while ((p
= t
->free_list
))
1287 t
->free_list
= p
->next
;
1291 BITMAP_XFREE (t
->partition_in_use
);
1292 BITMAP_XFREE (t
->replaceable
);
1294 free (t
->partition_dep_list
);
1295 if (t
->saw_replaceable
)
1296 ret
= (tree
*)t
->version_info
;
1298 free (t
->version_info
);
1305 /* Allocate a new value list node. Take it from the free list in TABLE if
1308 static inline value_expr_p
1309 new_value_expr (temp_expr_table_p table
)
1312 if (table
->free_list
)
1314 p
= table
->free_list
;
1315 table
->free_list
= p
->next
;
1318 p
= (value_expr_p
) xmalloc (sizeof (struct value_expr_d
));
1324 /* Add value list node P to the free list in TABLE. */
1327 free_value_expr (temp_expr_table_p table
, value_expr_p p
)
1329 p
->next
= table
->free_list
;
1330 table
->free_list
= p
;
1334 /* Find VALUE if its in LIST. Return a pointer to the list object if found,
1335 else return NULL. If LAST_PTR is provided, it will point to the previous
1336 item upon return, or NULL if this is the first item in the list. */
1338 static inline value_expr_p
1339 find_value_in_list (value_expr_p list
, int value
, value_expr_p
*last_ptr
)
1342 value_expr_p last
= NULL
;
1344 for (curr
= list
; curr
; last
= curr
, curr
= curr
->next
)
1346 if (curr
->value
== value
)
1355 /* Add VALUE to LIST, if it isn't already present. TAB is the expression
1359 add_value_to_list (temp_expr_table_p tab
, value_expr_p
*list
, int value
)
1363 if (!find_value_in_list (*list
, value
, NULL
))
1365 info
= new_value_expr (tab
);
1366 info
->value
= value
;
1373 /* Add value node INFO if it's value isn't already in LIST. Free INFO if
1374 it is already in the list. TAB is the expression table. */
1377 add_info_to_list (temp_expr_table_p tab
, value_expr_p
*list
, value_expr_p info
)
1379 if (find_value_in_list (*list
, info
->value
, NULL
))
1380 free_value_expr (tab
, info
);
1389 /* Look for VALUE in LIST. If found, remove it from the list and return it's
1393 remove_value_from_list (value_expr_p
*list
, int value
)
1395 value_expr_p info
, last
;
1397 info
= find_value_in_list (*list
, value
, &last
);
1403 last
->next
= info
->next
;
1409 /* Add a dependency between the def of ssa VERSION and VAR. If VAR is
1410 replaceable by an expression, add a dependence each of the elements of the
1411 expression. These are contained in the pending list. TAB is the
1412 expression table. */
1415 add_dependance (temp_expr_table_p tab
, int version
, tree var
)
1420 i
= SSA_NAME_VERSION (var
);
1421 if (bitmap_bit_p (tab
->replaceable
, i
))
1423 /* This variable is being substituted, so use whatever dependences
1424 were queued up when we marked this as replaceable earlier. */
1425 while ((info
= tab
->pending_dependence
))
1427 tab
->pending_dependence
= info
->next
;
1428 /* Get the partition this variable was dependent on. Reuse this
1429 object to represent the current expression instead. */
1431 info
->value
= version
;
1432 add_info_to_list (tab
, &(tab
->partition_dep_list
[x
]), info
);
1433 add_value_to_list (tab
,
1434 (value_expr_p
*)&(tab
->version_info
[version
]), x
);
1435 bitmap_set_bit (tab
->partition_in_use
, x
);
1440 i
= var_to_partition (tab
->map
, var
);
1441 gcc_assert (i
!= NO_PARTITION
);
1442 add_value_to_list (tab
, &(tab
->partition_dep_list
[i
]), version
);
1443 add_value_to_list (tab
,
1444 (value_expr_p
*)&(tab
->version_info
[version
]), i
);
1445 bitmap_set_bit (tab
->partition_in_use
, i
);
1450 /* Check if expression STMT is suitable for replacement in table TAB. If so,
1451 create an expression entry. Return true if this stmt is replaceable. */
1454 check_replaceable (temp_expr_table_p tab
, tree stmt
)
1457 vuse_optype vuseops
;
1461 int num_use_ops
, version
;
1462 var_map map
= tab
->map
;
1465 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
1468 ann
= stmt_ann (stmt
);
1469 defs
= DEF_OPS (ann
);
1471 /* Punt if there is more than 1 def, or more than 1 use. */
1472 if (NUM_DEFS (defs
) != 1)
1474 def
= DEF_OP (defs
, 0);
1475 if (version_ref_count (map
, def
) != 1)
1478 /* Assignments to variables assigned to hard registers are not
1480 if (DECL_HARD_REGISTER (SSA_NAME_VAR (def
)))
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 uses
= USE_OPS (ann
);
1496 num_use_ops
= NUM_USES (uses
);
1497 vuseops
= VUSE_OPS (ann
);
1499 /* Any expression which has no virtual operands and no real operands
1500 should have been propagated if it's possible to do anything with them.
1501 If this happens here, it probably exists that way for a reason, so we
1502 won't touch it. An example is:
1504 There are no virtual uses nor any real uses, so we just leave this
1505 alone to be safe. */
1507 if (num_use_ops
== 0 && NUM_VUSES (vuseops
) == 0)
1510 version
= SSA_NAME_VERSION (def
);
1512 /* Add this expression to the dependency list for each use partition. */
1513 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, SSA_OP_USE
)
1515 add_dependance (tab
, version
, var
);
1518 /* If there are VUSES, add a dependence on virtual defs. */
1519 if (NUM_VUSES (vuseops
) != 0)
1521 add_value_to_list (tab
, (value_expr_p
*)&(tab
->version_info
[version
]),
1522 VIRTUAL_PARTITION (tab
));
1523 add_value_to_list (tab
,
1524 &(tab
->partition_dep_list
[VIRTUAL_PARTITION (tab
)]),
1526 bitmap_set_bit (tab
->partition_in_use
, VIRTUAL_PARTITION (tab
));
1533 /* This function will remove the expression for VERSION from replacement
1534 consideration.n table TAB If 'replace' is true, it is marked as
1535 replaceable, otherwise not. */
1538 finish_expr (temp_expr_table_p tab
, int version
, bool replace
)
1540 value_expr_p info
, tmp
;
1543 /* Remove this expression from its dependent lists. The partition dependence
1544 list is retained and transfered later to whomever uses this version. */
1545 for (info
= (value_expr_p
) tab
->version_info
[version
]; info
; info
= tmp
)
1547 partition
= info
->value
;
1548 gcc_assert (tab
->partition_dep_list
[partition
]);
1549 tmp
= remove_value_from_list (&(tab
->partition_dep_list
[partition
]),
1552 free_value_expr (tab
, tmp
);
1553 /* Only clear the bit when the dependency list is emptied via
1554 a replacement. Otherwise kill_expr will take care of it. */
1555 if (!(tab
->partition_dep_list
[partition
]) && replace
)
1556 bitmap_clear_bit (tab
->partition_in_use
, partition
);
1559 free_value_expr (tab
, info
);
1564 tab
->saw_replaceable
= true;
1565 bitmap_set_bit (tab
->replaceable
, version
);
1569 gcc_assert (!bitmap_bit_p (tab
->replaceable
, version
));
1570 tab
->version_info
[version
] = NULL
;
1575 /* Mark the expression associated with VAR as replaceable, and enter
1576 the defining stmt into the version_info table TAB. */
1579 mark_replaceable (temp_expr_table_p tab
, tree var
)
1582 int version
= SSA_NAME_VERSION (var
);
1583 finish_expr (tab
, version
, true);
1585 /* Move the dependence list to the pending list. */
1586 if (tab
->version_info
[version
])
1588 info
= (value_expr_p
) tab
->version_info
[version
];
1589 for ( ; info
->next
; info
= info
->next
)
1591 info
->next
= tab
->pending_dependence
;
1592 tab
->pending_dependence
= (value_expr_p
)tab
->version_info
[version
];
1595 tab
->version_info
[version
] = SSA_NAME_DEF_STMT (var
);
1599 /* This function marks any expression in TAB which is dependent on PARTITION
1600 as NOT replaceable. CLEAR_BIT is used to determine whether partition_in_use
1601 should have its bit cleared. Since this routine can be called within an
1602 EXECUTE_IF_SET_IN_BITMAP, the bit can't always be cleared. */
1605 kill_expr (temp_expr_table_p tab
, int partition
, bool clear_bit
)
1609 /* Mark every active expr dependent on this var as not replaceable. */
1610 while ((ptr
= tab
->partition_dep_list
[partition
]) != NULL
)
1611 finish_expr (tab
, ptr
->value
, false);
1614 bitmap_clear_bit (tab
->partition_in_use
, partition
);
1618 /* This function kills all expressions in TAB which are dependent on virtual
1619 DEFs. CLEAR_BIT determines whether partition_in_use gets cleared. */
1622 kill_virtual_exprs (temp_expr_table_p tab
, bool clear_bit
)
1624 kill_expr (tab
, VIRTUAL_PARTITION (tab
), clear_bit
);
1628 /* This function processes basic block BB, and looks for variables which can
1629 be replaced by their expressions. Results are stored in TAB. */
1632 find_replaceable_in_bb (temp_expr_table_p tab
, basic_block bb
)
1634 block_stmt_iterator bsi
;
1638 var_map map
= tab
->map
;
1642 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1644 stmt
= bsi_stmt (bsi
);
1645 ann
= stmt_ann (stmt
);
1647 /* Determine if this stmt finishes an existing expression. */
1648 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_USE
)
1650 if (tab
->version_info
[SSA_NAME_VERSION (def
)])
1652 /* Mark expression as replaceable unless stmt is volatile. */
1653 if (!ann
->has_volatile_ops
)
1654 mark_replaceable (tab
, def
);
1656 finish_expr (tab
, SSA_NAME_VERSION (def
), false);
1660 /* Next, see if this stmt kills off an active expression. */
1661 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_DEF
)
1663 partition
= var_to_partition (map
, def
);
1664 if (partition
!= NO_PARTITION
&& tab
->partition_dep_list
[partition
])
1665 kill_expr (tab
, partition
, true);
1668 /* Now see if we are creating a new expression or not. */
1669 if (!ann
->has_volatile_ops
)
1670 check_replaceable (tab
, stmt
);
1672 /* Free any unused dependency lists. */
1673 while ((p
= tab
->pending_dependence
))
1675 tab
->pending_dependence
= p
->next
;
1676 free_value_expr (tab
, p
);
1679 /* A V_MAY_DEF kills any expression using a virtual operand. */
1680 if (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann
)) > 0)
1681 kill_virtual_exprs (tab
, true);
1683 /* A V_MUST_DEF kills any expression using a virtual operand. */
1684 if (NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann
)) > 0)
1685 kill_virtual_exprs (tab
, true);
1690 /* This function is the driver routine for replacement of temporary expressions
1691 in the SSA->normal phase, operating on MAP. If there are replaceable
1692 expressions, a table is returned which maps SSA versions to the
1693 expressions they should be replaced with. A NULL_TREE indicates no
1694 replacement should take place. If there are no replacements at all,
1695 NULL is returned by the function, otherwise an expression vector indexed
1696 by SSA_NAME version numbers. */
1699 find_replaceable_exprs (var_map map
)
1703 temp_expr_table_p table
;
1706 table
= new_temp_expr_table (map
);
1709 find_replaceable_in_bb (table
, bb
);
1710 EXECUTE_IF_SET_IN_BITMAP ((table
->partition_in_use
), 0, i
,
1712 kill_expr (table
, i
, false);
1716 ret
= free_temp_expr_table (table
);
1721 /* Dump TER expression table EXPR to file F. */
1724 dump_replaceable_exprs (FILE *f
, tree
*expr
)
1728 fprintf (f
, "\nReplacing Expressions\n");
1729 for (x
= 0; x
< (int)num_ssa_names
+ 1; x
++)
1733 var
= DEF_OP (STMT_DEF_OPS (stmt
), 0);
1734 print_generic_expr (f
, var
, TDF_SLIM
);
1735 fprintf (f
, " replace with --> ");
1736 print_generic_expr (f
, TREE_OPERAND (stmt
, 1), TDF_SLIM
);
1743 /* Helper function for discover_nonconstant_array_refs.
1744 Look for ARRAY_REF nodes with non-constant indexes and mark them
1748 discover_nonconstant_array_refs_r (tree
* tp
, int *walk_subtrees
,
1749 void *data ATTRIBUTE_UNUSED
)
1753 if (IS_TYPE_OR_DECL_P (t
))
1755 else if (TREE_CODE (t
) == ARRAY_REF
|| TREE_CODE (t
) == ARRAY_RANGE_REF
)
1757 while (((TREE_CODE (t
) == ARRAY_REF
|| TREE_CODE (t
) == ARRAY_RANGE_REF
)
1758 && is_gimple_min_invariant (TREE_OPERAND (t
, 1))
1759 && (!TREE_OPERAND (t
, 2)
1760 || is_gimple_min_invariant (TREE_OPERAND (t
, 2))))
1761 || (TREE_CODE (t
) == COMPONENT_REF
1762 && (!TREE_OPERAND (t
,2)
1763 || is_gimple_min_invariant (TREE_OPERAND (t
, 2))))
1764 || TREE_CODE (t
) == BIT_FIELD_REF
1765 || TREE_CODE (t
) == REALPART_EXPR
1766 || TREE_CODE (t
) == IMAGPART_EXPR
1767 || TREE_CODE (t
) == VIEW_CONVERT_EXPR
1768 || TREE_CODE (t
) == NOP_EXPR
1769 || TREE_CODE (t
) == CONVERT_EXPR
)
1770 t
= TREE_OPERAND (t
, 0);
1772 if (TREE_CODE (t
) == ARRAY_REF
|| TREE_CODE (t
) == ARRAY_RANGE_REF
)
1774 t
= get_base_address (t
);
1775 if (t
&& DECL_P (t
))
1776 TREE_ADDRESSABLE (t
) = 1;
1786 /* RTL expansion is not able to compile array references with variable
1787 offsets for arrays stored in single register. Discover such
1788 expressions and mark variables as addressable to avoid this
1792 discover_nonconstant_array_refs (void)
1795 block_stmt_iterator bsi
;
1799 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1800 walk_tree (bsi_stmt_ptr (bsi
), discover_nonconstant_array_refs_r
,
1806 /* This function will rewrite the current program using the variable mapping
1807 found in MAP. If the replacement vector VALUES is provided, any
1808 occurrences of partitions with non-null entries in the vector will be
1809 replaced with the expression in the vector instead of its mapped
1813 rewrite_trees (var_map map
, tree
*values
)
1817 block_stmt_iterator si
;
1822 #ifdef ENABLE_CHECKING
1823 /* Search for PHIs where the destination has no partition, but one
1824 or more arguments has a partition. This should not happen and can
1825 create incorrect code. */
1830 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1832 tree T0
= var_to_partition_to_var (map
, PHI_RESULT (phi
));
1834 if (T0
== NULL_TREE
)
1838 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
1840 tree arg
= PHI_ARG_DEF (phi
, i
);
1842 if (TREE_CODE (arg
) == SSA_NAME
1843 && var_to_partition (map
, arg
) != NO_PARTITION
)
1845 fprintf (stderr
, "Argument of PHI is in a partition :(");
1846 print_generic_expr (stderr
, arg
, TDF_SLIM
);
1847 fprintf (stderr
, "), but the result is not :");
1848 print_generic_stmt (stderr
, phi
, TDF_SLIM
);
1849 internal_error ("SSA corruption");
1857 /* Replace PHI nodes with any required copies. */
1858 g
= new_elim_graph (map
->num_partitions
);
1862 for (si
= bsi_start (bb
); !bsi_end_p (si
); )
1864 size_t num_uses
, num_defs
;
1867 tree stmt
= bsi_stmt (si
);
1868 use_operand_p use_p
;
1869 def_operand_p def_p
;
1870 int remove
= 0, is_copy
= 0;
1874 get_stmt_operands (stmt
);
1875 ann
= stmt_ann (stmt
);
1878 if (TREE_CODE (stmt
) == MODIFY_EXPR
1879 && (TREE_CODE (TREE_OPERAND (stmt
, 1)) == SSA_NAME
))
1882 uses
= USE_OPS (ann
);
1883 num_uses
= NUM_USES (uses
);
1884 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
1886 if (replace_use_variable (map
, use_p
, values
))
1890 defs
= DEF_OPS (ann
);
1891 num_defs
= NUM_DEFS (defs
);
1893 /* Mark this stmt for removal if it is the list of replaceable
1895 if (values
&& num_defs
== 1)
1897 tree def
= DEF_OP (defs
, 0);
1899 val
= values
[SSA_NAME_VERSION (def
)];
1905 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, iter
, SSA_OP_DEF
)
1907 if (replace_def_variable (map
, def_p
, NULL
))
1910 /* If both SSA_NAMEs coalesce to the same variable,
1911 mark the now redundant copy for removal. */
1914 && (DEF_FROM_PTR (def_p
) == USE_OP (uses
, 0)))
1917 if (changed
& !remove
)
1921 /* Remove any stmts marked for removal. */
1928 phi
= phi_nodes (bb
);
1931 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
1932 eliminate_phi (e
, phi_arg_from_edge (phi
, e
), g
);
1936 delete_elim_graph (g
);
1938 /* If any copies were inserted on edges, actually insert them now. */
1939 bsi_commit_edge_inserts (NULL
);
1943 /* Remove the variables specified in MAP from SSA form. Any debug information
1944 is sent to DUMP. FLAGS indicate what options should be used. */
1947 remove_ssa_form (FILE *dump
, var_map map
, int flags
)
1949 tree_live_info_p liveinfo
;
1953 tree
*values
= NULL
;
1958 /* If we are not combining temps, don't calculate live ranges for variables
1959 with only one SSA version. */
1960 if ((flags
& SSANORM_COMBINE_TEMPS
) == 0)
1961 compact_var_map (map
, VARMAP_NO_SINGLE_DEFS
);
1963 compact_var_map (map
, VARMAP_NORMAL
);
1965 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1966 dump_var_map (dump_file
, map
);
1968 liveinfo
= coalesce_ssa_name (map
, flags
);
1970 /* Make sure even single occurrence variables are in the list now. */
1971 if ((flags
& SSANORM_COMBINE_TEMPS
) == 0)
1972 compact_var_map (map
, VARMAP_NORMAL
);
1974 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1976 fprintf (dump_file
, "After Coalescing:\n");
1977 dump_var_map (dump_file
, map
);
1980 if (flags
& SSANORM_PERFORM_TER
)
1982 values
= find_replaceable_exprs (map
);
1983 if (values
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
1984 dump_replaceable_exprs (dump_file
, values
);
1987 /* Assign real variables to the partitions now. */
1990 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1992 fprintf (dump_file
, "After Root variable replacement:\n");
1993 dump_var_map (dump_file
, map
);
1996 if ((flags
& SSANORM_COMBINE_TEMPS
) && liveinfo
)
1998 coalesce_vars (map
, liveinfo
);
1999 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2001 fprintf (dump_file
, "After variable memory coalescing:\n");
2002 dump_var_map (dump_file
, map
);
2007 delete_tree_live_info (liveinfo
);
2009 rewrite_trees (map
, values
);
2014 /* Remove phi nodes which have been translated back to real variables. */
2017 for (phi
= phi_nodes (bb
); phi
; phi
= next
)
2019 next
= PHI_CHAIN (phi
);
2020 if ((flags
& SSANORM_REMOVE_ALL_PHIS
)
2021 || var_to_partition (map
, PHI_RESULT (phi
)) != NO_PARTITION
)
2022 remove_phi_node (phi
, NULL_TREE
, bb
);
2029 /* Take the current function out of SSA form, as described in
2030 R. Morgan, ``Building an Optimizing Compiler'',
2031 Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */
2034 rewrite_out_of_ssa (void)
2038 int ssa_flags
= (SSANORM_REMOVE_ALL_PHIS
| SSANORM_USE_COALESCE_LIST
);
2040 if (!flag_tree_live_range_split
)
2041 ssa_flags
|= SSANORM_COALESCE_PARTITIONS
;
2043 eliminate_virtual_phis ();
2045 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2046 dump_tree_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);
2048 /* We cannot allow unssa to un-gimplify trees before we instrument them. */
2049 if (flag_tree_ter
&& !flag_mudflap
)
2050 var_flags
= SSA_VAR_MAP_REF_COUNT
;
2052 map
= create_ssa_var_map (var_flags
);
2054 if (flag_tree_combine_temps
)
2055 ssa_flags
|= SSANORM_COMBINE_TEMPS
;
2056 if (flag_tree_ter
&& !flag_mudflap
)
2057 ssa_flags
|= SSANORM_PERFORM_TER
;
2059 remove_ssa_form (dump_file
, map
, ssa_flags
);
2061 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2062 dump_tree_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);
2064 /* Do some cleanups which reduce the amount of data the
2065 tree->rtl expanders deal with. */
2066 cfg_remove_useless_stmts ();
2068 /* Flush out flow graph and SSA data. */
2069 delete_var_map (map
);
2071 /* Mark arrays indexed with non-constant indices with TREE_ADDRESSABLE. */
2072 discover_nonconstant_array_refs ();
2076 /* Define the parameters of the out of SSA pass. */
2078 struct tree_opt_pass pass_del_ssa
=
2080 "optimized", /* name */
2082 rewrite_out_of_ssa
, /* execute */
2085 0, /* static_pass_number */
2086 TV_TREE_SSA_TO_NORMAL
, /* tv_id */
2087 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
2088 0, /* properties_provided */
2089 /* ??? If TER is enabled, we also kill gimple. */
2090 PROP_ssa
, /* properties_destroyed */
2091 TODO_verify_ssa
| TODO_verify_flow
2092 | TODO_verify_stmts
, /* todo_flags_start */
2093 TODO_dump_func
| TODO_ggc_collect
, /* todo_flags_finish */