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
)
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 y
= phi_arg_from_edge (phi
, e
);
605 gcc_assert (y
!= -1);
607 tmp
= PHI_ARG_DEF (phi
, y
);
608 #ifdef ENABLE_CHECKING
609 if (!phi_ssa_name_p (tmp
))
611 print_exprs_edge (stderr
, e
,
612 "\nConstant argument in PHI. Can't insert :",
614 internal_error ("SSA corruption");
617 gcc_assert (phi_ssa_name_p (tmp
));
619 y
= var_to_partition (map
, tmp
);
620 gcc_assert (x
!= NO_PARTITION
);
621 gcc_assert (y
!= NO_PARTITION
);
622 #ifdef ENABLE_CHECKING
623 if (root_var_find (rv
, x
) != root_var_find (rv
, y
))
625 print_exprs_edge (stderr
, e
, "\nDifferent root vars: ",
626 root_var (rv
, root_var_find (rv
, x
)),
628 root_var (rv
, root_var_find (rv
, y
)));
629 internal_error ("SSA corruption");
632 gcc_assert (root_var_find (rv
, x
) == root_var_find (rv
, y
));
637 #ifdef ENABLE_CHECKING
638 if (conflict_graph_conflict_p (graph
, x
, y
))
640 print_exprs_edge (stderr
, e
, "\n Conflict ",
641 partition_to_var (map
, x
),
642 " and ", partition_to_var (map
, y
));
643 internal_error ("SSA corruption");
646 gcc_assert (!conflict_graph_conflict_p (graph
, x
, y
));
649 /* Now map the partitions back to their real variables. */
650 var
= partition_to_var (map
, x
);
651 tmp
= partition_to_var (map
, y
);
652 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
654 print_exprs_edge (dump_file
, e
,
655 "ABNORMAL: Coalescing ",
658 #ifdef ENABLE_CHECKING
659 if (var_union (map
, var
, tmp
) == NO_PARTITION
)
661 print_exprs_edge (stderr
, e
, "\nUnable to coalesce",
662 partition_to_var (map
, x
), " and ",
663 partition_to_var (map
, y
));
664 internal_error ("SSA corruption");
667 gcc_assert (var_union (map
, var
, tmp
) != NO_PARTITION
);
669 conflict_graph_merge_regs (graph
, x
, y
);
675 /* Reduce the number of live ranges in MAP. Live range information is
676 returned if FLAGS indicates that we are combining temporaries, otherwise
677 NULL is returned. The only partitions which are associated with actual
678 variables at this point are those which are forced to be coalesced for
679 various reason. (live on entry, live across abnormal edges, etc.). */
681 static tree_live_info_p
682 coalesce_ssa_name (var_map map
, int flags
)
688 tree_live_info_p liveinfo
;
690 conflict_graph graph
;
692 coalesce_list_p cl
= NULL
;
694 if (num_var_partitions (map
) <= 1)
697 /* If no preference given, use cheap coalescing of all partitions. */
698 if ((flags
& (SSANORM_COALESCE_PARTITIONS
| SSANORM_USE_COALESCE_LIST
)) == 0)
699 flags
|= SSANORM_COALESCE_PARTITIONS
;
701 liveinfo
= calculate_live_on_entry (map
);
702 calculate_live_on_exit (liveinfo
);
703 rv
= root_var_init (map
);
705 /* Remove single element variable from the list. */
706 root_var_compact (rv
);
708 if (flags
& SSANORM_USE_COALESCE_LIST
)
710 cl
= create_coalesce_list (map
);
712 /* Add all potential copies via PHI arguments to the list. */
715 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
717 tree res
= PHI_RESULT (phi
);
718 int p
= var_to_partition (map
, res
);
719 if (p
== NO_PARTITION
)
721 for (x
= 0; x
< PHI_NUM_ARGS (phi
); x
++)
723 tree arg
= PHI_ARG_DEF (phi
, x
);
726 if (TREE_CODE (arg
) != SSA_NAME
)
728 if (SSA_NAME_VAR (res
) != SSA_NAME_VAR (arg
))
730 p2
= var_to_partition (map
, PHI_ARG_DEF (phi
, x
));
731 if (p2
!= NO_PARTITION
)
732 add_coalesce (cl
, p
, p2
, 1);
737 /* Coalesce all the result decls together. */
740 for (x
= 0; x
< num_var_partitions (map
); x
++)
742 tree p
= partition_to_var (map
, x
);
743 if (TREE_CODE (SSA_NAME_VAR(p
)) == RESULT_DECL
)
745 if (var
== NULL_TREE
)
751 add_coalesce (cl
, i
, x
, 1);
756 /* Build a conflict graph. */
757 graph
= build_tree_conflict_graph (liveinfo
, rv
, cl
);
761 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
763 fprintf (dump_file
, "Before sorting:\n");
764 dump_coalesce_list (dump_file
, cl
);
767 sort_coalesce_list (cl
);
769 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
771 fprintf (dump_file
, "\nAfter sorting:\n");
772 dump_coalesce_list (dump_file
, cl
);
776 /* Put the single element variables back in. */
777 root_var_decompact (rv
);
779 /* First, coalesce all live on entry variables to their root variable.
780 This will ensure the first use is coming from the correct location. */
782 live
= sbitmap_alloc (num_var_partitions (map
));
785 /* Set 'live' vector to indicate live on entry partitions. */
786 num
= num_var_partitions (map
);
787 for (x
= 0 ; x
< num
; x
++)
789 var
= partition_to_var (map
, x
);
790 if (default_def (SSA_NAME_VAR (var
)) == var
)
794 if ((flags
& SSANORM_COMBINE_TEMPS
) == 0)
796 delete_tree_live_info (liveinfo
);
800 /* Assign root variable as partition representative for each live on entry
802 EXECUTE_IF_SET_IN_SBITMAP (live
, 0, x
,
804 var
= root_var (rv
, root_var_find (rv
, x
));
806 /* If these aren't already coalesced... */
807 if (partition_to_var (map
, x
) != var
)
809 /* This root variable should have not already been assigned
810 to another partition which is not coalesced with this one. */
811 gcc_assert (!ann
->out_of_ssa_tag
);
813 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
815 print_exprs (dump_file
, "Must coalesce ",
816 partition_to_var (map
, x
),
817 " with the root variable ", var
, ".\n");
820 change_partition_var (map
, var
, x
);
826 /* Coalesce partitions live across abnormal edges. */
827 coalesce_abnormal_edges (map
, graph
, rv
);
829 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
830 dump_var_map (dump_file
, map
);
832 /* Coalesce partitions. */
833 if (flags
& SSANORM_USE_COALESCE_LIST
)
834 coalesce_tpa_members (rv
, graph
, map
, cl
,
835 ((dump_flags
& TDF_DETAILS
) ? dump_file
839 if (flags
& SSANORM_COALESCE_PARTITIONS
)
840 coalesce_tpa_members (rv
, graph
, map
, NULL
,
841 ((dump_flags
& TDF_DETAILS
) ? dump_file
844 delete_coalesce_list (cl
);
845 root_var_delete (rv
);
846 conflict_graph_delete (graph
);
852 /* Take the ssa-name var_map MAP, and assign real variables to each
856 assign_vars (var_map map
)
863 rv
= root_var_init (map
);
867 /* Coalescing may already have forced some partitions to their root
868 variable. Find these and tag them. */
870 num
= num_var_partitions (map
);
871 for (x
= 0; x
< num
; x
++)
873 var
= partition_to_var (map
, x
);
874 if (TREE_CODE (var
) != SSA_NAME
)
876 /* Coalescing will already have verified that more than one
877 partition doesn't have the same root variable. Simply marked
878 the variable as assigned. */
880 ann
->out_of_ssa_tag
= 1;
881 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
883 fprintf (dump_file
, "partition %d has variable ", x
);
884 print_generic_expr (dump_file
, var
, TDF_SLIM
);
885 fprintf (dump_file
, " assigned to it.\n");
891 num
= root_var_num (rv
);
892 for (x
= 0; x
< num
; x
++)
894 var
= root_var (rv
, x
);
896 for (i
= root_var_first_partition (rv
, x
);
898 i
= root_var_next_partition (rv
, i
))
900 t
= partition_to_var (map
, i
);
902 if (t
== var
|| TREE_CODE (t
) != SSA_NAME
)
905 rep
= var_to_partition (map
, t
);
907 if (!ann
->out_of_ssa_tag
)
909 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
910 print_exprs (dump_file
, "", t
, " --> ", var
, "\n");
911 change_partition_var (map
, var
, rep
);
915 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
916 print_exprs (dump_file
, "", t
, " not coalesced with ", var
,
919 var
= create_temp (t
);
920 change_partition_var (map
, var
, rep
);
923 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
925 fprintf (dump_file
, " --> New temp: '");
926 print_generic_expr (dump_file
, var
, TDF_SLIM
);
927 fprintf (dump_file
, "'\n");
932 root_var_delete (rv
);
936 /* Replace use operand P with whatever variable it has been rewritten to based
937 on the partitions in MAP. EXPR is an optional expression vector over SSA
938 versions which is used to replace P with an expression instead of a variable.
939 If the stmt is changed, return true. */
942 replace_use_variable (var_map map
, use_operand_p p
, tree
*expr
)
945 tree var
= USE_FROM_PTR (p
);
947 /* Check if we are replacing this variable with an expression. */
950 int version
= SSA_NAME_VERSION (var
);
953 tree new_expr
= TREE_OPERAND (expr
[version
], 1);
954 SET_USE (p
, new_expr
);
955 /* Clear the stmt's RHS, or GC might bite us. */
956 TREE_OPERAND (expr
[version
], 1) = NULL_TREE
;
961 new_var
= var_to_partition_to_var (map
, var
);
964 SET_USE (p
, new_var
);
965 set_is_used (new_var
);
972 /* Replace def operand DEF_P with whatever variable it has been rewritten to
973 based on the partitions in MAP. EXPR is an optional expression vector over
974 SSA versions which is used to replace DEF_P with an expression instead of a
975 variable. If the stmt is changed, return true. */
978 replace_def_variable (var_map map
, def_operand_p def_p
, tree
*expr
)
981 tree var
= DEF_FROM_PTR (def_p
);
983 /* Check if we are replacing this variable with an expression. */
986 int version
= SSA_NAME_VERSION (var
);
989 tree new_expr
= TREE_OPERAND (expr
[version
], 1);
990 SET_DEF (def_p
, new_expr
);
991 /* Clear the stmt's RHS, or GC might bite us. */
992 TREE_OPERAND (expr
[version
], 1) = NULL_TREE
;
997 new_var
= var_to_partition_to_var (map
, var
);
1000 SET_DEF (def_p
, new_var
);
1001 set_is_used (new_var
);
1008 /* Remove any PHI node which is a virtual PHI. */
1011 eliminate_virtual_phis (void)
1018 for (phi
= phi_nodes (bb
); phi
; phi
= next
)
1020 next
= PHI_CHAIN (phi
);
1021 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi
))))
1023 #ifdef ENABLE_CHECKING
1025 /* There should be no arguments of this PHI which are in
1026 the partition list, or we get incorrect results. */
1027 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
1029 tree arg
= PHI_ARG_DEF (phi
, i
);
1030 if (TREE_CODE (arg
) == SSA_NAME
1031 && is_gimple_reg (SSA_NAME_VAR (arg
)))
1033 fprintf (stderr
, "Argument of PHI is not virtual (");
1034 print_generic_expr (stderr
, arg
, TDF_SLIM
);
1035 fprintf (stderr
, "), but the result is :");
1036 print_generic_stmt (stderr
, phi
, TDF_SLIM
);
1037 internal_error ("SSA corruption");
1041 remove_phi_node (phi
, NULL_TREE
, bb
);
1048 /* This routine will coalesce variables in MAP of the same type which do not
1049 interfere with each other. LIVEINFO is the live range info for variables
1050 of interest. This will both reduce the memory footprint of the stack, and
1051 allow us to coalesce together local copies of globals and scalarized
1055 coalesce_vars (var_map map
, tree_live_info_p liveinfo
)
1062 conflict_graph graph
;
1064 cl
= create_coalesce_list (map
);
1066 /* Merge all the live on entry vectors for coalesced partitions. */
1067 for (x
= 0; x
< num_var_partitions (map
); x
++)
1069 var
= partition_to_var (map
, x
);
1070 p
= var_to_partition (map
, var
);
1072 live_merge_and_clear (liveinfo
, p
, x
);
1075 /* When PHI nodes are turned into copies, the result of each PHI node
1076 becomes live on entry to the block. Mark these now. */
1081 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1083 p
= var_to_partition (map
, PHI_RESULT (phi
));
1085 /* Skip virtual PHI nodes. */
1086 if (p
== NO_PARTITION
)
1089 make_live_on_entry (liveinfo
, bb
, p
);
1091 /* Each argument is a potential copy operation. Add any arguments
1092 which are not coalesced to the result to the coalesce list. */
1093 for (x
= 0; x
< PHI_NUM_ARGS (phi
); x
++)
1095 arg
= PHI_ARG_DEF (phi
, x
);
1096 if (!phi_ssa_name_p (arg
))
1098 p2
= var_to_partition (map
, arg
);
1099 if (p2
== NO_PARTITION
)
1102 add_coalesce (cl
, p
, p2
, 1);
1108 /* Re-calculate live on exit info. */
1109 calculate_live_on_exit (liveinfo
);
1111 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1113 fprintf (dump_file
, "Live range info for variable memory coalescing.\n");
1114 dump_live_info (dump_file
, liveinfo
, LIVEDUMP_ALL
);
1116 fprintf (dump_file
, "Coalesce list from phi nodes:\n");
1117 dump_coalesce_list (dump_file
, cl
);
1121 tv
= type_var_init (map
);
1123 type_var_dump (dump_file
, tv
);
1124 type_var_compact (tv
);
1126 type_var_dump (dump_file
, tv
);
1128 graph
= build_tree_conflict_graph (liveinfo
, tv
, cl
);
1130 type_var_decompact (tv
);
1131 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1133 fprintf (dump_file
, "type var list now looks like:n");
1134 type_var_dump (dump_file
, tv
);
1136 fprintf (dump_file
, "Coalesce list after conflict graph build:\n");
1137 dump_coalesce_list (dump_file
, cl
);
1140 sort_coalesce_list (cl
);
1141 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1143 fprintf (dump_file
, "Coalesce list after sorting:\n");
1144 dump_coalesce_list (dump_file
, cl
);
1147 coalesce_tpa_members (tv
, graph
, map
, cl
,
1148 ((dump_flags
& TDF_DETAILS
) ? dump_file
: NULL
));
1150 type_var_delete (tv
);
1151 delete_coalesce_list (cl
);
1155 /* Temporary Expression Replacement (TER)
1157 Replace SSA version variables during out-of-ssa with their defining
1158 expression if there is only one use of the variable.
1160 A pass is made through the function, one block at a time. No cross block
1161 information is tracked.
1163 Variables which only have one use, and whose defining stmt is considered
1164 a replaceable expression (see check_replaceable) are entered into
1165 consideration by adding a list of dependent partitions to the version_info
1166 vector for that ssa_name_version. This information comes from the partition
1167 mapping for each USE. At the same time, the partition_dep_list vector for
1168 these partitions have this version number entered into their lists.
1170 When the use of a replaceable ssa_variable is encountered, the dependence
1171 list in version_info[] is moved to the "pending_dependence" list in case
1172 the current expression is also replaceable. (To be determined later in
1173 processing this stmt.) version_info[] for the version is then updated to
1174 point to the defining stmt and the 'replaceable' bit is set.
1176 Any partition which is defined by a statement 'kills' any expression which
1177 is dependent on this partition. Every ssa version in the partitions'
1178 dependence list is removed from future consideration.
1180 All virtual references are lumped together. Any expression which is
1181 dependent on any virtual variable (via a VUSE) has a dependence added
1182 to the special partition defined by VIRTUAL_PARTITION.
1184 Whenever a V_MAY_DEF is seen, all expressions dependent this
1185 VIRTUAL_PARTITION are removed from consideration.
1187 At the end of a basic block, all expression are removed from consideration
1188 in preparation for the next block.
1190 The end result is a vector over SSA_NAME_VERSION which is passed back to
1191 rewrite_out_of_ssa. As the SSA variables are being rewritten, instead of
1192 replacing the SSA_NAME tree element with the partition it was assigned,
1193 it is replaced with the RHS of the defining expression. */
1196 /* Dependency list element. This can contain either a partition index or a
1197 version number, depending on which list it is in. */
1199 typedef struct value_expr_d
1202 struct value_expr_d
*next
;
1206 /* Temporary Expression Replacement (TER) table information. */
1208 typedef struct temp_expr_table_d
1211 void **version_info
;
1212 value_expr_p
*partition_dep_list
;
1214 bool saw_replaceable
;
1215 int virtual_partition
;
1216 bitmap partition_in_use
;
1217 value_expr_p free_list
;
1218 value_expr_p pending_dependence
;
1219 } *temp_expr_table_p
;
1221 /* Used to indicate a dependency on V_MAY_DEFs. */
1222 #define VIRTUAL_PARTITION(table) (table->virtual_partition)
1224 static temp_expr_table_p
new_temp_expr_table (var_map
);
1225 static tree
*free_temp_expr_table (temp_expr_table_p
);
1226 static inline value_expr_p
new_value_expr (temp_expr_table_p
);
1227 static inline void free_value_expr (temp_expr_table_p
, value_expr_p
);
1228 static inline value_expr_p
find_value_in_list (value_expr_p
, int,
1230 static inline void add_value_to_list (temp_expr_table_p
, value_expr_p
*, int);
1231 static inline void add_info_to_list (temp_expr_table_p
, value_expr_p
*,
1233 static value_expr_p
remove_value_from_list (value_expr_p
*, int);
1234 static void add_dependance (temp_expr_table_p
, int, tree
);
1235 static bool check_replaceable (temp_expr_table_p
, tree
);
1236 static void finish_expr (temp_expr_table_p
, int, bool);
1237 static void mark_replaceable (temp_expr_table_p
, tree
);
1238 static inline void kill_expr (temp_expr_table_p
, int, bool);
1239 static inline void kill_virtual_exprs (temp_expr_table_p
, bool);
1240 static void find_replaceable_in_bb (temp_expr_table_p
, basic_block
);
1241 static tree
*find_replaceable_exprs (var_map
);
1242 static void dump_replaceable_exprs (FILE *, tree
*);
1245 /* Create a new TER table for MAP. */
1247 static temp_expr_table_p
1248 new_temp_expr_table (var_map map
)
1250 temp_expr_table_p t
;
1252 t
= (temp_expr_table_p
) xmalloc (sizeof (struct temp_expr_table_d
));
1255 t
->version_info
= xcalloc (num_ssa_names
+ 1, sizeof (void *));
1256 t
->partition_dep_list
= xcalloc (num_var_partitions (map
) + 1,
1257 sizeof (value_expr_p
));
1259 t
->replaceable
= BITMAP_XMALLOC ();
1260 t
->partition_in_use
= BITMAP_XMALLOC ();
1262 t
->saw_replaceable
= false;
1263 t
->virtual_partition
= num_var_partitions (map
);
1264 t
->free_list
= NULL
;
1265 t
->pending_dependence
= NULL
;
1271 /* Free TER table T. If there are valid replacements, return the expression
1275 free_temp_expr_table (temp_expr_table_p t
)
1280 #ifdef ENABLE_CHECKING
1282 for (x
= 0; x
<= num_var_partitions (t
->map
); x
++)
1283 gcc_assert (!t
->partition_dep_list
[x
]);
1286 while ((p
= t
->free_list
))
1288 t
->free_list
= p
->next
;
1292 BITMAP_XFREE (t
->partition_in_use
);
1293 BITMAP_XFREE (t
->replaceable
);
1295 free (t
->partition_dep_list
);
1296 if (t
->saw_replaceable
)
1297 ret
= (tree
*)t
->version_info
;
1299 free (t
->version_info
);
1306 /* Allocate a new value list node. Take it from the free list in TABLE if
1309 static inline value_expr_p
1310 new_value_expr (temp_expr_table_p table
)
1313 if (table
->free_list
)
1315 p
= table
->free_list
;
1316 table
->free_list
= p
->next
;
1319 p
= (value_expr_p
) xmalloc (sizeof (struct value_expr_d
));
1325 /* Add value list node P to the free list in TABLE. */
1328 free_value_expr (temp_expr_table_p table
, value_expr_p p
)
1330 p
->next
= table
->free_list
;
1331 table
->free_list
= p
;
1335 /* Find VALUE if its in LIST. Return a pointer to the list object if found,
1336 else return NULL. If LAST_PTR is provided, it will point to the previous
1337 item upon return, or NULL if this is the first item in the list. */
1339 static inline value_expr_p
1340 find_value_in_list (value_expr_p list
, int value
, value_expr_p
*last_ptr
)
1343 value_expr_p last
= NULL
;
1345 for (curr
= list
; curr
; last
= curr
, curr
= curr
->next
)
1347 if (curr
->value
== value
)
1356 /* Add VALUE to LIST, if it isn't already present. TAB is the expression
1360 add_value_to_list (temp_expr_table_p tab
, value_expr_p
*list
, int value
)
1364 if (!find_value_in_list (*list
, value
, NULL
))
1366 info
= new_value_expr (tab
);
1367 info
->value
= value
;
1374 /* Add value node INFO if it's value isn't already in LIST. Free INFO if
1375 it is already in the list. TAB is the expression table. */
1378 add_info_to_list (temp_expr_table_p tab
, value_expr_p
*list
, value_expr_p info
)
1380 if (find_value_in_list (*list
, info
->value
, NULL
))
1381 free_value_expr (tab
, info
);
1390 /* Look for VALUE in LIST. If found, remove it from the list and return it's
1394 remove_value_from_list (value_expr_p
*list
, int value
)
1396 value_expr_p info
, last
;
1398 info
= find_value_in_list (*list
, value
, &last
);
1404 last
->next
= info
->next
;
1410 /* Add a dependency between the def of ssa VERSION and VAR. If VAR is
1411 replaceable by an expression, add a dependence each of the elements of the
1412 expression. These are contained in the pending list. TAB is the
1413 expression table. */
1416 add_dependance (temp_expr_table_p tab
, int version
, tree var
)
1421 i
= SSA_NAME_VERSION (var
);
1422 if (bitmap_bit_p (tab
->replaceable
, i
))
1424 /* This variable is being substituted, so use whatever dependences
1425 were queued up when we marked this as replaceable earlier. */
1426 while ((info
= tab
->pending_dependence
))
1428 tab
->pending_dependence
= info
->next
;
1429 /* Get the partition this variable was dependent on. Reuse this
1430 object to represent the current expression instead. */
1432 info
->value
= version
;
1433 add_info_to_list (tab
, &(tab
->partition_dep_list
[x
]), info
);
1434 add_value_to_list (tab
,
1435 (value_expr_p
*)&(tab
->version_info
[version
]), x
);
1436 bitmap_set_bit (tab
->partition_in_use
, x
);
1441 i
= var_to_partition (tab
->map
, var
);
1442 gcc_assert (i
!= NO_PARTITION
);
1443 add_value_to_list (tab
, &(tab
->partition_dep_list
[i
]), version
);
1444 add_value_to_list (tab
,
1445 (value_expr_p
*)&(tab
->version_info
[version
]), i
);
1446 bitmap_set_bit (tab
->partition_in_use
, i
);
1451 /* Check if expression STMT is suitable for replacement in table TAB. If so,
1452 create an expression entry. Return true if this stmt is replaceable. */
1455 check_replaceable (temp_expr_table_p tab
, tree stmt
)
1459 var_map map
= tab
->map
;
1462 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
1465 /* Punt if there is more than 1 def, or more than 1 use. */
1466 def
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_DEF
);
1470 if (version_ref_count (map
, def
) != 1)
1473 /* There must be no V_MAY_DEFS or V_MUST_DEFS. */
1474 if (!ZERO_SSA_OPERANDS (stmt
, (SSA_OP_VMAYDEF
| SSA_OP_VMUSTDEF
)))
1477 /* Float expressions must go through memory if float-store is on. */
1478 if (flag_float_store
&& FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt
, 1))))
1481 /* Any expression which has no virtual operands and no real operands
1482 should have been propagated if it's possible to do anything with them.
1483 If this happens here, it probably exists that way for a reason, so we
1484 won't touch it. An example is:
1486 There are no virtual uses nor any real uses, so we will just leave this
1487 alone to be safe. */
1489 version
= SSA_NAME_VERSION (def
);
1491 /* Add this expression to the dependency list for each use partition. */
1492 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, SSA_OP_USE
)
1494 add_dependance (tab
, version
, var
);
1497 /* If there are VUSES, add a dependence on virtual defs. */
1498 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_VUSE
))
1500 add_value_to_list (tab
, (value_expr_p
*)&(tab
->version_info
[version
]),
1501 VIRTUAL_PARTITION (tab
));
1502 add_value_to_list (tab
,
1503 &(tab
->partition_dep_list
[VIRTUAL_PARTITION (tab
)]),
1505 bitmap_set_bit (tab
->partition_in_use
, VIRTUAL_PARTITION (tab
));
1512 /* This function will remove the expression for VERSION from replacement
1513 consideration.n table TAB If 'replace' is true, it is marked as
1514 replaceable, otherwise not. */
1517 finish_expr (temp_expr_table_p tab
, int version
, bool replace
)
1519 value_expr_p info
, tmp
;
1522 /* Remove this expression from its dependent lists. The partition dependence
1523 list is retained and transfered later to whomever uses this version. */
1524 for (info
= (value_expr_p
) tab
->version_info
[version
]; info
; info
= tmp
)
1526 partition
= info
->value
;
1527 gcc_assert (tab
->partition_dep_list
[partition
]);
1528 tmp
= remove_value_from_list (&(tab
->partition_dep_list
[partition
]),
1531 free_value_expr (tab
, tmp
);
1532 /* Only clear the bit when the dependency list is emptied via
1533 a replacement. Otherwise kill_expr will take care of it. */
1534 if (!(tab
->partition_dep_list
[partition
]) && replace
)
1535 bitmap_clear_bit (tab
->partition_in_use
, partition
);
1538 free_value_expr (tab
, info
);
1543 tab
->saw_replaceable
= true;
1544 bitmap_set_bit (tab
->replaceable
, version
);
1548 gcc_assert (!bitmap_bit_p (tab
->replaceable
, version
));
1549 tab
->version_info
[version
] = NULL
;
1554 /* Mark the expression associated with VAR as replaceable, and enter
1555 the defining stmt into the version_info table TAB. */
1558 mark_replaceable (temp_expr_table_p tab
, tree var
)
1561 int version
= SSA_NAME_VERSION (var
);
1562 finish_expr (tab
, version
, true);
1564 /* Move the dependence list to the pending list. */
1565 if (tab
->version_info
[version
])
1567 info
= (value_expr_p
) tab
->version_info
[version
];
1568 for ( ; info
->next
; info
= info
->next
)
1570 info
->next
= tab
->pending_dependence
;
1571 tab
->pending_dependence
= (value_expr_p
)tab
->version_info
[version
];
1574 tab
->version_info
[version
] = SSA_NAME_DEF_STMT (var
);
1578 /* This function marks any expression in TAB which is dependent on PARTITION
1579 as NOT replaceable. CLEAR_BIT is used to determine whether partition_in_use
1580 should have its bit cleared. Since this routine can be called within an
1581 EXECUTE_IF_SET_IN_BITMAP, the bit can't always be cleared. */
1584 kill_expr (temp_expr_table_p tab
, int partition
, bool clear_bit
)
1588 /* Mark every active expr dependent on this var as not replaceable. */
1589 while ((ptr
= tab
->partition_dep_list
[partition
]) != NULL
)
1590 finish_expr (tab
, ptr
->value
, false);
1593 bitmap_clear_bit (tab
->partition_in_use
, partition
);
1597 /* This function kills all expressions in TAB which are dependent on virtual
1598 DEFs. CLEAR_BIT determines whether partition_in_use gets cleared. */
1601 kill_virtual_exprs (temp_expr_table_p tab
, bool clear_bit
)
1603 kill_expr (tab
, VIRTUAL_PARTITION (tab
), clear_bit
);
1607 /* This function processes basic block BB, and looks for variables which can
1608 be replaced by their expressions. Results are stored in TAB. */
1611 find_replaceable_in_bb (temp_expr_table_p tab
, basic_block bb
)
1613 block_stmt_iterator bsi
;
1617 var_map map
= tab
->map
;
1622 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1624 stmt
= bsi_stmt (bsi
);
1625 ann
= stmt_ann (stmt
);
1627 if (TREE_CODE (stmt
) == ASM_EXPR
&& ASM_VOLATILE_P (stmt
))
1629 /* Volatile ASM_EXPRs kill all current expressions. */
1630 EXECUTE_IF_SET_IN_BITMAP ((tab
->partition_in_use
), 0, partition
, bi
)
1631 kill_expr (tab
, partition
, false);
1634 /* Determine if this stmt finishes an existing expression. */
1635 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_USE
)
1637 if (tab
->version_info
[SSA_NAME_VERSION (def
)])
1639 /* Mark expression as replaceable unless stmt is volatile. */
1640 if (!ann
->has_volatile_ops
)
1641 mark_replaceable (tab
, def
);
1643 finish_expr (tab
, SSA_NAME_VERSION (def
), false);
1647 /* Next, see if this stmt kills off an active expression. */
1648 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_DEF
)
1650 partition
= var_to_partition (map
, def
);
1651 if (partition
!= NO_PARTITION
&& tab
->partition_dep_list
[partition
])
1652 kill_expr (tab
, partition
, true);
1655 /* Now see if we are creating a new expression or not. */
1656 if (!ann
->has_volatile_ops
)
1657 check_replaceable (tab
, stmt
);
1659 /* Free any unused dependency lists. */
1660 while ((p
= tab
->pending_dependence
))
1662 tab
->pending_dependence
= p
->next
;
1663 free_value_expr (tab
, p
);
1666 /* A V_{MAY,MUST}_DEF kills any expression using a virtual operand. */
1667 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_VIRTUAL_DEFS
))
1668 kill_virtual_exprs (tab
, true);
1673 /* This function is the driver routine for replacement of temporary expressions
1674 in the SSA->normal phase, operating on MAP. If there are replaceable
1675 expressions, a table is returned which maps SSA versions to the
1676 expressions they should be replaced with. A NULL_TREE indicates no
1677 replacement should take place. If there are no replacements at all,
1678 NULL is returned by the function, otherwise an expression vector indexed
1679 by SSA_NAME version numbers. */
1682 find_replaceable_exprs (var_map map
)
1686 temp_expr_table_p table
;
1689 table
= new_temp_expr_table (map
);
1694 find_replaceable_in_bb (table
, bb
);
1695 EXECUTE_IF_SET_IN_BITMAP ((table
->partition_in_use
), 0, i
, bi
)
1697 kill_expr (table
, i
, false);
1701 ret
= free_temp_expr_table (table
);
1706 /* Dump TER expression table EXPR to file F. */
1709 dump_replaceable_exprs (FILE *f
, tree
*expr
)
1713 fprintf (f
, "\nReplacing Expressions\n");
1714 for (x
= 0; x
< (int)num_ssa_names
+ 1; x
++)
1718 var
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_DEF
);
1719 gcc_assert (var
!= NULL_TREE
);
1720 print_generic_expr (f
, var
, TDF_SLIM
);
1721 fprintf (f
, " replace with --> ");
1722 print_generic_expr (f
, TREE_OPERAND (stmt
, 1), TDF_SLIM
);
1729 /* Helper function for discover_nonconstant_array_refs.
1730 Look for ARRAY_REF nodes with non-constant indexes and mark them
1734 discover_nonconstant_array_refs_r (tree
* tp
, int *walk_subtrees
,
1735 void *data ATTRIBUTE_UNUSED
)
1739 if (IS_TYPE_OR_DECL_P (t
))
1741 else if (TREE_CODE (t
) == ARRAY_REF
|| TREE_CODE (t
) == ARRAY_RANGE_REF
)
1743 while (((TREE_CODE (t
) == ARRAY_REF
|| TREE_CODE (t
) == ARRAY_RANGE_REF
)
1744 && is_gimple_min_invariant (TREE_OPERAND (t
, 1))
1745 && (!TREE_OPERAND (t
, 2)
1746 || is_gimple_min_invariant (TREE_OPERAND (t
, 2))))
1747 || (TREE_CODE (t
) == COMPONENT_REF
1748 && (!TREE_OPERAND (t
,2)
1749 || is_gimple_min_invariant (TREE_OPERAND (t
, 2))))
1750 || TREE_CODE (t
) == BIT_FIELD_REF
1751 || TREE_CODE (t
) == REALPART_EXPR
1752 || TREE_CODE (t
) == IMAGPART_EXPR
1753 || TREE_CODE (t
) == VIEW_CONVERT_EXPR
1754 || TREE_CODE (t
) == NOP_EXPR
1755 || TREE_CODE (t
) == CONVERT_EXPR
)
1756 t
= TREE_OPERAND (t
, 0);
1758 if (TREE_CODE (t
) == ARRAY_REF
|| TREE_CODE (t
) == ARRAY_RANGE_REF
)
1760 t
= get_base_address (t
);
1761 if (t
&& DECL_P (t
))
1762 TREE_ADDRESSABLE (t
) = 1;
1772 /* RTL expansion is not able to compile array references with variable
1773 offsets for arrays stored in single register. Discover such
1774 expressions and mark variables as addressable to avoid this
1778 discover_nonconstant_array_refs (void)
1781 block_stmt_iterator bsi
;
1785 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1786 walk_tree (bsi_stmt_ptr (bsi
), discover_nonconstant_array_refs_r
,
1792 /* This function will rewrite the current program using the variable mapping
1793 found in MAP. If the replacement vector VALUES is provided, any
1794 occurrences of partitions with non-null entries in the vector will be
1795 replaced with the expression in the vector instead of its mapped
1799 rewrite_trees (var_map map
, tree
*values
)
1803 block_stmt_iterator si
;
1808 #ifdef ENABLE_CHECKING
1809 /* Search for PHIs where the destination has no partition, but one
1810 or more arguments has a partition. This should not happen and can
1811 create incorrect code. */
1816 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1818 tree T0
= var_to_partition_to_var (map
, PHI_RESULT (phi
));
1820 if (T0
== NULL_TREE
)
1824 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
1826 tree arg
= PHI_ARG_DEF (phi
, i
);
1828 if (TREE_CODE (arg
) == SSA_NAME
1829 && var_to_partition (map
, arg
) != NO_PARTITION
)
1831 fprintf (stderr
, "Argument of PHI is in a partition :(");
1832 print_generic_expr (stderr
, arg
, TDF_SLIM
);
1833 fprintf (stderr
, "), but the result is not :");
1834 print_generic_stmt (stderr
, phi
, TDF_SLIM
);
1835 internal_error ("SSA corruption");
1843 /* Replace PHI nodes with any required copies. */
1844 g
= new_elim_graph (map
->num_partitions
);
1848 for (si
= bsi_start (bb
); !bsi_end_p (si
); )
1850 tree stmt
= bsi_stmt (si
);
1851 use_operand_p use_p
, copy_use_p
;
1852 def_operand_p def_p
;
1853 bool remove
= false, is_copy
= false;
1858 get_stmt_operands (stmt
);
1859 ann
= stmt_ann (stmt
);
1862 if (TREE_CODE (stmt
) == MODIFY_EXPR
1863 && (TREE_CODE (TREE_OPERAND (stmt
, 1)) == SSA_NAME
))
1866 copy_use_p
= NULL_USE_OPERAND_P
;
1867 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
1869 if (replace_use_variable (map
, use_p
, values
))
1878 def_p
= SINGLE_SSA_DEF_OPERAND (stmt
, SSA_OP_DEF
);
1880 if (def_p
.def
!= NULL
)
1882 /* Mark this stmt for removal if it is the list of replaceable
1884 if (values
&& values
[SSA_NAME_VERSION (DEF_FROM_PTR (def_p
))])
1888 if (replace_def_variable (map
, def_p
, NULL
))
1890 /* If both SSA_NAMEs coalesce to the same variable,
1891 mark the now redundant copy for removal. */
1894 gcc_assert (copy_use_p
!= NULL_USE_OPERAND_P
);
1895 if (DEF_FROM_PTR (def_p
) == USE_FROM_PTR (copy_use_p
))
1901 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, iter
, SSA_OP_DEF
)
1902 if (replace_def_variable (map
, def_p
, NULL
))
1905 /* Remove any stmts marked for removal. */
1912 phi
= phi_nodes (bb
);
1916 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1917 eliminate_phi (e
, phi_arg_from_edge (phi
, e
), g
);
1921 delete_elim_graph (g
);
1923 /* If any copies were inserted on edges, actually insert them now. */
1924 bsi_commit_edge_inserts (NULL
);
1928 /* Remove the variables specified in MAP from SSA form. Any debug information
1929 is sent to DUMP. FLAGS indicate what options should be used. */
1932 remove_ssa_form (FILE *dump
, var_map map
, int flags
)
1934 tree_live_info_p liveinfo
;
1938 tree
*values
= NULL
;
1943 /* If we are not combining temps, don't calculate live ranges for variables
1944 with only one SSA version. */
1945 if ((flags
& SSANORM_COMBINE_TEMPS
) == 0)
1946 compact_var_map (map
, VARMAP_NO_SINGLE_DEFS
);
1948 compact_var_map (map
, VARMAP_NORMAL
);
1950 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1951 dump_var_map (dump_file
, map
);
1953 liveinfo
= coalesce_ssa_name (map
, flags
);
1955 /* Make sure even single occurrence variables are in the list now. */
1956 if ((flags
& SSANORM_COMBINE_TEMPS
) == 0)
1957 compact_var_map (map
, VARMAP_NORMAL
);
1959 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1961 fprintf (dump_file
, "After Coalescing:\n");
1962 dump_var_map (dump_file
, map
);
1965 if (flags
& SSANORM_PERFORM_TER
)
1967 values
= find_replaceable_exprs (map
);
1968 if (values
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
1969 dump_replaceable_exprs (dump_file
, values
);
1972 /* Assign real variables to the partitions now. */
1975 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1977 fprintf (dump_file
, "After Root variable replacement:\n");
1978 dump_var_map (dump_file
, map
);
1981 if ((flags
& SSANORM_COMBINE_TEMPS
) && liveinfo
)
1983 coalesce_vars (map
, liveinfo
);
1984 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1986 fprintf (dump_file
, "After variable memory coalescing:\n");
1987 dump_var_map (dump_file
, map
);
1992 delete_tree_live_info (liveinfo
);
1994 rewrite_trees (map
, values
);
1999 /* Remove phi nodes which have been translated back to real variables. */
2002 for (phi
= phi_nodes (bb
); phi
; phi
= next
)
2004 next
= PHI_CHAIN (phi
);
2005 if ((flags
& SSANORM_REMOVE_ALL_PHIS
)
2006 || var_to_partition (map
, PHI_RESULT (phi
)) != NO_PARTITION
)
2007 remove_phi_node (phi
, NULL_TREE
, bb
);
2011 /* we no longer maintain the SSA operand cache at this point. */
2012 fini_ssa_operands ();
2017 /* Take the current function out of SSA form, as described in
2018 R. Morgan, ``Building an Optimizing Compiler'',
2019 Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */
2022 rewrite_out_of_ssa (void)
2026 int ssa_flags
= (SSANORM_REMOVE_ALL_PHIS
| SSANORM_USE_COALESCE_LIST
);
2028 if (!flag_tree_live_range_split
)
2029 ssa_flags
|= SSANORM_COALESCE_PARTITIONS
;
2031 eliminate_virtual_phis ();
2033 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2034 dump_tree_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);
2036 /* We cannot allow unssa to un-gimplify trees before we instrument them. */
2037 if (flag_tree_ter
&& !flag_mudflap
)
2038 var_flags
= SSA_VAR_MAP_REF_COUNT
;
2040 map
= create_ssa_var_map (var_flags
);
2042 if (flag_tree_combine_temps
)
2043 ssa_flags
|= SSANORM_COMBINE_TEMPS
;
2044 if (flag_tree_ter
&& !flag_mudflap
)
2045 ssa_flags
|= SSANORM_PERFORM_TER
;
2047 remove_ssa_form (dump_file
, map
, ssa_flags
);
2049 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2050 dump_tree_cfg (dump_file
, dump_flags
& ~TDF_DETAILS
);
2052 /* Do some cleanups which reduce the amount of data the
2053 tree->rtl expanders deal with. */
2054 cfg_remove_useless_stmts ();
2056 /* Flush out flow graph and SSA data. */
2057 delete_var_map (map
);
2059 /* Mark arrays indexed with non-constant indices with TREE_ADDRESSABLE. */
2060 discover_nonconstant_array_refs ();
2064 /* Define the parameters of the out of SSA pass. */
2066 struct tree_opt_pass pass_del_ssa
=
2068 "optimized", /* name */
2070 rewrite_out_of_ssa
, /* execute */
2073 0, /* static_pass_number */
2074 TV_TREE_SSA_TO_NORMAL
, /* tv_id */
2075 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
2076 0, /* properties_provided */
2077 /* ??? If TER is enabled, we also kill gimple. */
2078 PROP_ssa
, /* properties_destroyed */
2079 TODO_verify_ssa
| TODO_verify_flow
2080 | TODO_verify_stmts
, /* todo_flags_start */
2081 TODO_dump_func
| TODO_ggc_collect
, /* todo_flags_finish */