diff options
| author | amacleod <amacleod@138bc75d-0d04-0410-961f-82ee72b054a4> | 2006-12-10 21:25:40 +0000 |
|---|---|---|
| committer | amacleod <amacleod@138bc75d-0d04-0410-961f-82ee72b054a4> | 2006-12-10 21:25:40 +0000 |
| commit | 2d043327e6bf9c316751af014a81548f08284a7b (patch) | |
| tree | 02feab0e9ac8689b190a759c435c1c7653207328 | |
| parent | 322026327df36027e148aabd5df318c8376ea1ab (diff) | |
| download | gcc-2d043327e6bf9c316751af014a81548f08284a7b.tar.gz | |
New out of ssa Coalescer.
2006-12-10 Andrew MacLeod <amacleod@redhat.com>
* common.opt (-ftree-lrs): Remove live range splitting option.
* makefile.in: Add tree-ssa-coalesce.o and reduce header dependancies.
* opts.c (decode_options): Remove flag_tree_live_range_split.
* tree-flow.h (struct var_ann_d): Rename fields from root_ to base_.
* tree-flow-inline.h (single_imm_use_p): New. Check for single use.
* tree-outof-ssa.c: Remove header files which aren't needed.
(SSANORM_*): Remove flags.
(print_exprs_edge, coalesce_abnormal_edges, coalesce_phi_operands,
coalesce_result_decls_and_copies, coalesce_asm_operands): Remove.
(coalesce_ssa_name): Move to tree-ssa-coalesce.c.
(assign_vars): Use Basevar instead of root_var structure.
(replace_def_variable): Dont do anything if def is replaceable.
(remove_ssa_form): Integrate functional changes.
(rewrite_out_of_ssa): Remove live-range_split option.
* tree-ssa-coalesce.c: New File for ssa-name coalescing.
(coalesce_cost): Calculate the cost of a coalesce.
(coalesce_cost_bb): Calculate the coalesce cost within a BB.
(coalesce_cost_edge): Calculate the coalesce cost on an edge.
(pop_cost_one_pair): Remove the best coalesce with cost 1 from the list.
(pop_best_coalesce): Remove the best coalesce from the list.
(coalesce_pair_map_hash): Calculate coalesce pair hash.
(coalesce_pair_map_eq): Compare 2 coalesce pairs for hash function.
(create_coalesce_list): Create a coalesce list object.
(delete_coalesce_list): Free a coalesce list object.
(find_coalesce_pair): Find matching pair in the coalesce list.
(add_cost_one_coalesce): Add a coalesce to the "cost one" list.
(add_coalesce): Add a coalesce to the coalesce list.
(compare_pairs): Comparision function to determine pair sorted order.
(num_coalesce_pairs): Number of coalesced pairs.
(first_coalesce_pair, end_coalesce_pair_p, next_coalesce_pair):
Coalesce pair iterator functions.
(sort_coalesce_list): Sort coalesce pairs in order of expense.
(dump_coalesce_list): Show coalesce list.
(ssa_conflicts_new): Create an SSA conflict graph.
(ssa_conflicts_delete): Delete an SSA conflict graph.
(ssa_conflicts_test_p): Test for conflicts.
(ssa_conflicts_add_one): Add a single conflict.
(ssa_conflicts_add): Add a conflict pair.
(ssa_conflicts_merge): Merge conflicts.
(struct live_track_d): Struct for tracking live partitions.
(new_live_track): Create new live_track object.
(delete_live_track): Delete a live_track object.
(live_track_remove_partition): Remove a partition from the live list.
(live_track_add_partition): Add a partition from the live list.
(live_track_clear_var): Take VAR from the live list.
(live_track_live_p): Is var live?
(live_track_process_use): Make var come alive.
(live_track_process_def): Make var go dead, add conflicts.
(live_track_init): Initialize to a live on exit set.
(live_track_clear_base_vars): Clear live partitions.
(build_ssa_conflict_graph): Build a conflict graph.
(print_exprs): Common debug output routine.
(abnormal_corrupt): Output info about a failed coalesce across an
abnormal edge.
(fail_abnormal_edge_coalesce): Output info about a failed MUST_COALESCE.
(create_outofssa_var_map): Create a var map and coalesce list.
(attempt_coalesce): Coalesce a pair.
(coalesce_partitions): Coalesce all pairs in a coalesce list.
(coalesce_ssa_name): Entry point. Determine what ssa_names to coalesce.
* tree-ssa-live.c: Remove header files which aren't needed.
(var_map_base_init): New. Initialize a basevar list.
(var_map_base_fini): New. Finish a basevar list.
(init_var_map): Initialize new fields.
(delete_var_map): Free new fields.
(var_union): Use renamed fields.
(compact_var_map): Remove.
(partition_to_view_init): Use renamed fields, change order of an if.
(partition_view_fini): Use renamed fields.
(partition_view_normal): Create basevar list if requested.
(partition_view_bitmap): Create a view based on a bitmap of partitions.
(change_partition_var): Use renamed fields.
(create_ssa_var_map): Remove.
(tpa_init, tpa_remove_partition, tpa_delete, tpa_compact,
root_var_init): Remove.
(partition_pair_map_hash, partition_pair_map_eq, create_coalesce_list,
delete_coalesce_list, find_partition_pair, coalesce_cost, add_coalesce,
compare_pairs, num_coalesce_pairs, first_partition_pair,
end_partition_pair_p, next_partition_pair, sort_coalesce_list,
pop_best_coalesce, add_conflicts_if_valid, set_if_valid,
build_tree_conflict_graph, coalesce_tpa_members, dump_coalesce_list,
tpa_dump): Moved to tree-ssa-coalesce.c and/or renamed there.
(dump_var_map): Use renamed fields.
* tree-ssa-live.h (struct _var_map): Modify fields.
(partition_to_var, version_to_var, var_to_partition): Use renamed
fields.
(basevar_index): New. Index of the base variable of a partition.
(num_basevars): New. Number of unique base variables in partition map.
(register_ssa_partition): Use renamed fields.
(struct tree_partition_associator_d): Remove.
(tpa_num_trees, tpa_tree, tpa_first_partition, tpa_next_partition,
tpa_find_tree, tpa_decompact, root_var_init, root_var_num,
root_var, root_var_first_partition, root_var_next_partition,
root_var_dump, root_var_delete, root_var_remove_partition,
root_var_find, root_var_compact, root_var_decompact): Remove.
(struct partition_pair, struct coalesce_list_d): Moved to
tree-ssa-coalesce.c
* tree-ssa-ter.c: Remove header files which aren't needed.
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@119711 138bc75d-0d04-0410-961f-82ee72b054a4
| -rw-r--r-- | gcc/ChangeLog | 100 | ||||
| -rw-r--r-- | gcc/Makefile.in | 25 | ||||
| -rw-r--r-- | gcc/common.opt | 4 | ||||
| -rw-r--r-- | gcc/opts.c | 1 | ||||
| -rw-r--r-- | gcc/tree-flow-inline.h | 12 | ||||
| -rw-r--r-- | gcc/tree-flow.h | 8 | ||||
| -rw-r--r-- | gcc/tree-outof-ssa.c | 601 | ||||
| -rw-r--r-- | gcc/tree-ssa-coalesce.c | 1355 | ||||
| -rw-r--r-- | gcc/tree-ssa-live.c | 1375 | ||||
| -rw-r--r-- | gcc/tree-ssa-live.h | 395 | ||||
| -rw-r--r-- | gcc/tree-ssa-ter.c | 18 |
11 files changed, 1851 insertions, 2043 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index b984524281d..60ff40a5e82 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,103 @@ +2006-12-10 Andrew MacLeod <amacleod@redhat.com> + + * common.opt (-ftree-lrs): Remove live range splitting option. + * makefile.in: Add tree-ssa-coalesce.o and reduce header dependancies. + * opts.c (decode_options): Remove flag_tree_live_range_split. + * tree-flow.h (struct var_ann_d): Rename fields from root_ to base_. + * tree-flow-inline.h (single_imm_use_p): New. Check for single use. + * tree-outof-ssa.c: Remove header files which aren't needed. + (SSANORM_*): Remove flags. + (print_exprs_edge, coalesce_abnormal_edges, coalesce_phi_operands, + coalesce_result_decls_and_copies, coalesce_asm_operands): Remove. + (coalesce_ssa_name): Move to tree-ssa-coalesce.c. + (assign_vars): Use Basevar instead of root_var structure. + (replace_def_variable): Dont do anything if def is replaceable. + (remove_ssa_form): Integrate functional changes. + (rewrite_out_of_ssa): Remove live-range_split option. + * tree-ssa-coalesce.c: New File for ssa-name coalescing. + (coalesce_cost): Calculate the cost of a coalesce. + (coalesce_cost_bb): Calculate the coalesce cost within a BB. + (coalesce_cost_edge): Calculate the coalesce cost on an edge. + (pop_cost_one_pair): Remove the best coalesce with cost 1 from the list. + (pop_best_coalesce): Remove the best coalesce from the list. + (coalesce_pair_map_hash): Calculate coalesce pair hash. + (coalesce_pair_map_eq): Compare 2 coalesce pairs for hash function. + (create_coalesce_list): Create a coalesce list object. + (delete_coalesce_list): Free a coalesce list object. + (find_coalesce_pair): Find matching pair in the coalesce list. + (add_cost_one_coalesce): Add a coalesce to the "cost one" list. + (add_coalesce): Add a coalesce to the coalesce list. + (compare_pairs): Comparision function to determine pair sorted order. + (num_coalesce_pairs): Number of coalesced pairs. + (first_coalesce_pair, end_coalesce_pair_p, next_coalesce_pair): + Coalesce pair iterator functions. + (sort_coalesce_list): Sort coalesce pairs in order of expense. + (dump_coalesce_list): Show coalesce list. + (ssa_conflicts_new): Create an SSA conflict graph. + (ssa_conflicts_delete): Delete an SSA conflict graph. + (ssa_conflicts_test_p): Test for conflicts. + (ssa_conflicts_add_one): Add a single conflict. + (ssa_conflicts_add): Add a conflict pair. + (ssa_conflicts_merge): Merge conflicts. + (struct live_track_d): Struct for tracking live partitions. + (new_live_track): Create new live_track object. + (delete_live_track): Delete a live_track object. + (live_track_remove_partition): Remove a partition from the live list. + (live_track_add_partition): Add a partition from the live list. + (live_track_clear_var): Take VAR from the live list. + (live_track_live_p): Is var live? + (live_track_process_use): Make var come alive. + (live_track_process_def): Make var go dead, add conflicts. + (live_track_init): Initialize to a live on exit set. + (live_track_clear_base_vars): Clear live partitions. + (build_ssa_conflict_graph): Build a conflict graph. + (print_exprs): Common debug output routine. + (abnormal_corrupt): Output info about a failed coalesce across an + abnormal edge. + (fail_abnormal_edge_coalesce): Output info about a failed MUST_COALESCE. + (create_outofssa_var_map): Create a var map and coalesce list. + (attempt_coalesce): Coalesce a pair. + (coalesce_partitions): Coalesce all pairs in a coalesce list. + (coalesce_ssa_name): Entry point. Determine what ssa_names to coalesce. + * tree-ssa-live.c: Remove header files which aren't needed. + (var_map_base_init): New. Initialize a basevar list. + (var_map_base_fini): New. Finish a basevar list. + (init_var_map): Initialize new fields. + (delete_var_map): Free new fields. + (var_union): Use renamed fields. + (compact_var_map): Remove. + (partition_to_view_init): Use renamed fields, change order of an if. + (partition_view_fini): Use renamed fields. + (partition_view_normal): Create basevar list if requested. + (partition_view_bitmap): Create a view based on a bitmap of partitions. + (change_partition_var): Use renamed fields. + (create_ssa_var_map): Remove. + (tpa_init, tpa_remove_partition, tpa_delete, tpa_compact, + root_var_init): Remove. + (partition_pair_map_hash, partition_pair_map_eq, create_coalesce_list, + delete_coalesce_list, find_partition_pair, coalesce_cost, add_coalesce, + compare_pairs, num_coalesce_pairs, first_partition_pair, + end_partition_pair_p, next_partition_pair, sort_coalesce_list, + pop_best_coalesce, add_conflicts_if_valid, set_if_valid, + build_tree_conflict_graph, coalesce_tpa_members, dump_coalesce_list, + tpa_dump): Moved to tree-ssa-coalesce.c and/or renamed there. + (dump_var_map): Use renamed fields. + * tree-ssa-live.h (struct _var_map): Modify fields. + (partition_to_var, version_to_var, var_to_partition): Use renamed + fields. + (basevar_index): New. Index of the base variable of a partition. + (num_basevars): New. Number of unique base variables in partition map. + (register_ssa_partition): Use renamed fields. + (struct tree_partition_associator_d): Remove. + (tpa_num_trees, tpa_tree, tpa_first_partition, tpa_next_partition, + tpa_find_tree, tpa_decompact, root_var_init, root_var_num, + root_var, root_var_first_partition, root_var_next_partition, + root_var_dump, root_var_delete, root_var_remove_partition, + root_var_find, root_var_compact, root_var_decompact): Remove. + (struct partition_pair, struct coalesce_list_d): Moved to + tree-ssa-coalesce.c + * tree-ssa-ter.c: Remove header files which aren't needed. + 2006-12-10 Steven Bosscher <steven@gcc.gnu.org> * cse.c: (struct cse_basic_block_data): Remove LAST field. diff --git a/gcc/Makefile.in b/gcc/Makefile.in index bf954ebab88..8da131d5ee0 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -985,7 +985,7 @@ OBJS-common = \ tree-vect-generic.o tree-ssa-loop.o tree-ssa-loop-niter.o \ tree-ssa-loop-manip.o tree-ssa-threadupdate.o tree-ssa-threadedge.o \ tree-vectorizer.o tree-vect-analyze.o tree-vect-transform.o \ - tree-vect-patterns.o tree-ssa-loop-prefetch.o \ + tree-vect-patterns.o tree-ssa-loop-prefetch.o tree-ssa-coalesce.o \ tree-ssa-loop-ivcanon.o tree-ssa-propagate.o tree-ssa-address.o \ tree-ssa-math-opts.o \ tree-ssa-loop-ivopts.o tree-if-conv.o tree-ssa-loop-unswitch.o \ @@ -1851,17 +1851,14 @@ tree-into-ssa.o : tree-into-ssa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \ bitmap.h $(CFGLOOP_H) $(FLAGS_H) hard-reg-set.h $(HASHTAB_H) \ $(TREE_GIMPLE_H) $(TREE_INLINE_H) $(VARRAY_H) vecprim.h tree-ssa-ter.o : tree-ssa-ter.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \ - $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) output.h $(DIAGNOSTIC_H) \ - $(FUNCTION_H) $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \ - langhooks.h tree-pass.h $(TREE_SSA_LIVE_H) $(BASIC_BLOCK_H) bitmap.h \ - $(FLAGS_H) $(GGC_H) hard-reg-set.h $(HASHTAB_H) $(TREE_GIMPLE_H) \ - $(TREE_INLINE_H) $(VARRAY_H) toplev.h vecprim.h + $(TREE_H) $(DIAGNOSTIC_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \ + $(TREE_SSA_LIVE_H) bitmap.h +tree-ssa-coalesce.o : tree-ssa-coalesce.c $(TREE_FLOW_H) $(CONFIG_H) \ + $(SYSTEM_H) $(TREE_H) $(DIAGNOSTIC_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \ + $(TREE_SSA_LIVE_H) bitmap.h $(FLAGS_H) $(HASHTAB_H) toplev.h tree-outof-ssa.o : tree-outof-ssa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \ - $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) output.h $(DIAGNOSTIC_H) \ - $(FUNCTION_H) $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \ - langhooks.h tree-pass.h $(TREE_SSA_LIVE_H) $(BASIC_BLOCK_H) bitmap.h \ - $(FLAGS_H) $(GGC_H) hard-reg-set.h $(HASHTAB_H) $(TREE_GIMPLE_H) \ - $(TREE_INLINE_H) $(VARRAY_H) toplev.h vecprim.h + $(TREE_H) $(DIAGNOSTIC_H) $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \ + tree-pass.h $(TREE_SSA_LIVE_H) $(BASIC_BLOCK_H) bitmap.h $(GGC_H) toplev.h tree-ssa-dse.o : tree-ssa-dse.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \ $(TM_H) $(GGC_H) $(TREE_H) $(RTL_H) $(TM_P_H) $(BASIC_BLOCK_H) \ $(TREE_FLOW_H) tree-pass.h $(TREE_DUMP_H) domwalk.h $(FLAGS_H) \ @@ -1913,10 +1910,8 @@ tree-phinodes.o : tree-phinodes.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \ domwalk.o : domwalk.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \ $(TREE_H) $(BASIC_BLOCK_H) $(TREE_FLOW_H) domwalk.h $(GGC_H) tree-ssa-live.o : tree-ssa-live.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \ - $(TREE_H) $(DIAGNOSTIC_H) $(FUNCTION_H) $(TIMEVAR_H) \ - $(TM_H) coretypes.h $(TREE_DUMP_H) $(TREE_SSA_LIVE_H) $(BASIC_BLOCK_H) \ - bitmap.h $(FLAGS_H) $(HASHTAB_H) $(TREE_GIMPLE_H) $(TREE_INLINE_H) \ - $(VARRAY_H) toplev.h vecprim.h + $(TREE_H) $(DIAGNOSTIC_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \ + $(TREE_SSA_LIVE_H) bitmap.h toplev.h tree-ssa-copyrename.o : tree-ssa-copyrename.c $(TREE_FLOW_H) $(CONFIG_H) \ $(SYSTEM_H) $(TREE_H) $(DIAGNOSTIC_H) $(FUNCTION_H) $(TIMEVAR_H) tree-pass.h \ $(TM_H) coretypes.h $(TREE_DUMP_H) $(TREE_SSA_LIVE_H) $(BASIC_BLOCK_H) \ diff --git a/gcc/common.opt b/gcc/common.opt index 2251b86e34a..7ec6f4723cd 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -1003,10 +1003,6 @@ ftree-ter Common Report Var(flag_tree_ter) Replace temporary expressions in the SSA->normal pass -ftree-lrs -Common Report Var(flag_tree_live_range_split) -Perform live range splitting during the SSA->normal pass - ftree-vrp Common Report Var(flag_tree_vrp) Init(0) Perform Value Range Propagation on trees diff --git a/gcc/opts.c b/gcc/opts.c index da16f7bf341..b31d67d94a6 100644 --- a/gcc/opts.c +++ b/gcc/opts.c @@ -449,7 +449,6 @@ decode_options (unsigned int argc, const char **argv) flag_tree_dom = 1; flag_tree_dse = 1; flag_tree_ter = 1; - flag_tree_live_range_split = 1; flag_tree_sra = 1; flag_tree_copyrename = 1; flag_tree_fre = 1; diff --git a/gcc/tree-flow-inline.h b/gcc/tree-flow-inline.h index f19faa1c4ff..bc4c3946335 100644 --- a/gcc/tree-flow-inline.h +++ b/gcc/tree-flow-inline.h @@ -541,6 +541,18 @@ has_single_use (tree var) return (ptr != ptr->next && ptr == ptr->next->next); } + +/* If VAR has only a single immediate use, return true. */ +static inline bool +single_imm_use_p (tree var) +{ + ssa_use_operand_t *ptr; + + ptr = &(SSA_NAME_IMM_USE_NODE (var)); + return (ptr != ptr->next && ptr == ptr->next->next); +} + + /* If VAR has only a single immediate use, return true, and set USE_P and STMT to the use pointer and stmt of occurrence. */ static inline bool diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h index b3aa655f556..bb6b4ae2113 100644 --- a/gcc/tree-flow.h +++ b/gcc/tree-flow.h @@ -218,8 +218,8 @@ struct var_ann_d GTY(()) been seen yet or not. */ unsigned out_of_ssa_tag : 1; - /* Used when building root_var structures in tree_ssa_live.[ch]. */ - unsigned root_var_processed : 1; + /* Used when building base variable structures in a var_map. */ + unsigned base_var_processed : 1; /* Nonzero if this variable is in the alias set of another variable. */ unsigned is_aliased : 1; @@ -257,8 +257,8 @@ struct var_ann_d GTY(()) variable represents storage for. */ unsigned partition; - /* Used by the root-var object in tree-ssa-live.[ch]. */ - unsigned root_index; + /* Used by var_map for the base index of ssa base variables. */ + unsigned base_index; /* During into-ssa and the dominator optimizer, this field holds the current version of this variable (an SSA_NAME). */ diff --git a/gcc/tree-outof-ssa.c b/gcc/tree-outof-ssa.c index 5edea642805..f591eb5ed97 100644 --- a/gcc/tree-outof-ssa.c +++ b/gcc/tree-outof-ssa.c @@ -1,5 +1,5 @@ /* Convert a program in SSA form into Normal form. - Copyright (C) 2004, 2005 Free Software Foundation, Inc. + Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc. Contributed by Andrew Macleod <amacleod@redhat.com> This file is part of GCC. @@ -24,34 +24,17 @@ Boston, MA 02110-1301, USA. */ #include "coretypes.h" #include "tm.h" #include "tree.h" -#include "flags.h" -#include "rtl.h" -#include "tm_p.h" #include "ggc.h" -#include "langhooks.h" -#include "hard-reg-set.h" #include "basic-block.h" -#include "output.h" -#include "expr.h" -#include "function.h" #include "diagnostic.h" #include "bitmap.h" #include "tree-flow.h" -#include "tree-gimple.h" -#include "tree-inline.h" -#include "varray.h" #include "timevar.h" -#include "hashtab.h" #include "tree-dump.h" #include "tree-ssa-live.h" #include "tree-pass.h" #include "toplev.h" -#include "vecprim.h" -/* Flags to pass to remove_ssa_form. */ - -#define SSANORM_PERFORM_TER 0x1 -#define SSANORM_COALESCE_PARTITIONS 0x4 /* Used to hold all the components required to do SSA PHI elimination. The node and pred/succ list is a simple linear list of nodes and @@ -101,36 +84,6 @@ typedef struct _elim_graph { } *elim_graph; -/* Local functions. */ -static tree create_temp (tree); -static void insert_copy_on_edge (edge, tree, tree); -static elim_graph new_elim_graph (int); -static inline void delete_elim_graph (elim_graph); -static inline void clear_elim_graph (elim_graph); -static inline int elim_graph_size (elim_graph); -static inline void elim_graph_add_node (elim_graph, tree); -static inline void elim_graph_add_edge (elim_graph, int, int); -static inline int elim_graph_remove_succ_edge (elim_graph, int); - -static inline void eliminate_name (elim_graph, tree); -static void eliminate_build (elim_graph, basic_block); -static void elim_forward (elim_graph, int); -static int elim_unvisited_predecessor (elim_graph, int); -static void elim_backward (elim_graph, int); -static void elim_create (elim_graph, int); -static void eliminate_phi (edge, elim_graph); -static tree_live_info_p coalesce_ssa_name (var_map, int); -static void assign_vars (var_map); -static bool replace_use_variable (var_map, use_operand_p, tree *); -static bool replace_def_variable (var_map, def_operand_p, tree *); -static void eliminate_virtual_phis (void); -static void coalesce_abnormal_edges (var_map, conflict_graph, root_var_p); -static void print_exprs (FILE *, const char *, tree, const char *, tree, - const char *); -static void print_exprs_edge (FILE *, edge, const char *, tree, const char *, - tree); - - /* Create a temporary variable based on the type of variable T. Use T's name as the prefix. */ @@ -489,6 +442,7 @@ elim_create (elim_graph g, int T) } + /* Eliminate all the phi nodes on edge E in graph G. */ static void @@ -541,407 +495,15 @@ eliminate_phi (edge e, elim_graph g) } -/* Shortcut routine to print messages to file F of the form: - "STR1 EXPR1 STR2 EXPR2 STR3." */ - -static void -print_exprs (FILE *f, const char *str1, tree expr1, const char *str2, - tree expr2, const char *str3) -{ - fprintf (f, "%s", str1); - print_generic_expr (f, expr1, TDF_SLIM); - fprintf (f, "%s", str2); - print_generic_expr (f, expr2, TDF_SLIM); - fprintf (f, "%s", str3); -} - - -/* Shortcut routine to print abnormal edge messages to file F of the form: - "STR1 EXPR1 STR2 EXPR2 across edge E. */ - -static void -print_exprs_edge (FILE *f, edge e, const char *str1, tree expr1, - const char *str2, tree expr2) -{ - print_exprs (f, str1, expr1, str2, expr2, " across an abnormal edge"); - fprintf (f, " from BB%d->BB%d\n", e->src->index, - e->dest->index); -} - - -/* Coalesce partitions in MAP which are live across abnormal edges in GRAPH. - RV is the root variable groupings of the partitions in MAP. Since code - cannot be inserted on these edges, failure to coalesce something across - an abnormal edge is an error. */ - -static void -coalesce_abnormal_edges (var_map map, conflict_graph graph, root_var_p rv) -{ - basic_block bb; - edge e; - tree phi, var, tmp; - int x, y, z; - edge_iterator ei; - - /* Code cannot be inserted on abnormal edges. Look for all abnormal - edges, and coalesce any PHI results with their arguments across - that edge. */ - - FOR_EACH_BB (bb) - FOR_EACH_EDGE (e, ei, bb->succs) - if (e->dest != EXIT_BLOCK_PTR && e->flags & EDGE_ABNORMAL) - for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi)) - { - /* Visit each PHI on the destination side of this abnormal - edge, and attempt to coalesce the argument with the result. */ - var = PHI_RESULT (phi); - x = var_to_partition (map, var); - - /* Ignore results which are not relevant. */ - if (x == NO_PARTITION) - continue; - - tmp = PHI_ARG_DEF (phi, e->dest_idx); -#ifdef ENABLE_CHECKING - if (!phi_ssa_name_p (tmp)) - { - print_exprs_edge (stderr, e, - "\nConstant argument in PHI. Can't insert :", - var, " = ", tmp); - internal_error ("SSA corruption"); - } -#else - gcc_assert (phi_ssa_name_p (tmp)); -#endif - y = var_to_partition (map, tmp); - gcc_assert (x != NO_PARTITION); - gcc_assert (y != NO_PARTITION); -#ifdef ENABLE_CHECKING - if (root_var_find (rv, x) != root_var_find (rv, y)) - { - print_exprs_edge (stderr, e, "\nDifferent root vars: ", - root_var (rv, root_var_find (rv, x)), - " and ", - root_var (rv, root_var_find (rv, y))); - internal_error ("SSA corruption"); - } -#else - gcc_assert (root_var_find (rv, x) == root_var_find (rv, y)); -#endif - - if (x != y) - { -#ifdef ENABLE_CHECKING - if (conflict_graph_conflict_p (graph, x, y)) - { - print_exprs_edge (stderr, e, "\n Conflict ", - partition_to_var (map, x), - " and ", partition_to_var (map, y)); - internal_error ("SSA corruption"); - } -#else - gcc_assert (!conflict_graph_conflict_p (graph, x, y)); -#endif - - /* Now map the partitions back to their real variables. */ - var = partition_to_var (map, x); - tmp = partition_to_var (map, y); - if (dump_file && (dump_flags & TDF_DETAILS)) - { - print_exprs_edge (dump_file, e, - "ABNORMAL: Coalescing ", - var, " and ", tmp); - } - z = var_union (map, var, tmp); -#ifdef ENABLE_CHECKING - if (z == NO_PARTITION) - { - print_exprs_edge (stderr, e, "\nUnable to coalesce", - partition_to_var (map, x), " and ", - partition_to_var (map, y)); - internal_error ("SSA corruption"); - } -#else - gcc_assert (z != NO_PARTITION); -#endif - gcc_assert (z == x || z == y); - if (z == x) - conflict_graph_merge_regs (graph, x, y); - else - conflict_graph_merge_regs (graph, y, x); - } - } -} - -/* Coalesce potential copies via PHI arguments. */ - -static void -coalesce_phi_operands (var_map map, coalesce_list_p cl) -{ - basic_block bb; - tree phi; - - FOR_EACH_BB (bb) - { - for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) - { - tree res = PHI_RESULT (phi); - int p = var_to_partition (map, res); - int x; - - if (p == NO_PARTITION) - continue; - - for (x = 0; x < PHI_NUM_ARGS (phi); x++) - { - tree arg = PHI_ARG_DEF (phi, x); - int p2; - - if (TREE_CODE (arg) != SSA_NAME) - continue; - if (SSA_NAME_VAR (res) != SSA_NAME_VAR (arg)) - continue; - p2 = var_to_partition (map, PHI_ARG_DEF (phi, x)); - if (p2 != NO_PARTITION) - { - edge e = PHI_ARG_EDGE (phi, x); - add_coalesce (cl, p, p2, - coalesce_cost (EDGE_FREQUENCY (e), - maybe_hot_bb_p (bb), - EDGE_CRITICAL_P (e))); - } - } - } - } -} - -/* Coalesce all the result decls together. */ - -static void -coalesce_result_decls (var_map map, coalesce_list_p cl) -{ - unsigned int i, x; - tree var = NULL; - - for (i = x = 0; x < num_var_partitions (map); x++) - { - tree p = partition_to_var (map, x); - if (TREE_CODE (SSA_NAME_VAR (p)) == RESULT_DECL) - { - if (var == NULL_TREE) - { - var = p; - i = x; - } - else - add_coalesce (cl, i, x, - coalesce_cost (EXIT_BLOCK_PTR->frequency, - maybe_hot_bb_p (EXIT_BLOCK_PTR), - false)); - } - } -} - -/* Coalesce matching constraints in asms. */ - -static void -coalesce_asm_operands (var_map map, coalesce_list_p cl) -{ - basic_block bb; - - FOR_EACH_BB (bb) - { - block_stmt_iterator bsi; - for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) - { - tree stmt = bsi_stmt (bsi); - unsigned long noutputs, i; - tree *outputs, link; - - if (TREE_CODE (stmt) != ASM_EXPR) - continue; - - noutputs = list_length (ASM_OUTPUTS (stmt)); - outputs = (tree *) alloca (noutputs * sizeof (tree)); - for (i = 0, link = ASM_OUTPUTS (stmt); link; - ++i, link = TREE_CHAIN (link)) - outputs[i] = TREE_VALUE (link); - - for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link)) - { - const char *constraint - = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link))); - tree input = TREE_VALUE (link); - char *end; - unsigned long match; - int p1, p2; - - if (TREE_CODE (input) != SSA_NAME && !DECL_P (input)) - continue; - - match = strtoul (constraint, &end, 10); - if (match >= noutputs || end == constraint) - continue; - - if (TREE_CODE (outputs[match]) != SSA_NAME - && !DECL_P (outputs[match])) - continue; - - p1 = var_to_partition (map, outputs[match]); - if (p1 == NO_PARTITION) - continue; - p2 = var_to_partition (map, input); - if (p2 == NO_PARTITION) - continue; - - add_coalesce (cl, p1, p2, coalesce_cost (REG_BR_PROB_BASE, - maybe_hot_bb_p (bb), - false)); - } - } - } -} - -/* Reduce the number of live ranges in MAP. Live range information is - returned if FLAGS indicates that we are combining temporaries, otherwise - NULL is returned. The only partitions which are associated with actual - variables at this point are those which are forced to be coalesced for - various reason. (live on entry, live across abnormal edges, etc.). */ - -static tree_live_info_p -coalesce_ssa_name (var_map map, int flags) -{ - unsigned num, x; - sbitmap live; - root_var_p rv; - tree_live_info_p liveinfo; - conflict_graph graph; - coalesce_list_p cl = NULL; - sbitmap_iterator sbi; - - if (num_var_partitions (map) <= 1) - return NULL; - - liveinfo = calculate_live_ranges (map); - rv = root_var_init (map); - - /* Remove single element variable from the list. */ - root_var_compact (rv); - - cl = create_coalesce_list (map); - - coalesce_phi_operands (map, cl); - coalesce_result_decls (map, cl); - coalesce_asm_operands (map, cl); - - /* Build a conflict graph. */ - graph = build_tree_conflict_graph (liveinfo, rv, cl); - - if (cl) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Before sorting:\n"); - dump_coalesce_list (dump_file, cl); - } - - sort_coalesce_list (cl); - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "\nAfter sorting:\n"); - dump_coalesce_list (dump_file, cl); - } - } - - /* Put the single element variables back in. */ - root_var_decompact (rv); - - /* First, coalesce all live on entry variables to their root variable. - This will ensure the first use is coming from the correct location. */ - - num = num_var_partitions (map); - live = sbitmap_alloc (num); - sbitmap_zero (live); - - /* Set 'live' vector to indicate live on entry partitions. */ - for (x = 0 ; x < num; x++) - { - tree var = partition_to_var (map, x); - if (gimple_default_def (cfun, SSA_NAME_VAR (var)) == var) - SET_BIT (live, x); - } - - delete_tree_live_info (liveinfo); - liveinfo = NULL; - - /* Assign root variable as partition representative for each live on entry - partition. */ - EXECUTE_IF_SET_IN_SBITMAP (live, 0, x, sbi) - { - tree var = root_var (rv, root_var_find (rv, x)); - var_ann_t ann = var_ann (var); - /* If these aren't already coalesced... */ - if (partition_to_var (map, x) != var) - { - /* This root variable should have not already been assigned - to another partition which is not coalesced with this one. */ - gcc_assert (!ann->out_of_ssa_tag); - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - print_exprs (dump_file, "Must coalesce ", - partition_to_var (map, x), - " with the root variable ", var, ".\n"); - } - - change_partition_var (map, var, x); - } - } - - sbitmap_free (live); - - /* Coalesce partitions live across abnormal edges. */ - coalesce_abnormal_edges (map, graph, rv); - - if (dump_file && (dump_flags & TDF_DETAILS)) - dump_var_map (dump_file, map); - - /* Coalesce partitions. */ - coalesce_tpa_members (rv, graph, map, cl, - ((dump_flags & TDF_DETAILS) ? dump_file - : NULL)); - - if (flags & SSANORM_COALESCE_PARTITIONS) - coalesce_tpa_members (rv, graph, map, NULL, - ((dump_flags & TDF_DETAILS) ? dump_file - : NULL)); - if (cl) - delete_coalesce_list (cl); - root_var_delete (rv); - conflict_graph_delete (graph); - - return liveinfo; -} - - /* Take the ssa-name var_map MAP, and assign real variables to each partition. */ static void assign_vars (var_map map) { - int x, i, num, rep; - tree t, var; + int x, num; + tree var, root; var_ann_t ann; - root_var_p rv; - - rv = root_var_init (map); - if (!rv) - return; - - /* Coalescing may already have forced some partitions to their root - variable. Find these and tag them. */ num = num_var_partitions (map); for (x = 0; x < num; x++) @@ -949,63 +511,35 @@ assign_vars (var_map map) var = partition_to_var (map, x); if (TREE_CODE (var) != SSA_NAME) { - /* Coalescing will already have verified that more than one - partition doesn't have the same root variable. Simply marked - the variable as assigned. */ ann = var_ann (var); - ann->out_of_ssa_tag = 1; + /* It must already be coalesced. */ + gcc_assert (ann->out_of_ssa_tag == 1); if (dump_file && (dump_flags & TDF_DETAILS)) { - fprintf (dump_file, "partition %d has variable ", x); + fprintf (dump_file, "partition %d already has variable ", x); print_generic_expr (dump_file, var, TDF_SLIM); fprintf (dump_file, " assigned to it.\n"); } - } - } - - num = root_var_num (rv); - for (x = 0; x < num; x++) - { - var = root_var (rv, x); - ann = var_ann (var); - for (i = root_var_first_partition (rv, x); - i != ROOT_VAR_NONE; - i = root_var_next_partition (rv, i)) - { - t = partition_to_var (map, i); - - if (t == var || TREE_CODE (t) != SSA_NAME) - continue; - - rep = var_to_partition (map, t); - - if (!ann->out_of_ssa_tag) + else + { + root = SSA_NAME_VAR (var); + ann = var_ann (root); + /* If ROOT is already associated, create a new one. */ + if (ann->out_of_ssa_tag) { - if (dump_file && (dump_flags & TDF_DETAILS)) - print_exprs (dump_file, "", t, " --> ", var, "\n"); - change_partition_var (map, var, rep); - continue; + root = create_temp (root); + ann = var_ann (root); } - - if (dump_file && (dump_flags & TDF_DETAILS)) - print_exprs (dump_file, "", t, " not coalesced with ", var, - ""); - - var = create_temp (t); - change_partition_var (map, var, rep); - ann = var_ann (var); - + /* ROOT has not been coalesced yet, so use it. */ if (dump_file && (dump_flags & TDF_DETAILS)) { - fprintf (dump_file, " --> New temp: '"); - print_generic_expr (dump_file, var, TDF_SLIM); - fprintf (dump_file, "'\n"); + fprintf (dump_file, "Partition %d is assigned to var ", x); + print_generic_stmt (dump_file, root, TDF_SLIM); } + change_partition_var (map, root, x); } } - - root_var_delete (rv); } @@ -1028,6 +562,7 @@ replace_use_variable (var_map map, use_operand_p p, tree *expr) { tree new_expr = GIMPLE_STMT_OPERAND (expr[version], 1); SET_USE (p, new_expr); + /* Clear the stmt's RHS, or GC might bite us. */ GIMPLE_STMT_OPERAND (expr[version], 1) = NULL_TREE; return true; @@ -1056,19 +591,9 @@ replace_def_variable (var_map map, def_operand_p def_p, tree *expr) tree new_var; tree var = DEF_FROM_PTR (def_p); - /* Check if we are replacing this variable with an expression. */ - if (expr) - { - int version = SSA_NAME_VERSION (var); - if (expr[version]) - { - tree new_expr = TREE_OPERAND (expr[version], 1); - SET_DEF (def_p, new_expr); - /* Clear the stmt's RHS, or GC might bite us. */ - TREE_OPERAND (expr[version], 1) = NULL_TREE; - return true; - } - } + /* Do nothing if we are replacing this variable with an expression. */ + if (expr && expr[SSA_NAME_VERSION (var)]) + return true; new_var = var_to_partition_to_var (map, var); if (new_var) @@ -1144,15 +669,12 @@ rewrite_trees (var_map map, tree *values) FOR_EACH_BB (bb) { tree phi; - for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) { tree T0 = var_to_partition_to_var (map, PHI_RESULT (phi)); - if (T0 == NULL_TREE) { int i; - for (i = 0; i < PHI_NUM_ARGS (phi); i++) { tree arg = PHI_ARG_DEF (phi, i); @@ -1261,8 +783,10 @@ static edge leader_match = NULL; /* Pass this function to make_forwarder_block so that all the edges with - matching PENDING_STMT lists to 'curr_stmt_list' get redirected. */ -static bool + matching PENDING_STMT lists to 'curr_stmt_list' get redirected. E is the + edge to test for a match. */ + +static inline bool same_stmt_list_p (edge e) { return (e->aux == (PTR) leader_match) ? true : false; @@ -1270,6 +794,7 @@ same_stmt_list_p (edge e) /* Return TRUE if S1 and S2 are equivalent copies. */ + static inline bool identical_copies_p (tree s1, tree s2) { @@ -1293,7 +818,7 @@ identical_copies_p (tree s1, tree s2) } -/* Compare the PENDING_STMT list for two edges, and return true if the lists +/* Compare the PENDING_STMT list for edges E1 and E2. Return true if the lists contain the same sequence of copies. */ static inline bool @@ -1380,6 +905,7 @@ analyze_edges_for_bb (basic_block bb) bsi_commit_one_edge_insert (e, NULL); return; } + /* Find out how many edges there are with interesting pending stmts on them. Commit the stmts on edges we are not interested in. */ FOR_EACH_EDGE (e, ei, bb->preds) @@ -1470,11 +996,9 @@ analyze_edges_for_bb (basic_block bb) return; } - if (dump_file) fprintf (dump_file, "\nOpportunities in BB %d for stmt/block reduction:\n", bb->index); - /* For each common list, create a forwarding block and issue the stmt's in that block. */ @@ -1601,28 +1125,23 @@ perform_edge_inserts (void) } -/* Remove the variables specified in MAP from SSA form. FLAGS indicate what - options should be used. */ +/* Remove the ssa-names in the current function and translate them into normal + compiler variables. PERFORM_TER is true if Temporary Expression Replacement + should also be used. */ static void -remove_ssa_form (var_map map, int flags) +remove_ssa_form (bool perform_ter) { - tree_live_info_p liveinfo; basic_block bb; tree phi, next; tree *values = NULL; + var_map map; - /* If we are not combining temps, don't calculate live ranges for variables - with only one SSA version. */ - compact_var_map (map, VARMAP_NO_SINGLE_DEFS); - - if (dump_file && (dump_flags & TDF_DETAILS)) - dump_var_map (dump_file, map); - - liveinfo = coalesce_ssa_name (map, flags); + map = coalesce_ssa_name (); - /* Make sure even single occurrence variables are in the list now. */ - compact_var_map (map, VARMAP_NORMAL); + /* Return to viewing the variable list as just all reference variables after + coalescing has been performed. */ + partition_view_normal (map, false); if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -1630,7 +1149,7 @@ remove_ssa_form (var_map map, int flags) dump_var_map (dump_file, map); } - if (flags & SSANORM_PERFORM_TER) + if (perform_ter) { values = find_replaceable_exprs (map); if (values && dump_file && (dump_flags & TDF_DETAILS)) @@ -1642,13 +1161,10 @@ remove_ssa_form (var_map map, int flags) if (dump_file && (dump_flags & TDF_DETAILS)) { - fprintf (dump_file, "After Root variable replacement:\n"); + fprintf (dump_file, "After Base variable replacement:\n"); dump_var_map (dump_file, map); } - if (liveinfo) - delete_tree_live_info (liveinfo); - rewrite_trees (map, values); if (values) @@ -1669,8 +1185,11 @@ remove_ssa_form (var_map map, int flags) /* If any copies were inserted on edges, analyze and insert them now. */ perform_edge_inserts (); + + delete_var_map (map); } + /* Search every PHI node for arguments associated with backedges which we can trivially determine will need a copy (the argument is either not an SSA_NAME or the argument has a different underlying variable @@ -1704,11 +1223,10 @@ insert_backedge_copies (void) tree arg = PHI_ARG_DEF (phi, i); edge e = PHI_ARG_EDGE (phi, i); - /* If the argument is not an SSA_NAME, then we will - need a constant initialization. If the argument is - an SSA_NAME with a different underlying variable and - we are not combining temporaries, then we will - need a copy statement. */ + /* If the argument is not an SSA_NAME, then we will need a + constant initialization. If the argument is an SSA_NAME with + a different underlying variable then a copy statement will be + needed. */ if ((e->flags & EDGE_DFS_BACK) && (TREE_CODE (arg) != SSA_NAME || SSA_NAME_VAR (arg) != result_var)) @@ -1723,7 +1241,6 @@ insert_backedge_copies (void) /* In theory the only way we ought to get back to the start of a loop should be with a COND_EXPR or GOTO_EXPR. However, better safe than sorry. - If the block ends with a control statement or something that might throw, then we have to insert this assignment before the last @@ -1738,8 +1255,8 @@ insert_backedge_copies (void) continue; } - /* Create a new instance of the underlying - variable of the PHI result. */ + /* Create a new instance of the underlying variable of the + PHI result. */ stmt = build2 (GIMPLE_MODIFY_STMT, TREE_TYPE (result_var), NULL_TREE, PHI_ARG_DEF (phi, i)); name = make_ssa_name (result_var, stmt); @@ -1758,16 +1275,13 @@ insert_backedge_copies (void) } } -/* Take the current function out of SSA form, as described in +/* Take the current function out of SSA form, translating PHIs as described in R. Morgan, ``Building an Optimizing Compiler'', Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */ static unsigned int rewrite_out_of_ssa (void) { - var_map map; - int ssa_flags = 0; - /* If elimination of a PHI requires inserting a copy on a backedge, then we will have to split the backedge which has numerous undesirable performance effects. @@ -1776,27 +1290,16 @@ rewrite_out_of_ssa (void) copies into the loop itself. */ insert_backedge_copies (); - if (!flag_tree_live_range_split) - ssa_flags |= SSANORM_COALESCE_PARTITIONS; - eliminate_virtual_phis (); if (dump_file && (dump_flags & TDF_DETAILS)) dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS); - map = create_ssa_var_map (); - - if (flag_tree_ter && !flag_mudflap) - ssa_flags |= SSANORM_PERFORM_TER; - - remove_ssa_form (map, ssa_flags); + remove_ssa_form (flag_tree_ter && !flag_mudflap); if (dump_file && (dump_flags & TDF_DETAILS)) dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS); - /* Flush out flow graph and SSA data. */ - delete_var_map (map); - cfun->gimple_df->in_ssa_p = false; return 0; } diff --git a/gcc/tree-ssa-coalesce.c b/gcc/tree-ssa-coalesce.c new file mode 100644 index 00000000000..00793618d67 --- /dev/null +++ b/gcc/tree-ssa-coalesce.c @@ -0,0 +1,1355 @@ +/* Coalesce SSA_NAMES together for the out-of-ssa pass. + Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc. + Contributed by Andrew MacLeod <amacleod@redhat.com> + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING. If not, write to +the Free Software Foundation, 51 Franklin Street, Fifth Floor, +Boston, MA 02110-1301, USA. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include "tree.h" +#include "flags.h" +#include "diagnostic.h" +#include "bitmap.h" +#include "tree-flow.h" +#include "hashtab.h" +#include "tree-dump.h" +#include "tree-ssa-live.h" +#include "toplev.h" + + +/* This set of routines implements a coalesce_list. This is an object which + is used to track pairs of ssa_names which are desirable to coalesce + together to avoid copies. Costs are associated with each pair, and when + all desired information has been collected, the object can be used to + order the pairs for processing. */ + +/* This structure defines a pair entry. */ + +typedef struct coalesce_pair +{ + int first_element; + int second_element; + int cost; +} * coalesce_pair_p; + +typedef struct cost_one_pair_d +{ + int first_element; + int second_element; + struct cost_one_pair_d *next; +} * cost_one_pair_p; + +/* This structure maintains the list of coalesce pairs. */ + +typedef struct coalesce_list_d +{ + htab_t list; /* Hash table. */ + coalesce_pair_p *sorted; /* List when sorted. */ + int num_sorted; /* Number in the sorted list. */ + cost_one_pair_p cost_one_list;/* Single use coalesces with cost 1. */ +} *coalesce_list_p; + +#define NO_BEST_COALESCE -1 +#define MUST_COALESCE_COST INT_MAX + + +/* Return cost of execution of copy instruction with FREQUENCY + possibly on CRITICAL edge and in HOT basic block. */ + +static inline int +coalesce_cost (int frequency, bool hot, bool critical) +{ + /* Base costs on BB frequencies bounded by 1. */ + int cost = frequency; + + if (!cost) + cost = 1; + + if (optimize_size) + cost = 1; + else + /* It is more important to coalesce in HOT blocks. */ + if (hot) + cost *= 2; + + /* Inserting copy on critical edge costs more than inserting it elsewhere. */ + if (critical) + cost *= 2; + return cost; +} + + +/* Return the cost of executing a copy instruction in basic block BB. */ + +static inline int +coalesce_cost_bb (basic_block bb) +{ + return coalesce_cost (bb->frequency, maybe_hot_bb_p (bb), false); +} + + +/* Return the cost of executing a copy instruction on edge E. */ + +static inline int +coalesce_cost_edge (edge e) +{ + if (e->flags & EDGE_ABNORMAL) + return MUST_COALESCE_COST; + + return coalesce_cost (EDGE_FREQUENCY (e), + maybe_hot_bb_p (e->src), + EDGE_CRITICAL_P (e)); +} + + +/* Retrieve a pair to coalesce from the cost_one_list in CL. Returns the + 2 elements via P1 and P2. 1 is returned by the function if there is a pair, + NO_BEST_COALESCE is returned if there aren't any. */ + +static inline int +pop_cost_one_pair (coalesce_list_p cl, int *p1, int *p2) +{ + cost_one_pair_p ptr; + + ptr = cl->cost_one_list; + if (!ptr) + return NO_BEST_COALESCE; + + *p1 = ptr->first_element; + *p2 = ptr->second_element; + cl->cost_one_list = ptr->next; + + free (ptr); + + return 1; +} + +/* Retrieve the most expensive remaining pair to coalesce from CL. Returns the + 2 elements via P1 and P2. Their calculated cost is returned by the function. + NO_BEST_COALESCE is returned if the coalesce list is empty. */ + +static inline int +pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2) +{ + coalesce_pair_p node; + int ret; + + if (cl->sorted == NULL) + return pop_cost_one_pair (cl, p1, p2); + + if (cl->num_sorted == 0) + return pop_cost_one_pair (cl, p1, p2); + + node = cl->sorted[--(cl->num_sorted)]; + *p1 = node->first_element; + *p2 = node->second_element; + ret = node->cost; + free (node); + + return ret; +} + + +#define COALESCE_HASH_FN(R1, R2) ((R2) * ((R2) - 1) / 2 + (R1)) + +/* Hash function for coalesce list. Calculate hash for PAIR. */ + +static unsigned int +coalesce_pair_map_hash (const void *pair) +{ + hashval_t a = (hashval_t)(((coalesce_pair_p)pair)->first_element); + hashval_t b = (hashval_t)(((coalesce_pair_p)pair)->second_element); + + return COALESCE_HASH_FN (a,b); +} + + +/* Equality function for coalesce list hash table. Compare PAIR1 and PAIR2, + returning TRUE if the two pairs are equivilent. */ + +static int +coalesce_pair_map_eq (const void *pair1, const void *pair2) +{ + coalesce_pair_p p1 = (coalesce_pair_p) pair1; + coalesce_pair_p p2 = (coalesce_pair_p) pair2; + + return (p1->first_element == p2->first_element + && p1->second_element == p2->second_element); +} + + +/* Create a new empty coalesce list object and return it. */ + +static inline coalesce_list_p +create_coalesce_list (void) +{ + coalesce_list_p list; + unsigned size = num_ssa_names * 3; + + if (size < 40) + size = 40; + + list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d)); + list->list = htab_create (size, coalesce_pair_map_hash, + coalesce_pair_map_eq, NULL); + list->sorted = NULL; + list->num_sorted = 0; + list->cost_one_list = NULL; + return list; +} + + +/* Delete coalesce list CL. */ + +static inline void +delete_coalesce_list (coalesce_list_p cl) +{ + gcc_assert (cl->cost_one_list == NULL); + htab_delete (cl->list); + if (cl->sorted) + free (cl->sorted); + gcc_assert (cl->num_sorted == 0); + free (cl); +} + + +/* Find a matching coalesce pair object in CL for the pair P1 and P2. If + one isn't found, return NULL if CREATE is false, otherwise create a new + coalesce pair object and return it. */ + +static coalesce_pair_p +find_coalesce_pair (coalesce_list_p cl, int p1, int p2, bool create) +{ + struct coalesce_pair p, *pair; + void **slot; + unsigned int hash; + + /* Normalize so that p1 is the smaller value. */ + if (p2 < p1) + { + p.first_element = p2; + p.second_element = p1; + } + else + { + p.first_element = p1; + p.second_element = p2; + } + + + hash = coalesce_pair_map_hash (&p); + pair = (struct coalesce_pair *) htab_find_with_hash (cl->list, &p, hash); + + if (create && !pair) + { + gcc_assert (cl->sorted == NULL); + pair = xmalloc (sizeof (struct coalesce_pair)); + pair->first_element = p.first_element; + pair->second_element = p.second_element; + pair->cost = 0; + slot = htab_find_slot_with_hash (cl->list, pair, hash, INSERT); + *(struct coalesce_pair **)slot = pair; + } + + return pair; +} + +static inline void +add_cost_one_coalesce (coalesce_list_p cl, int p1, int p2) +{ + cost_one_pair_p pair; + + pair = xmalloc (sizeof (struct cost_one_pair_d)); + pair->first_element = p1; + pair->second_element = p2; + pair->next = cl->cost_one_list; + cl->cost_one_list = pair; +} + + +/* Add a coalesce between P1 and P2 in list CL with a cost of VALUE. */ + +static inline void +add_coalesce (coalesce_list_p cl, int p1, int p2, + int value) +{ + coalesce_pair_p node; + + gcc_assert (cl->sorted == NULL); + if (p1 == p2) + return; + + node = find_coalesce_pair (cl, p1, p2, true); + + /* Once the value is MUST_COALESCE_COST, leave it that way. */ + if (node->cost != MUST_COALESCE_COST) + { + if (value == MUST_COALESCE_COST) + node->cost = value; + else + node->cost += value; + } +} + + +/* Comparison function to allow qsort to sort P1 and P2 in Ascendiong order. */ + +static int +compare_pairs (const void *p1, const void *p2) +{ + return (*(coalesce_pair_p *)p1)->cost - (*(coalesce_pair_p *)p2)->cost; +} + + +/* Return the number of unique coalesce pairs in CL. */ + +static inline int +num_coalesce_pairs (coalesce_list_p cl) +{ + return htab_elements (cl->list); +} + + +/* Iterator over hash table pairs. */ +typedef struct +{ + htab_iterator hti; +} coalesce_pair_iterator; + + +/* Return first partition pair from list CL, initializing iterator ITER. */ + +static inline coalesce_pair_p +first_coalesce_pair (coalesce_list_p cl, coalesce_pair_iterator *iter) +{ + coalesce_pair_p pair; + + pair = (coalesce_pair_p) first_htab_element (&(iter->hti), cl->list); + return pair; +} + + +/* Return TRUE if there are no more partitions in for ITER to process. */ + +static inline bool +end_coalesce_pair_p (coalesce_pair_iterator *iter) +{ + return end_htab_p (&(iter->hti)); +} + + +/* Return the next parttition pair to be visited by ITER. */ + +static inline coalesce_pair_p +next_coalesce_pair (coalesce_pair_iterator *iter) +{ + coalesce_pair_p pair; + + pair = (coalesce_pair_p) next_htab_element (&(iter->hti)); + return pair; +} + + +/* Iterate over CL using ITER, returning values in PAIR. */ + +#define FOR_EACH_PARTITION_PAIR(PAIR, ITER, CL) \ + for ((PAIR) = first_coalesce_pair ((CL), &(ITER)); \ + !end_coalesce_pair_p (&(ITER)); \ + (PAIR) = next_coalesce_pair (&(ITER))) + + +/* Prepare CL for removal of preferred pairs. When finished they are sorted + in order from most important coalesce to least important. */ + +static void +sort_coalesce_list (coalesce_list_p cl) +{ + unsigned x, num; + coalesce_pair_p p; + coalesce_pair_iterator ppi; + + gcc_assert (cl->sorted == NULL); + + num = num_coalesce_pairs (cl); + cl->num_sorted = num; + if (num == 0) + return; + + /* Allocate a vector for the pair pointers. */ + cl->sorted = XNEWVEC (coalesce_pair_p, num); + + /* Populate the vector with pointers to the pairs. */ + x = 0; + FOR_EACH_PARTITION_PAIR (p, ppi, cl) + cl->sorted[x++] = p; + gcc_assert (x == num); + + /* Already sorted. */ + if (num == 1) + return; + + /* If there are only 2, just pick swap them if the order isn't correct. */ + if (num == 2) + { + if (cl->sorted[0]->cost > cl->sorted[1]->cost) + { + p = cl->sorted[0]; + cl->sorted[0] = cl->sorted[1]; + cl->sorted[1] = p; + } + return; + } + + /* Only call qsort if there are more than 2 items. */ + if (num > 2) + qsort (cl->sorted, num, sizeof (coalesce_pair_p), compare_pairs); +} + + +/* Send debug info for coalesce list CL to file F. */ + +static void +dump_coalesce_list (FILE *f, coalesce_list_p cl) +{ + coalesce_pair_p node; + coalesce_pair_iterator ppi; + int x; + tree var; + + if (cl->sorted == NULL) + { + fprintf (f, "Coalesce List:\n"); + FOR_EACH_PARTITION_PAIR (node, ppi, cl) + { + tree var1 = ssa_name (node->first_element); + tree var2 = ssa_name (node->second_element); + print_generic_expr (f, var1, TDF_SLIM); + fprintf (f, " <-> "); + print_generic_expr (f, var2, TDF_SLIM); + fprintf (f, " (%1d), ", node->cost); + fprintf (f, "\n"); + } + } + else + { + fprintf (f, "Sorted Coalesce list:\n"); + for (x = cl->num_sorted - 1 ; x >=0; x--) + { + node = cl->sorted[x]; + fprintf (f, "(%d) ", node->cost); + var = ssa_name (node->first_element); + print_generic_expr (f, var, TDF_SLIM); + fprintf (f, " <-> "); + var = ssa_name (node->second_element); + print_generic_expr (f, var, TDF_SLIM); + fprintf (f, "\n"); + } + } +} + + +/* This represents a conflict graph. Implemented as an array of bitmaps. + A full matrix isused for conflicts rather than just upper triangular form. + this make sit much simpler and faster to perform conflict merges. */ + +typedef struct ssa_conflicts_d +{ + unsigned size; + bitmap *conflicts; +} * ssa_conflicts_p; + + +/* Return a empty new conflict graph for SIZE elements. */ + +static inline ssa_conflicts_p +ssa_conflicts_new (unsigned size) +{ + ssa_conflicts_p ptr; + + ptr = XNEW (struct ssa_conflicts_d); + ptr->conflicts = XCNEWVEC (bitmap, size); + ptr->size = size; + return ptr; +} + + +/* Free storage for conflict graph PTR. */ + +static inline void +ssa_conflicts_delete (ssa_conflicts_p ptr) +{ + unsigned x; + for (x = 0; x < ptr->size; x++) + if (ptr->conflicts[x]) + BITMAP_FREE (ptr->conflicts[x]); + + free (ptr->conflicts); + free (ptr); +} + + +/* Test if elements X and Y conflict in graph PTR. */ + +static inline bool +ssa_conflicts_test_p (ssa_conflicts_p ptr, unsigned x, unsigned y) +{ + bitmap b; + +#ifdef ENABLE_CHECKING + gcc_assert (x < ptr->size); + gcc_assert (y < ptr->size); + gcc_assert (x != y); +#endif + + b = ptr->conflicts[x]; + if (b) + /* Avoid the lookup if Y has no conflicts. */ + return ptr->conflicts[y] ? bitmap_bit_p (b, y) : false; + else + return false; +} + + +/* Add a conflict with Y to the bitmap for X in graph PTR. */ + +static inline void +ssa_conflicts_add_one (ssa_conflicts_p ptr, unsigned x, unsigned y) +{ + /* If there are no conflicts yet, allocate the bitmap and set bit. */ + if (!ptr->conflicts[x]) + ptr->conflicts[x] = BITMAP_ALLOC (NULL); + bitmap_set_bit (ptr->conflicts[x], y); +} + + +/* Add conflicts between X and Y in graph PTR. */ + +static inline void +ssa_conflicts_add (ssa_conflicts_p ptr, unsigned x, unsigned y) +{ +#ifdef ENABLE_CHECKING + gcc_assert (x < ptr->size); + gcc_assert (y < ptr->size); + gcc_assert (x != y); +#endif + ssa_conflicts_add_one (ptr, x, y); + ssa_conflicts_add_one (ptr, y, x); +} + + +/* Merge all Y's conflict into X in graph PTR. */ + +static inline void +ssa_conflicts_merge (ssa_conflicts_p ptr, unsigned x, unsigned y) +{ + unsigned z; + bitmap_iterator bi; + + gcc_assert (x != y); + if (!(ptr->conflicts[y])) + return; + + /* Add a conflict between X and every one Y has. If the bitmap doesn't + exist, then it has already been coalesced, and we dont need to add a + conflict. */ + EXECUTE_IF_SET_IN_BITMAP (ptr->conflicts[y], 0, z, bi) + if (ptr->conflicts[z]) + bitmap_set_bit (ptr->conflicts[z], x); + + if (ptr->conflicts[x]) + { + /* If X has conflicts, add Y's to X. */ + bitmap_ior_into (ptr->conflicts[x], ptr->conflicts[y]); + BITMAP_FREE (ptr->conflicts[y]); + } + else + { + /* If X has no conflicts, simply use Y's. */ + ptr->conflicts[x] = ptr->conflicts[y]; + ptr->conflicts[y] = NULL; + } +} + + +/* This structure is used to efficiently record the current status of live + SSA_NAMES when building a conflict graph. + LIVE_BASE_VAR has a bit set for each base variable which has at least one + ssa version live. + LIVE_BASE_PARTITIONS is an array of bitmaps using the basevar table as an + index, and is used to track what partitions of each base variable are + live. This makes it easy to add conflicts between just live partitions + with the same base variable. + The values in LIVE_BASE_PARTITIONS are only valid if the base variable is + marked as being live. This delays clearing of these bitmaps until + they are actually needed again. */ + +typedef struct live_track_d +{ + bitmap live_base_var; /* Indicates if a basevar is live. */ + bitmap *live_base_partitions; /* Live partitions for each basevar. */ + var_map map; /* Var_map being used for partition mapping. */ +} * live_track_p; + + +/* This routine will create a new live track structure based on the partitions + in MAP. */ + +static live_track_p +new_live_track (var_map map) +{ + live_track_p ptr; + int lim, x; + + /* Make sure there is a partition view in place. */ + gcc_assert (map->partition_to_base_index != NULL); + + ptr = (live_track_p) xmalloc (sizeof (struct live_track_d)); + ptr->map = map; + lim = num_basevars (map); + ptr->live_base_partitions = (bitmap *) xmalloc(sizeof (bitmap *) * lim); + ptr->live_base_var = BITMAP_ALLOC (NULL); + for (x = 0; x < lim; x++) + ptr->live_base_partitions[x] = BITMAP_ALLOC (NULL); + return ptr; +} + + +/* This routine will free the memory associated with PTR. */ + +static void +delete_live_track (live_track_p ptr) +{ + int x, lim; + + lim = num_basevars (ptr->map); + for (x = 0; x < lim; x++) + BITMAP_FREE (ptr->live_base_partitions[x]); + BITMAP_FREE (ptr->live_base_var); + free (ptr->live_base_partitions); + free (ptr); +} + + +/* This function will remove PARTITION from the live list in PTR. */ + +static inline void +live_track_remove_partition (live_track_p ptr, int partition) +{ + int root; + + root = basevar_index (ptr->map, partition); + bitmap_clear_bit (ptr->live_base_partitions[root], partition); + /* If the element list is empty, make the base variable not live either. */ + if (bitmap_empty_p (ptr->live_base_partitions[root])) + bitmap_clear_bit (ptr->live_base_var, root); +} + + +/* This function will adds PARTITION to the live list in PTR. */ + +static inline void +live_track_add_partition (live_track_p ptr, int partition) +{ + int root; + + root = basevar_index (ptr->map, partition); + /* If this base var wasn't live before, it is now. Clear the element list + since it was delayed until needed. */ + if (!bitmap_bit_p (ptr->live_base_var, root)) + { + bitmap_set_bit (ptr->live_base_var, root); + bitmap_clear (ptr->live_base_partitions[root]); + } + bitmap_set_bit (ptr->live_base_partitions[root], partition); + +} + + +/* Clear the live bit for VAR in PTR. */ + +static inline void +live_track_clear_var (live_track_p ptr, tree var) +{ + int p; + + p = var_to_partition (ptr->map, var); + if (p != NO_PARTITION) + live_track_remove_partition (ptr, p); +} + + +/* Return TRUE if VAR is live in PTR. */ + +static inline bool +live_track_live_p (live_track_p ptr, tree var) +{ + int p, root; + + p = var_to_partition (ptr->map, var); + if (p != NO_PARTITION) + { + root = basevar_index (ptr->map, p); + if (bitmap_bit_p (ptr->live_base_var, root)) + return bitmap_bit_p (ptr->live_base_partitions[root], p); + } + return false; +} + + +/* This routine will add USE to PTR. USE will be marked as live in both the + ssa live map and the live bitmap for the root of USE. */ + +static inline void +live_track_process_use (live_track_p ptr, tree use) +{ + int p; + + p = var_to_partition (ptr->map, use); + if (p == NO_PARTITION) + return; + + /* Mark as live in the appropriate live list. */ + live_track_add_partition (ptr, p); +} + + +/* This routine will process a DEF in PTR. DEF will be removed from the live + lists, and if there are any other live partitions with the same base + variable, conflicts will be added to GRAPH. */ + +static inline void +live_track_process_def (live_track_p ptr, tree def, ssa_conflicts_p graph) +{ + int p, root; + bitmap b; + unsigned x; + bitmap_iterator bi; + + p = var_to_partition (ptr->map, def); + if (p == NO_PARTITION) + return; + + /* Clear the liveness bit. */ + live_track_remove_partition (ptr, p); + + /* If the bitmap isn't empty now, conflicts need to be added. */ + root = basevar_index (ptr->map, p); + if (bitmap_bit_p (ptr->live_base_var, root)) + { + b = ptr->live_base_partitions[root]; + EXECUTE_IF_SET_IN_BITMAP (b, 0, x, bi) + ssa_conflicts_add (graph, p, x); + } +} + + +/* Initialize PTR with the partitions set in INIT. */ + +static inline void +live_track_init (live_track_p ptr, bitmap init) +{ + unsigned p; + bitmap_iterator bi; + + /* Mark all live on exit partitions. */ + EXECUTE_IF_SET_IN_BITMAP (init, 0, p, bi) + live_track_add_partition (ptr, p); +} + + +/* This routine will clear all live partitions in PTR. */ + +static inline void +live_track_clear_base_vars (live_track_p ptr) +{ + /* Simply clear the live base list. Anything marked as live in the element + lists will be cleared later if/when the base variable ever comes alive + again. */ + bitmap_clear (ptr->live_base_var); +} + + +/* Build a conflict graph based on LIVEINFO. Any partitions which are in the + partition view of the var_map liveinfo is based on get entires in the + conflict graph. Only conflicts between ssa_name partitions with the same + base variableare added. */ + +static ssa_conflicts_p +build_ssa_conflict_graph (tree_live_info_p liveinfo) +{ + ssa_conflicts_p graph; + var_map map; + basic_block bb; + ssa_op_iter iter; + live_track_p live; + + map = live_var_map (liveinfo); + graph = ssa_conflicts_new (num_var_partitions (map)); + + live = new_live_track (map); + + FOR_EACH_BB (bb) + { + block_stmt_iterator bsi; + tree phi; + + /* Start with live on exit temporaries. */ + live_track_init (live, live_on_exit (liveinfo, bb)); + + for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi)) + { + tree var; + tree stmt = bsi_stmt (bsi); + + /* A copy between 2 partitions does not introduce an interference + by itself. If they did, you would never be able to coalesce + two things which are copied. If the two variables really do + conflict, they will conflict elsewhere in the program. + + This is handled by simply removing the SRC of the copy from the + live list, and processing the stmt normally. */ + if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT) + { + tree lhs = GIMPLE_STMT_OPERAND (stmt, 0); + tree rhs = GIMPLE_STMT_OPERAND (stmt, 1); + if (TREE_CODE (lhs) == SSA_NAME && TREE_CODE (rhs) == SSA_NAME) + live_track_clear_var (live, rhs); + } + + FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF) + live_track_process_def (live, var, graph); + + FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE) + live_track_process_use (live, var); + } + + /* If result of a PHI is unused, looping over the statements will not + record any conflicts since the def was never live. Since the PHI node + is going to be translated out of SSA form, it will insert a copy. + There must be a conflict recorded between the result of the PHI and + any variables that are live. Otherwise the out-of-ssa translation + may create incorrect code. */ + for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) + { + tree result = PHI_RESULT (phi); + if (live_track_live_p (live, result)) + live_track_process_def (live, result, graph); + } + + live_track_clear_base_vars (live); + } + + delete_live_track (live); + return graph; +} + + +/* Shortcut routine to print messages to file F of the form: + "STR1 EXPR1 STR2 EXPR2 STR3." */ + +static inline void +print_exprs (FILE *f, const char *str1, tree expr1, const char *str2, + tree expr2, const char *str3) +{ + fprintf (f, "%s", str1); + print_generic_expr (f, expr1, TDF_SLIM); + fprintf (f, "%s", str2); + print_generic_expr (f, expr2, TDF_SLIM); + fprintf (f, "%s", str3); +} + + +/* Called if a coalesce across and abnormal edge cannot be performed. PHI is + the phi node at fault, I is the argument index at fault. A message is + printed and compilation is then terminated. */ + +static inline void +abnormal_corrupt (tree phi, int i) +{ + edge e = PHI_ARG_EDGE (phi, i); + tree res = PHI_RESULT (phi); + tree arg = PHI_ARG_DEF (phi, i); + + fprintf (stderr, " Corrupt SSA across abnormal edge BB%d->BB%d\n", + e->src->index, e->dest->index); + fprintf (stderr, "Argument %d (", i); + print_generic_expr (stderr, arg, TDF_SLIM); + if (TREE_CODE (arg) != SSA_NAME) + fprintf (stderr, ") is not an SSA_NAME.\n"); + else + { + gcc_assert (SSA_NAME_VAR (res) != SSA_NAME_VAR (arg)); + fprintf (stderr, ") does not have the same base variable as the result "); + print_generic_stmt (stderr, res, TDF_SLIM); + } + + internal_error ("SSA corruption"); +} + + +/* Print a failure to coalesce a MUST_COALESCE pair X and Y. */ + +static inline void +fail_abnormal_edge_coalesce (int x, int y) +{ + fprintf (stderr, "\nUnable to coalesce ssa_names %d and %d ",x, y); + fprintf (stderr, " which are marked as MUST COALESCE.\n"); + print_generic_expr (stderr, ssa_name (x), TDF_SLIM); + fprintf (stderr, " and "); + print_generic_stmt (stderr, ssa_name (y), TDF_SLIM); + + internal_error ("SSA corruption"); +} + + +/* This function creates a var_map for the current function as well as creating + a coalesce list for use later in the out of ssa process. */ + +static var_map +create_outofssa_var_map (coalesce_list_p cl, bitmap used_in_copy) +{ + block_stmt_iterator bsi; + basic_block bb; + tree var; + tree stmt; + tree first; + var_map map; + ssa_op_iter iter; + int v1, v2, cost; + unsigned i; + +#ifdef ENABLE_CHECKING + bitmap used_in_real_ops; + bitmap used_in_virtual_ops; + + used_in_real_ops = BITMAP_ALLOC (NULL); + used_in_virtual_ops = BITMAP_ALLOC (NULL); +#endif + + map = init_var_map (num_ssa_names + 1); + + FOR_EACH_BB (bb) + { + tree phi, arg; + + for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) + { + int i; + int ver; + tree res; + bool saw_copy = false; + + res = PHI_RESULT (phi); + ver = SSA_NAME_VERSION (res); + register_ssa_partition (map, res); + + /* Register ssa_names and coalesces between the args and the result + of all PHI. */ + for (i = 0; i < PHI_NUM_ARGS (phi); i++) + { + edge e = PHI_ARG_EDGE (phi, i); + arg = PHI_ARG_DEF (phi, i); + if (TREE_CODE (arg) == SSA_NAME) + register_ssa_partition (map, arg); + if (TREE_CODE (arg) == SSA_NAME + && SSA_NAME_VAR (arg) == SSA_NAME_VAR (res)) + { + saw_copy = true; + bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (arg)); + if ((e->flags & EDGE_ABNORMAL) == 0) + { + int cost = coalesce_cost_edge (e); + if (cost == 1 && single_imm_use_p (arg)) + add_cost_one_coalesce (cl, ver, SSA_NAME_VERSION (arg)); + else + add_coalesce (cl, ver, SSA_NAME_VERSION (arg), cost); + } + } + else + if (e->flags & EDGE_ABNORMAL) + abnormal_corrupt (phi, i); + } + if (saw_copy) + bitmap_set_bit (used_in_copy, ver); + } + + for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) + { + stmt = bsi_stmt (bsi); + + /* Register USE and DEF operands in each statement. */ + FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, (SSA_OP_DEF|SSA_OP_USE)) + register_ssa_partition (map, var); + + /* Check for copy coalesces. */ + switch (TREE_CODE (stmt)) + { + case GIMPLE_MODIFY_STMT: + { + tree op1 = GIMPLE_STMT_OPERAND (stmt, 0); + tree op2 = GIMPLE_STMT_OPERAND (stmt, 1); + if (TREE_CODE (op1) == SSA_NAME + && TREE_CODE (op2) == SSA_NAME + && SSA_NAME_VAR (op1) == SSA_NAME_VAR (op2)) + { + v1 = SSA_NAME_VERSION (op1); + v2 = SSA_NAME_VERSION (op2); + cost = coalesce_cost_bb (bb); + add_coalesce (cl, v1, v2, cost); + bitmap_set_bit (used_in_copy, v1); + bitmap_set_bit (used_in_copy, v2); + } + } + break; + + case ASM_EXPR: + { + unsigned long noutputs, i; + tree *outputs, link; + noutputs = list_length (ASM_OUTPUTS (stmt)); + outputs = (tree *) alloca (noutputs * sizeof (tree)); + for (i = 0, link = ASM_OUTPUTS (stmt); link; + ++i, link = TREE_CHAIN (link)) + outputs[i] = TREE_VALUE (link); + + for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link)) + { + const char *constraint + = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link))); + tree input = TREE_VALUE (link); + char *end; + unsigned long match; + + if (TREE_CODE (input) != SSA_NAME && !DECL_P (input)) + continue; + + match = strtoul (constraint, &end, 10); + if (match >= noutputs || end == constraint) + continue; + + if (TREE_CODE (outputs[match]) != SSA_NAME) + continue; + + v1 = SSA_NAME_VERSION (outputs[match]); + v2 = SSA_NAME_VERSION (input); + + if (SSA_NAME_VAR (outputs[match]) == SSA_NAME_VAR (input)) + { + cost = coalesce_cost (REG_BR_PROB_BASE, + maybe_hot_bb_p (bb), + false); + add_coalesce (cl, v1, v2, cost); + bitmap_set_bit (used_in_copy, v1); + bitmap_set_bit (used_in_copy, v2); + } + } + break; + } + + default: + break; + } + +#ifdef ENABLE_CHECKING + /* Mark real uses and defs. */ + FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, (SSA_OP_DEF|SSA_OP_USE)) + bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (var))); + + /* Validate that virtual ops don't get used in funny ways. */ + FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, + SSA_OP_VIRTUAL_USES | SSA_OP_VMUSTDEF) + { + bitmap_set_bit (used_in_virtual_ops, + DECL_UID (SSA_NAME_VAR (var))); + } + +#endif /* ENABLE_CHECKING */ + } + } + + /* Now process result decls and live on entry variables for entry into + the coalesce list. */ + first = NULL_TREE; + for (i = 1; i < num_ssa_names; i++) + { + var = map->partition_to_var[i]; + if (var != NULL_TREE) + { + /* Add coalesces between all the result decls. */ + if (TREE_CODE (SSA_NAME_VAR (var)) == RESULT_DECL) + { + if (first == NULL_TREE) + first = var; + else + { + gcc_assert (SSA_NAME_VAR (var) == SSA_NAME_VAR (first)); + v1 = SSA_NAME_VERSION (first); + v2 = SSA_NAME_VERSION (var); + bitmap_set_bit (used_in_copy, v1); + bitmap_set_bit (used_in_copy, v2); + cost = coalesce_cost_bb (EXIT_BLOCK_PTR); + add_coalesce (cl, v1, v2, cost); + } + } + /* Mark any default_def variables as being in the coalesce list + since they will have to be coalesced with the base variable. If + not marked as present, they won't be in the coalesce view. */ + if (gimple_default_def (cfun, SSA_NAME_VAR (var)) == var) + bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var)); + } + } + +#if defined ENABLE_CHECKING + { + unsigned i; + bitmap both = BITMAP_ALLOC (NULL); + bitmap_and (both, used_in_real_ops, used_in_virtual_ops); + if (!bitmap_empty_p (both)) + { + bitmap_iterator bi; + + EXECUTE_IF_SET_IN_BITMAP (both, 0, i, bi) + fprintf (stderr, "Variable %s used in real and virtual operands\n", + get_name (referenced_var (i))); + internal_error ("SSA corruption"); + } + + BITMAP_FREE (used_in_real_ops); + BITMAP_FREE (used_in_virtual_ops); + BITMAP_FREE (both); + } +#endif + + return map; +} + + +/* Attempt to coalesce ssa verisons X and Y together using the partition + mapping in MAP and checking conflicts in GRAPH. Output any debug info to + DEBUG, if it is nun-NULL. */ + +static inline bool +attempt_coalesce (var_map map, ssa_conflicts_p graph, int x, int y, + FILE *debug) +{ + int z; + tree var1, var2; + int p1, p2; + + p1 = var_to_partition (map, ssa_name (x)); + p2 = var_to_partition (map, ssa_name (y)); + + if (debug) + { + fprintf (debug, "(%d)", x); + print_generic_expr (debug, partition_to_var (map, p1), TDF_SLIM); + fprintf (debug, " & (%d)", y); + print_generic_expr (debug, partition_to_var (map, p2), TDF_SLIM); + } + + if (p1 == p2) + { + if (debug) + fprintf (debug, ": Already Coalesced.\n"); + return true; + } + + if (debug) + fprintf (debug, " [map: %d, %d] ", p1, p2); + + + if (!ssa_conflicts_test_p (graph, p1, p2)) + { + var1 = partition_to_var (map, p1); + var2 = partition_to_var (map, p2); + z = var_union (map, var1, var2); + if (z == NO_PARTITION) + { + if (debug) + fprintf (debug, ": Unable to perform partition union.\n"); + return false; + } + + /* z is the new combined partition. Remove the other partition from + the list, and merge the conflicts. */ + if (z == p1) + ssa_conflicts_merge (graph, p1, p2); + else + ssa_conflicts_merge (graph, p2, p1); + + if (debug) + fprintf (debug, ": Success -> %d\n", z); + return true; + } + + if (debug) + fprintf (debug, ": Fail due to conflict\n"); + + return false; +} + + +/* Attempt to Coalesce partitions in MAP which occur in the list CL using + GRAPH. Debug output is sent to DEBUG if it is non-NULL. */ + +static void +coalesce_partitions (var_map map, ssa_conflicts_p graph, coalesce_list_p cl, + FILE *debug) +{ + int x = 0, y = 0; + tree var1, var2, phi; + int cost; + basic_block bb; + edge e; + edge_iterator ei; + + /* First, coalece all the copie across abnormal edges. These are not placed + in the coalesce list becase they do not need to be sorted, and simply + consume extra memory/compilation time in large programs. */ + + FOR_EACH_BB (bb) + { + FOR_EACH_EDGE (e, ei, bb->preds) + if (e->flags & EDGE_ABNORMAL) + { + for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) + { + tree res = PHI_RESULT (phi); + tree arg = PHI_ARG_DEF (phi, e->dest_idx); + int v1 = SSA_NAME_VERSION (res); + int v2 = SSA_NAME_VERSION (arg); + + if (SSA_NAME_VAR (arg) != SSA_NAME_VAR (res)) + abnormal_corrupt (phi, e->dest_idx); + + if (debug) + fprintf (debug, "Abnormal coalesce: "); + + if (!attempt_coalesce (map, graph, v1, v2, debug)) + fail_abnormal_edge_coalesce (v1, v2); + } + } + } + + /* Now process the items in the coalesce list. */ + + while ((cost = pop_best_coalesce (cl, &x, &y)) != NO_BEST_COALESCE) + { + var1 = ssa_name (x); + var2 = ssa_name (y); + + /* Assert the coalesces have the same base variable. */ + gcc_assert (SSA_NAME_VAR (var1) == SSA_NAME_VAR (var2)); + + if (debug) + fprintf (debug, "Coalesce list: "); + attempt_coalesce (map, graph, x, y, debug); + } +} + + +/* Reduce the number of copies by coalescing variables in the function. Return + a partition map with the resulting coalesces. */ + +extern var_map +coalesce_ssa_name (void) +{ + unsigned num, x; + tree_live_info_p liveinfo; + ssa_conflicts_p graph; + coalesce_list_p cl; + bitmap used_in_copies = BITMAP_ALLOC (NULL); + var_map map; + + cl = create_coalesce_list (); + map = create_outofssa_var_map (cl, used_in_copies); + + /* Don't calculate live ranges for variables not in the coalesce list. */ + partition_view_bitmap (map, used_in_copies, true); + BITMAP_FREE (used_in_copies); + + if (num_var_partitions (map) <= 1) + { + delete_coalesce_list (cl); + return map; + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + dump_var_map (dump_file, map); + + liveinfo = calculate_live_ranges (map); + + if (dump_file && (dump_flags & TDF_DETAILS)) + dump_live_info (dump_file, liveinfo, LIVEDUMP_ENTRY); + + /* Build a conflict graph. */ + graph = build_ssa_conflict_graph (liveinfo); + delete_tree_live_info (liveinfo); + + sort_coalesce_list (cl); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "\nAfter sorting:\n"); + dump_coalesce_list (dump_file, cl); + } + + /* First, coalesce all live on entry variables to their base variable. + This will ensure the first use is coming from the correct location. */ + + num = num_var_partitions (map); + for (x = 0 ; x < num; x++) + { + tree var = partition_to_var (map, x); + tree root; + + if (TREE_CODE (var) != SSA_NAME) + continue; + + root = SSA_NAME_VAR (var); + if (gimple_default_def (cfun, root) == var) + { + /* This root variable should have not already been assigned + to another partition which is not coalesced with this one. */ + gcc_assert (!var_ann (root)->out_of_ssa_tag); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + print_exprs (dump_file, "Must coalesce ", var, + " with the root variable ", root, ".\n"); + } + change_partition_var (map, root, x); + } + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + dump_var_map (dump_file, map); + + /* Now coalesce everything in the list. */ + coalesce_partitions (map, graph, cl, + ((dump_flags & TDF_DETAILS) ? dump_file + : NULL)); + + delete_coalesce_list (cl); + ssa_conflicts_delete (graph); + + return map; +} + diff --git a/gcc/tree-ssa-live.c b/gcc/tree-ssa-live.c index 277e2763bc5..2049e43d0d4 100644 --- a/gcc/tree-ssa-live.c +++ b/gcc/tree-ssa-live.c @@ -24,44 +24,107 @@ Boston, MA 02110-1301, USA. */ #include "coretypes.h" #include "tm.h" #include "tree.h" -#include "flags.h" -#include "basic-block.h" -#include "function.h" #include "diagnostic.h" #include "bitmap.h" #include "tree-flow.h" -#include "tree-gimple.h" -#include "tree-inline.h" -#include "varray.h" -#include "timevar.h" -#include "hashtab.h" #include "tree-dump.h" #include "tree-ssa-live.h" #include "toplev.h" -#include "vecprim.h" - -static void live_worklist (tree_live_info_p); -static tree_live_info_p new_tree_live_info (var_map); -static inline void set_if_valid (var_map, bitmap, tree); -static inline void add_conflicts_if_valid (tpa_p, conflict_graph, - var_map, bitmap, tree); -static partition_pair_p find_partition_pair (coalesce_list_p, int, int, bool); + #ifdef ENABLE_CHECKING static void verify_live_on_entry (tree_live_info_p); #endif -/* This is where the mapping from SSA version number to real storage variable - is tracked. - All SSA versions of the same variable may not ultimately be mapped back to - the same real variable. In that instance, we need to detect the live - range overlap, and give one of the variable new storage. The vector - 'partition_to_var' tracks which partition maps to which variable. +/* VARMAP maintains a mapping from SSA version number to real variables. + + All SSA_NAMES are divided into partitions. Initially each ssa_name is the + only member of it's own partition. Coalescing will attempt to group any + ssa_names which occur in a copy or in a PHI node into the same partition. + + At the end of out-of-ssa, each partition becomes a "real" variable and is + rewritten as a compiler variable. + + The var_map datat structure is used to manage these partitions. It allows + partitions to be combined, and determines which partition belongs to what + ssa_name or variable, and vice versa. */ + + +/* This routine will initialize the basevar fields of MAP. */ + +static void +var_map_base_init (var_map map) +{ + int x, num_part, num; + tree var; + var_ann_t ann; + + num = 0; + num_part = num_var_partitions (map); + + /* If a base table already exists, clear it, otherwise create it. */ + if (map->partition_to_base_index != NULL) + { + free (map->partition_to_base_index); + VEC_truncate (tree, map->basevars, 0); + } + else + map->basevars = VEC_alloc (tree, heap, MAX (40, (num_part / 10))); + + map->partition_to_base_index = (int *) xmalloc (sizeof (int) * num_part); + + /* Build the base variable list, and point partitions at their bases. */ + for (x = 0; x < num_part; x++) + { + var = partition_to_var (map, x); + if (TREE_CODE (var) == SSA_NAME) + var = SSA_NAME_VAR (var); + ann = var_ann (var); + /* If base variable hasn't been seen, set it up. */ + if (!ann->base_var_processed) + { + ann->base_var_processed = 1; + VAR_ANN_BASE_INDEX (ann) = num++; + VEC_safe_push (tree, heap, map->basevars, var); + } + map->partition_to_base_index[x] = VAR_ANN_BASE_INDEX (ann); + } - Given a VAR, it is sometimes desirable to know which partition that VAR - represents. There is an additional field in the variable annotation to - track that information. */ + map->num_basevars = num; + /* Now clear the processed bit. */ + for (x = 0; x < num; x++) + { + var = VEC_index (tree, map->basevars, x); + var_ann (var)->base_var_processed = 0; + } + +#ifdef ENABLE_CHECKING + for (x = 0; x < num_part; x++) + { + tree var2; + var = SSA_NAME_VAR (partition_to_var (map, x)); + var2 = VEC_index (tree, map->basevars, basevar_index (map, x)); + gcc_assert (var == var2); + } +#endif +} + + +/* Remove the base table in MAP. */ + +static void +var_map_base_fini (var_map map) +{ + /* Free the basevar info if it is present. */ + if (map->partition_to_base_index != NULL) + { + VEC_free (tree, heap, map->basevars); + free (map->partition_to_base_index); + map->partition_to_base_index = NULL; + map->num_basevars = 0; + } +} /* Create a variable partition map of SIZE, initialize and return it. */ var_map @@ -75,10 +138,13 @@ init_var_map (int size) = (tree *)xmalloc (size * sizeof (tree)); memset (map->partition_to_var, 0, size * sizeof (tree)); - map->partition_to_compact = NULL; - map->compact_to_partition = NULL; + map->partition_to_view = NULL; + map->view_to_partition = NULL; map->num_partitions = size; map->partition_size = size; + map->num_basevars = 0; + map->partition_to_base_index = NULL; + map->basevars = NULL; return map; } @@ -88,12 +154,13 @@ init_var_map (int size) void delete_var_map (var_map map) { + var_map_base_fini (map); free (map->partition_to_var); partition_delete (map->var_partition); - if (map->partition_to_compact) - free (map->partition_to_compact); - if (map->compact_to_partition) - free (map->compact_to_partition); + if (map->partition_to_view) + free (map->partition_to_view); + if (map->view_to_partition) + free (map->view_to_partition); free (map); } @@ -109,17 +176,17 @@ var_union (var_map map, tree var1, tree var2) tree root_var = NULL_TREE; tree other_var = NULL_TREE; - /* This is independent of partition_to_compact. If partition_to_compact is + /* This is independent of partition_to_view. If partition_to_view is on, then whichever one of these partitions is absorbed will never have a - dereference into the partition_to_compact array any more. */ + dereference into the partition_to_view array any more. */ if (TREE_CODE (var1) == SSA_NAME) p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1)); else { p1 = var_to_partition (map, var1); - if (map->compact_to_partition) - p1 = map->compact_to_partition[p1]; + if (map->view_to_partition) + p1 = map->view_to_partition[p1]; root_var = var1; } @@ -128,8 +195,8 @@ var_union (var_map map, tree var1, tree var2) else { p2 = var_to_partition (map, var2); - if (map->compact_to_partition) - p2 = map->compact_to_partition[p2]; + if (map->view_to_partition) + p2 = map->view_to_partition[p2]; /* If there is no root_var set, or it's not a user variable, set the root_var to this one. */ @@ -150,8 +217,8 @@ var_union (var_map map, tree var1, tree var2) else p3 = partition_union (map->var_partition, p1, p2); - if (map->partition_to_compact) - p3 = map->partition_to_compact[p3]; + if (map->partition_to_view) + p3 = map->partition_to_view[p3]; if (root_var) change_partition_var (map, root_var, p3); @@ -161,12 +228,12 @@ var_union (var_map map, tree var1, tree var2) return p3; } - + /* Compress the partition numbers in MAP such that they fall in the range 0..(num_partitions-1) instead of wherever they turned out during the partitioning exercise. This removes any references to unused partitions, thereby allowing bitmaps and other vectors to be much - denser. Compression type is controlled by FLAGS. + denser. This is implemented such that compaction doesn't affect partitioning. Ie., once partitions are created and possibly merged, running one @@ -179,96 +246,140 @@ var_union (var_map map, tree var1, tree var2) definitions, and then 'recompact' later to include all the single definitions for assignment to program variables. */ -void -compact_var_map (var_map map, int flags) + +/* Set MAP back to the initial state of having no partition view. Return a + bitmap which has a bit set for each partition number which is in use in the + varmap. */ + +static bitmap +partition_view_init (var_map map) { - sbitmap used; - int tmp, root, root_i; - unsigned int x, limit, count; - tree var; - root_var_p rv = NULL; + bitmap used; + int tmp; + unsigned int x; - limit = map->partition_size; - used = sbitmap_alloc (limit); - sbitmap_zero (used); + used = BITMAP_ALLOC (NULL); - /* Already compressed? Abandon the old one. */ - if (map->partition_to_compact) + /* Already in a view? Abandon the old one. */ + if (map->partition_to_view) { - free (map->partition_to_compact); - map->partition_to_compact = NULL; + free (map->partition_to_view); + map->partition_to_view = NULL; } - if (map->compact_to_partition) + if (map->view_to_partition) { - free (map->compact_to_partition); - map->compact_to_partition = NULL; + free (map->view_to_partition); + map->view_to_partition = NULL; } - map->num_partitions = map->partition_size; - - if (flags & VARMAP_NO_SINGLE_DEFS) - rv = root_var_init (map); - - map->partition_to_compact = (int *)xmalloc (limit * sizeof (int)); - memset (map->partition_to_compact, 0xff, (limit * sizeof (int))); - /* Find out which partitions are actually referenced. */ - count = 0; - for (x = 0; x < limit; x++) + for (x = 0; x < map->partition_size; x++) { tmp = partition_find (map->var_partition, x); - if (!TEST_BIT (used, tmp) && map->partition_to_var[tmp] != NULL_TREE) - { - /* It is referenced, check to see if there is more than one version - in the root_var table, if one is available. */ - if (rv) - { - root = root_var_find (rv, tmp); - root_i = root_var_first_partition (rv, root); - /* If there is only one, don't include this in the compaction. */ - if (root_var_next_partition (rv, root_i) == ROOT_VAR_NONE) - continue; - } - SET_BIT (used, tmp); - count++; - } + if (map->partition_to_var[tmp] != NULL_TREE && !bitmap_bit_p (used, tmp)) + bitmap_set_bit (used, tmp); } - /* Build a compacted partitioning. */ - if (count != limit) + map->num_partitions = map->partition_size; + return used; +} + + +/* This routine will finalize the view data for MAP based on the partitions + set in SELECTED. This is either the same bitmap returned from + partition_view_init, or a trimmed down version if some of those partitions + were not desired in this view. SELECTED is freed before returning. */ + +static void +partition_view_fini (var_map map, bitmap selected) +{ + bitmap_iterator bi; + unsigned count, i, x, limit; + tree var; + + gcc_assert (selected); + + count = bitmap_count_bits (selected); + limit = map->partition_size; + + /* If its a one-to-one ratio, we don't need any view compaction. */ + if (count < limit) { - sbitmap_iterator sbi; + map->partition_to_view = (int *)xmalloc (limit * sizeof (int)); + memset (map->partition_to_view, 0xff, (limit * sizeof (int))); + map->view_to_partition = (int *)xmalloc (count * sizeof (int)); - map->compact_to_partition = (int *)xmalloc (count * sizeof (int)); - count = 0; - /* SSA renaming begins at 1, so skip 0 when compacting. */ - EXECUTE_IF_SET_IN_SBITMAP (used, 1, x, sbi) + i = 0; + /* Give each selected partition an index. */ + EXECUTE_IF_SET_IN_BITMAP (selected, 0, x, bi) { - map->partition_to_compact[x] = count; - map->compact_to_partition[count] = x; + map->partition_to_view[x] = i; + map->view_to_partition[i] = x; var = map->partition_to_var[x]; + /* If any one of the members of a partition is not an SSA_NAME, make + sure it is the representative. */ if (TREE_CODE (var) != SSA_NAME) - change_partition_var (map, var, count); - count++; + change_partition_var (map, var, i); + i++; } + gcc_assert (i == count); + map->num_partitions = i; } + + BITMAP_FREE (selected); +} + + +/* Create a partition view which includes all the used partitions in MAP. If + WANT_BASES is true, create the base variable map as well. */ + +extern void +partition_view_normal (var_map map, bool want_bases) +{ + bitmap used; + + used = partition_view_init (map); + partition_view_fini (map, used); + + if (want_bases) + var_map_base_init (map); else + var_map_base_fini (map); +} + + +/* Create a partition view in MAP which includes just partitions which occur in + the bitmap ONLY. If WANT_BASES is true, create the base variable map + as well. */ + +extern void +partition_view_bitmap (var_map map, bitmap only, bool want_bases) +{ + bitmap used; + bitmap new_partitions = BITMAP_ALLOC (NULL); + unsigned x, p; + bitmap_iterator bi; + + used = partition_view_init (map); + EXECUTE_IF_SET_IN_BITMAP (only, 0, x, bi) { - free (map->partition_to_compact); - map->partition_to_compact = NULL; + p = partition_find (map->var_partition, x); + gcc_assert (bitmap_bit_p (used, p)); + bitmap_set_bit (new_partitions, p); } + partition_view_fini (map, new_partitions); - map->num_partitions = count; - - if (rv) - root_var_delete (rv); - sbitmap_free (used); + BITMAP_FREE (used); + if (want_bases) + var_map_base_init (map); + else + var_map_base_fini (map); } /* This function is used to change the representative variable in MAP for VAR's - partition from an SSA_NAME variable to a regular variable. This allows - partitions to be mapped back to real variables. */ + partition to a regular non-ssa variable. This allows partitions to be + mapped back to real variables. */ void change_partition_var (var_map map, tree var, int part) @@ -280,10 +391,11 @@ change_partition_var (var_map map, tree var, int part) ann = var_ann (var); ann->out_of_ssa_tag = 1; VAR_ANN_PARTITION (ann) = part; - if (map->compact_to_partition) - map->partition_to_var[map->compact_to_partition[part]] = var; + if (map->view_to_partition) + map->partition_to_var[map->view_to_partition[part]] = var; } + static inline void mark_all_vars_used (tree *); /* Helper function for mark_all_vars_used, called via walk_tree. */ @@ -319,6 +431,7 @@ mark_all_vars_used_1 (tree *tp, int *walk_subtrees, return NULL; } + /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be eliminated during the tree->rtl conversion process. */ @@ -394,102 +507,6 @@ remove_unused_locals (void) } } -/* This function looks through the program and uses FLAGS to determine what - SSA versioned variables are given entries in a new partition table. This - new partition map is returned. */ - -var_map -create_ssa_var_map (void) -{ - block_stmt_iterator bsi; - basic_block bb; - tree var; - tree stmt; - var_map map; - ssa_op_iter iter; -#ifdef ENABLE_CHECKING - bitmap used_in_real_ops; - bitmap used_in_virtual_ops; -#endif - - map = init_var_map (num_ssa_names + 1); - -#ifdef ENABLE_CHECKING - used_in_real_ops = BITMAP_ALLOC (NULL); - used_in_virtual_ops = BITMAP_ALLOC (NULL); -#endif - - FOR_EACH_BB (bb) - { - tree phi, arg; - - for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) - { - int i; - register_ssa_partition (map, PHI_RESULT (phi)); - for (i = 0; i < PHI_NUM_ARGS (phi); i++) - { - arg = PHI_ARG_DEF (phi, i); - if (TREE_CODE (arg) == SSA_NAME) - register_ssa_partition (map, arg); - - mark_all_vars_used (&PHI_ARG_DEF_TREE (phi, i)); - } - } - - for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) - { - stmt = bsi_stmt (bsi); - - /* Register USE and DEF operands in each statement. */ - FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, (SSA_OP_DEF|SSA_OP_USE)) - { - register_ssa_partition (map, var); - -#ifdef ENABLE_CHECKING - bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (var))); -#endif - } - -#ifdef ENABLE_CHECKING - /* Validate that virtual ops don't get used in funny ways. */ - FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, - SSA_OP_VIRTUAL_USES | SSA_OP_VMUSTDEF) - { - bitmap_set_bit (used_in_virtual_ops, - DECL_UID (SSA_NAME_VAR (var))); - } - -#endif /* ENABLE_CHECKING */ - - mark_all_vars_used (bsi_stmt_ptr (bsi)); - } - } - -#if defined ENABLE_CHECKING - { - unsigned i; - bitmap both = BITMAP_ALLOC (NULL); - bitmap_and (both, used_in_real_ops, used_in_virtual_ops); - if (!bitmap_empty_p (both)) - { - bitmap_iterator bi; - - EXECUTE_IF_SET_IN_BITMAP (both, 0, i, bi) - fprintf (stderr, "Variable %s used in real and virtual operands\n", - get_name (referenced_var (i))); - internal_error ("SSA corruption"); - } - - BITMAP_FREE (used_in_real_ops); - BITMAP_FREE (used_in_virtual_ops); - BITMAP_FREE (both); - } -#endif - - return map; -} - /* Allocate and return a new live range information object base on MAP. */ @@ -541,7 +558,7 @@ delete_tree_live_info (tree_live_info_p live) } -/* Visit basic block BB, and propogate any required live on entry bits from +/* Visit basic block BB and propogate any required live on entry bits from LIVE into the predecessors. VISITED is the bitmap of visited blocks. TMP is a temporary work bitmap which is passed in to avoid reallocting it each time. */ @@ -565,8 +582,8 @@ loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited, pred_bb = e->src; if (pred_bb == ENTRY_BLOCK_PTR) continue; - /* tmp is vars live-=on-entry from BB that aren't defined in the - pred. block. This should be the live on entry vars to pred. + /* TMP is variables live-on-entry from BB that aren't defined in the + predecessor block. This should be the live on entry vars to pred. Note that liveout is the DEFs in a block while live on entry is being calculated. */ bitmap_and_compl (tmp, loe, live->liveout[pred_bb->index]); @@ -636,7 +653,7 @@ set_var_live_on_entry (tree ssa_name, tree_live_info_p live) if (stmt) { def_bb = bb_for_stmt (stmt); - /* Mark defs in liveout bitmap for now. */ + /* Mark defs in liveout bitmap temporarily. */ if (def_bb) bitmap_set_bit (live->liveout[def_bb->index], p); } @@ -698,7 +715,7 @@ calculate_live_on_exit (tree_live_info_p liveinfo) edge e; edge_iterator ei; - /* live on entry calculations used the liveouit vector for defs. */ + /* live on entry calculations used liveout vectors for defs, clear them. */ FOR_EACH_BB (bb) bitmap_clear (liveinfo->liveout[bb->index]); @@ -720,7 +737,7 @@ calculate_live_on_exit (tree_live_info_p liveinfo) bitmap_set_bit (liveinfo->liveout[e->src->index], p); } - /* add each successors live on entry to this bock live on exit. */ + /* Add each successors live on entry to this bock live on exit. */ FOR_EACH_EDGE (e, ei, bb->succs) if (e->dest != EXIT_BLOCK_PTR) bitmap_ior_into (liveinfo->liveout[bb->index], @@ -728,6 +745,7 @@ calculate_live_on_exit (tree_live_info_p liveinfo) } } + /* Given partition map MAP, calculate all the live on entry bitmaps for each partition. Return a new live info object. */ @@ -757,936 +775,6 @@ calculate_live_ranges (var_map map) } -/* Initialize a tree_partition_associator object using MAP. */ - -static tpa_p -tpa_init (var_map map) -{ - tpa_p tpa; - int num_partitions = num_var_partitions (map); - int x; - - if (num_partitions == 0) - return NULL; - - tpa = (tpa_p) xmalloc (sizeof (struct tree_partition_associator_d)); - tpa->num_trees = 0; - tpa->uncompressed_num = -1; - tpa->map = map; - tpa->next_partition = (int *)xmalloc (num_partitions * sizeof (int)); - memset (tpa->next_partition, TPA_NONE, num_partitions * sizeof (int)); - - tpa->partition_to_tree_map = (int *)xmalloc (num_partitions * sizeof (int)); - memset (tpa->partition_to_tree_map, TPA_NONE, num_partitions * sizeof (int)); - - x = MAX (40, (num_partitions / 20)); - tpa->trees = VEC_alloc (tree, heap, x); - tpa->first_partition = VEC_alloc (int, heap, x); - - return tpa; - -} - - -/* Remove PARTITION_INDEX from TREE_INDEX's list in the tpa structure TPA. */ - -void -tpa_remove_partition (tpa_p tpa, int tree_index, int partition_index) -{ - int i; - - i = tpa_first_partition (tpa, tree_index); - if (i == partition_index) - { - VEC_replace (int, tpa->first_partition, tree_index, - tpa->next_partition[i]); - } - else - { - for ( ; i != TPA_NONE; i = tpa_next_partition (tpa, i)) - { - if (tpa->next_partition[i] == partition_index) - { - tpa->next_partition[i] = tpa->next_partition[partition_index]; - break; - } - } - } -} - - -/* Free the memory used by tree_partition_associator object TPA. */ - -void -tpa_delete (tpa_p tpa) -{ - if (!tpa) - return; - - VEC_free (tree, heap, tpa->trees); - VEC_free (int, heap, tpa->first_partition); - free (tpa->partition_to_tree_map); - free (tpa->next_partition); - free (tpa); -} - - -/* This function will remove any tree entries from TPA which have only a single - element. This will help keep the size of the conflict graph down. The - function returns the number of remaining tree lists. */ - -int -tpa_compact (tpa_p tpa) -{ - int last, x, y, first, swap_i; - tree swap_t; - - /* Find the last list which has more than 1 partition. */ - for (last = tpa->num_trees - 1; last > 0; last--) - { - first = tpa_first_partition (tpa, last); - if (tpa_next_partition (tpa, first) != NO_PARTITION) - break; - } - - x = 0; - while (x < last) - { - first = tpa_first_partition (tpa, x); - - /* If there is not more than one partition, swap with the current end - of the tree list. */ - if (tpa_next_partition (tpa, first) == NO_PARTITION) - { - swap_t = VEC_index (tree, tpa->trees, last); - swap_i = VEC_index (int, tpa->first_partition, last); - - /* Update the last entry. Since it is known to only have one - partition, there is nothing else to update. */ - VEC_replace (tree, tpa->trees, last, - VEC_index (tree, tpa->trees, x)); - VEC_replace (int, tpa->first_partition, last, - VEC_index (int, tpa->first_partition, x)); - tpa->partition_to_tree_map[tpa_first_partition (tpa, last)] = last; - - /* Since this list is known to have more than one partition, update - the list owner entries. */ - VEC_replace (tree, tpa->trees, x, swap_t); - VEC_replace (int, tpa->first_partition, x, swap_i); - for (y = tpa_first_partition (tpa, x); - y != NO_PARTITION; - y = tpa_next_partition (tpa, y)) - tpa->partition_to_tree_map[y] = x; - - /* Ensure last is a list with more than one partition. */ - last--; - for (; last > x; last--) - { - first = tpa_first_partition (tpa, last); - if (tpa_next_partition (tpa, first) != NO_PARTITION) - break; - } - } - x++; - } - - first = tpa_first_partition (tpa, x); - if (tpa_next_partition (tpa, first) != NO_PARTITION) - x++; - tpa->uncompressed_num = tpa->num_trees; - tpa->num_trees = x; - return last; -} - - -/* Initialize a root_var object with SSA partitions from MAP which are based - on each root variable. */ - -root_var_p -root_var_init (var_map map) -{ - root_var_p rv; - int num_partitions = num_var_partitions (map); - int x, p; - tree t; - var_ann_t ann; - sbitmap seen; - - rv = tpa_init (map); - if (!rv) - return NULL; - - seen = sbitmap_alloc (num_partitions); - sbitmap_zero (seen); - - /* Start at the end and work towards the front. This will provide a list - that is ordered from smallest to largest. */ - for (x = num_partitions - 1; x >= 0; x--) - { - t = partition_to_var (map, x); - - /* The var map may not be compacted yet, so check for NULL. */ - if (!t) - continue; - - p = var_to_partition (map, t); - - gcc_assert (p != NO_PARTITION); - - /* Make sure we only put coalesced partitions into the list once. */ - if (TEST_BIT (seen, p)) - continue; - SET_BIT (seen, p); - if (TREE_CODE (t) == SSA_NAME) - t = SSA_NAME_VAR (t); - ann = var_ann (t); - if (ann->root_var_processed) - { - rv->next_partition[p] = VEC_index (int, rv->first_partition, - VAR_ANN_ROOT_INDEX (ann)); - VEC_replace (int, rv->first_partition, VAR_ANN_ROOT_INDEX (ann), p); - } - else - { - ann->root_var_processed = 1; - VAR_ANN_ROOT_INDEX (ann) = rv->num_trees++; - VEC_safe_push (tree, heap, rv->trees, t); - VEC_safe_push (int, heap, rv->first_partition, p); - } - rv->partition_to_tree_map[p] = VAR_ANN_ROOT_INDEX (ann); - } - - /* Reset the out_of_ssa_tag flag on each variable for later use. */ - for (x = 0; x < rv->num_trees; x++) - { - t = VEC_index (tree, rv->trees, x); - var_ann (t)->root_var_processed = 0; - } - - sbitmap_free (seen); - return rv; -} - - -/* Hash function for 2 integer coalesce pairs. */ -#define COALESCE_HASH_FN(R1, R2) ((R2) * ((R2) - 1) / 2 + (R1)) - - -/* Return hash value for partition pair PAIR. */ - -unsigned int -partition_pair_map_hash (const void *pair) -{ - hashval_t a = (hashval_t)(((partition_pair_p)pair)->first_partition); - hashval_t b = (hashval_t)(((partition_pair_p)pair)->second_partition); - - return COALESCE_HASH_FN (a,b); -} - - -/* Return TRUE if PAIR1 is equivalent to PAIR2. */ - -int -partition_pair_map_eq (const void *pair1, const void *pair2) -{ - partition_pair_p p1 = (partition_pair_p) pair1; - partition_pair_p p2 = (partition_pair_p) pair2; - - return (p1->first_partition == p2->first_partition - && p1->second_partition == p2->second_partition); -} - - -/* Create a new coalesce list object from MAP and return it. */ - -coalesce_list_p -create_coalesce_list (var_map map) -{ - coalesce_list_p list; - unsigned size = num_ssa_names * 3; - - if (size < 40) - size = 40; - - list = xmalloc (sizeof (struct coalesce_list_d)); - list->list = htab_create (size, partition_pair_map_hash, - partition_pair_map_eq, NULL); - - list->map = map; - list->sorted = NULL; - list->add_mode = true; - list->num_sorted = 0; - return list; -} - - -/* Delete coalesce list CL. */ - -void -delete_coalesce_list (coalesce_list_p cl) -{ - htab_delete (cl->list); - if (cl->sorted) - free (cl->sorted); - gcc_assert (cl->num_sorted == 0); - free (cl); -} - - -/* Find a matching coalesce pair object in CL for partitions P1 and P2. If - one isn't found, return NULL if CREATE is false, otherwise create a new - coalesce pair object and return it. */ - -static partition_pair_p -find_partition_pair (coalesce_list_p cl, int p1, int p2, bool create) -{ - struct partition_pair p, *pair; - void **slot; - unsigned int hash; - - /* normalize so that p1 is the smaller value. */ - if (p2 < p1) - { - p.first_partition = p2; - p.second_partition = p1; - } - else - { - p.first_partition = p1; - p.second_partition = p2; - } - - - hash = partition_pair_map_hash (&p); - pair = (struct partition_pair *) htab_find_with_hash (cl->list, &p, hash); - - if (create && !pair) - { - gcc_assert (cl->add_mode); - pair = xmalloc (sizeof (struct partition_pair)); - pair->first_partition = p.first_partition; - pair->second_partition = p.second_partition; - pair->cost = 0; - slot = htab_find_slot_with_hash (cl->list, pair, hash, INSERT); - *(struct partition_pair **)slot = pair; - } - - return pair; -} - -/* Return cost of execution of copy instruction with FREQUENCY - possibly on CRITICAL edge and in HOT basic block. */ -int -coalesce_cost (int frequency, bool hot, bool critical) -{ - /* Base costs on BB frequencies bounded by 1. */ - int cost = frequency; - - if (!cost) - cost = 1; - if (optimize_size || hot) - cost = 1; - /* Inserting copy on critical edge costs more - than inserting it elsewhere. */ - if (critical) - cost *= 2; - return cost; -} - -/* Add a potential coalesce between P1 and P2 in CL with a cost of VALUE. */ - -void -add_coalesce (coalesce_list_p cl, int p1, int p2, - int value) -{ - partition_pair_p node; - - gcc_assert (cl->add_mode); - - if (p1 == p2) - return; - - node = find_partition_pair (cl, p1, p2, true); - - node->cost += value; -} - - -/* Comparison function to allow qsort to sort P1 and P2 in Ascending order. */ - -static -int compare_pairs (const void *p1, const void *p2) -{ - return (*(partition_pair_p *)p1)->cost - (*(partition_pair_p *)p2)->cost; -} - - -static inline int -num_coalesce_pairs (coalesce_list_p cl) -{ - return htab_elements (cl->list); -} - -typedef struct -{ - htab_iterator hti; -} partition_pair_iterator; - -static inline partition_pair_p -first_partition_pair (coalesce_list_p cl, partition_pair_iterator *iter) -{ - partition_pair_p pair; - - pair = (partition_pair_p) first_htab_element (&(iter->hti), cl->list); - return pair; -} - -static inline bool -end_partition_pair_p (partition_pair_iterator *iter) -{ - return end_htab_p (&(iter->hti)); -} - -static inline partition_pair_p -next_partition_pair (partition_pair_iterator *iter) -{ - partition_pair_p pair; - - pair = (partition_pair_p) next_htab_element (&(iter->hti)); - return pair; -} - -#define FOR_EACH_PARTITION_PAIR(PAIR, ITER, CL) \ - for ((PAIR) = first_partition_pair ((CL), &(ITER)); \ - !end_partition_pair_p (&(ITER)); \ - (PAIR) = next_partition_pair (&(ITER))) - - -/* Prepare CL for removal of preferred pairs. When finished, list element - 0 has all the coalesce pairs, sorted in order from most important coalesce - to least important. */ - -void -sort_coalesce_list (coalesce_list_p cl) -{ - unsigned x, num; - partition_pair_p p; - partition_pair_iterator ppi; - - gcc_assert (cl->add_mode); - - cl->add_mode = false; - - /* allocate a vector for the pair pointers. */ - num = num_coalesce_pairs (cl); - cl->num_sorted = num; - if (num == 0) - return; - cl->sorted = XNEWVEC (partition_pair_p, num); - - /* Populate the vector with pointers to the partition pairs. */ - - x = 0; - FOR_EACH_PARTITION_PAIR (p, ppi, cl) - cl->sorted[x++] = p; - gcc_assert (x == num); - - if (num == 1) - return; - - if (num == 2) - { - if (cl->sorted[0]->cost > cl->sorted[1]->cost) - { - p = cl->sorted[0]; - cl->sorted[0] = cl->sorted[1]; - cl->sorted[1] = p; - } - return; - } - - /* Only call qsort if there are more than 2 items. */ - if (num > 2) - qsort (cl->sorted, num, sizeof (partition_pair_p), compare_pairs); -} - - -/* Retrieve the best remaining pair to coalesce from CL. Returns the 2 - partitions via P1 and P2. Their calculated cost is returned by the function. - NO_BEST_COALESCE is returned if the coalesce list is empty. */ - -static int -pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2) -{ - partition_pair_p node; - int ret; - - gcc_assert (!cl->add_mode); - - if (cl->num_sorted == 0) - return NO_BEST_COALESCE; - - node = cl->sorted[--(cl->num_sorted)]; - - *p1 = node->first_partition; - *p2 = node->second_partition; - ret = node->cost; - free (node); - - return ret; -} - - -/* If variable VAR is in a partition in MAP, add a conflict in GRAPH between - VAR and any other live partitions in VEC which are associated via TPA. - Reset the live bit in VEC. */ - -static inline void -add_conflicts_if_valid (tpa_p tpa, conflict_graph graph, - var_map map, bitmap vec, tree var) -{ - int p, y, first; - p = var_to_partition (map, var); - if (p != NO_PARTITION) - { - bitmap_clear_bit (vec, p); - first = tpa_find_tree (tpa, p); - /* If find returns nothing, this object isn't interesting. */ - if (first == TPA_NONE) - return; - /* Only add interferences between objects in the same list. */ - for (y = tpa_first_partition (tpa, first); - y != TPA_NONE; - y = tpa_next_partition (tpa, y)) - { - if (bitmap_bit_p (vec, y)) - conflict_graph_add (graph, p, y); - } - } -} - - -/* If VAR is in a partition of MAP, set the bit for that partition in VEC. */ - -static inline void -set_if_valid (var_map map, bitmap vec, tree var) -{ - int p = var_to_partition (map, var); - if (p != NO_PARTITION) - bitmap_set_bit (vec, p); -} - -/* Return a conflict graph for the information contained in LIVE_INFO. Only - conflicts between items in the same TPA list are added. If optional - coalesce list CL is passed in, any copies encountered are added. */ - -conflict_graph -build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa, - coalesce_list_p cl) -{ - conflict_graph graph; - var_map map; - bitmap live; - unsigned x, y, i; - basic_block bb; - int *partition_link, *tpa_nodes; - VEC(int,heap) *tpa_to_clear; - unsigned l; - ssa_op_iter iter; - bitmap_iterator bi; - - map = live_var_map (liveinfo); - graph = conflict_graph_new (num_var_partitions (map)); - - if (tpa_num_trees (tpa) == 0) - return graph; - - live = BITMAP_ALLOC (NULL); - - partition_link = XCNEWVEC (int, num_var_partitions (map) + 1); - tpa_nodes = XCNEWVEC (int, tpa_num_trees (tpa)); - tpa_to_clear = VEC_alloc (int, heap, 50); - - FOR_EACH_BB (bb) - { - block_stmt_iterator bsi; - tree phi; - int idx; - - /* Start with live on exit temporaries. */ - bitmap_copy (live, live_on_exit (liveinfo, bb)); - - for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi)) - { - bool is_a_copy = false; - tree stmt = bsi_stmt (bsi); - - /* A copy between 2 partitions does not introduce an interference - by itself. If they did, you would never be able to coalesce - two things which are copied. If the two variables really do - conflict, they will conflict elsewhere in the program. - - This is handled specially here since we may also be interested - in copies between real variables and SSA_NAME variables. We may - be interested in trying to coalesce SSA_NAME variables with - root variables in some cases. */ - - if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT) - { - tree lhs = GIMPLE_STMT_OPERAND (stmt, 0); - tree rhs = GIMPLE_STMT_OPERAND (stmt, 1); - int p1, p2; - int bit; - - if (DECL_P (lhs) || TREE_CODE (lhs) == SSA_NAME) - p1 = var_to_partition (map, lhs); - else - p1 = NO_PARTITION; - - if (DECL_P (rhs) || TREE_CODE (rhs) == SSA_NAME) - p2 = var_to_partition (map, rhs); - else - p2 = NO_PARTITION; - - if (p1 != NO_PARTITION && p2 != NO_PARTITION) - { - is_a_copy = true; - bit = bitmap_bit_p (live, p2); - /* If the RHS is live, make it not live while we add - the conflicts, then make it live again. */ - if (bit) - bitmap_clear_bit (live, p2); - add_conflicts_if_valid (tpa, graph, map, live, lhs); - if (bit) - bitmap_set_bit (live, p2); - if (cl) - add_coalesce (cl, p1, p2, - coalesce_cost (bb->frequency, - maybe_hot_bb_p (bb), false)); - set_if_valid (map, live, rhs); - } - } - - if (!is_a_copy) - { - tree var; - FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF) - { - add_conflicts_if_valid (tpa, graph, map, live, var); - } - - FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE) - { - set_if_valid (map, live, var); - } - } - } - - /* If result of a PHI is unused, then the loops over the statements - will not record any conflicts. However, since the PHI node is - going to be translated out of SSA form we must record a conflict - between the result of the PHI and any variables with are live. - Otherwise the out-of-ssa translation may create incorrect code. */ - for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) - { - tree result = PHI_RESULT (phi); - int p = var_to_partition (map, result); - - if (p != NO_PARTITION && ! bitmap_bit_p (live, p)) - add_conflicts_if_valid (tpa, graph, map, live, result); - } - - /* Anything which is still live at this point interferes. - In order to implement this efficiently, only conflicts between - partitions which have the same TPA root need be added. - TPA roots which have been seen are tracked in 'tpa_nodes'. A nonzero - entry points to an index into 'partition_link', which then indexes - into itself forming a linked list of partitions sharing a tpa root - which have been seen as live up to this point. Since partitions start - at index zero, all entries in partition_link are (partition + 1). - - Conflicts are added between the current partition and any already seen. - tpa_clear contains all the tpa_roots processed, and these are the only - entries which need to be zero'd out for a clean restart. */ - - EXECUTE_IF_SET_IN_BITMAP (live, 0, x, bi) - { - i = tpa_find_tree (tpa, x); - if (i != (unsigned)TPA_NONE) - { - int start = tpa_nodes[i]; - /* If start is 0, a new root reference list is being started. - Register it to be cleared. */ - if (!start) - VEC_safe_push (int, heap, tpa_to_clear, i); - - /* Add interferences to other tpa members seen. */ - for (y = start; y != 0; y = partition_link[y]) - conflict_graph_add (graph, x, y - 1); - tpa_nodes[i] = x + 1; - partition_link[x + 1] = start; - } - } - - /* Now clear the used tpa root references. */ - for (l = 0; VEC_iterate (int, tpa_to_clear, l, idx); l++) - tpa_nodes[idx] = 0; - VEC_truncate (int, tpa_to_clear, 0); - } - - free (tpa_nodes); - free (partition_link); - VEC_free (int, heap, tpa_to_clear); - BITMAP_FREE (live); - return graph; -} - - -/* This routine will attempt to coalesce the elements in TPA subject to the - conflicts found in GRAPH. If optional coalesce_list CL is provided, - only coalesces specified within the coalesce list are attempted. Otherwise - an attempt is made to coalesce as many partitions within each TPA grouping - as possible. If DEBUG is provided, debug output will be sent there. */ - -void -coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map, - coalesce_list_p cl, FILE *debug) -{ - int x, y, z, w; - tree var, tmp; - - /* Attempt to coalesce any items in a coalesce list. */ - if (cl) - { - while (pop_best_coalesce (cl, &x, &y) != NO_BEST_COALESCE) - { - if (debug) - { - fprintf (debug, "Coalesce list: (%d)", x); - print_generic_expr (debug, partition_to_var (map, x), TDF_SLIM); - fprintf (debug, " & (%d)", y); - print_generic_expr (debug, partition_to_var (map, y), TDF_SLIM); - } - - w = tpa_find_tree (tpa, x); - z = tpa_find_tree (tpa, y); - if (w != z || w == TPA_NONE || z == TPA_NONE) - { - if (debug) - { - if (w != z) - fprintf (debug, ": Fail, Non-matching TPA's\n"); - if (w == TPA_NONE) - fprintf (debug, ": Fail %d non TPA.\n", x); - else - fprintf (debug, ": Fail %d non TPA.\n", y); - } - continue; - } - var = partition_to_var (map, x); - tmp = partition_to_var (map, y); - x = var_to_partition (map, var); - y = var_to_partition (map, tmp); - if (debug) - fprintf (debug, " [map: %d, %d] ", x, y); - if (x == y) - { - if (debug) - fprintf (debug, ": Already Coalesced.\n"); - continue; - } - if (!conflict_graph_conflict_p (graph, x, y)) - { - z = var_union (map, var, tmp); - if (z == NO_PARTITION) - { - if (debug) - fprintf (debug, ": Unable to perform partition union.\n"); - continue; - } - - /* z is the new combined partition. We need to remove the other - partition from the list. Set x to be that other partition. */ - if (z == x) - { - conflict_graph_merge_regs (graph, x, y); - w = tpa_find_tree (tpa, y); - tpa_remove_partition (tpa, w, y); - } - else - { - conflict_graph_merge_regs (graph, y, x); - w = tpa_find_tree (tpa, x); - tpa_remove_partition (tpa, w, x); - } - - if (debug) - fprintf (debug, ": Success -> %d\n", z); - } - else - if (debug) - fprintf (debug, ": Fail due to conflict\n"); - } - /* If using a coalesce list, don't try to coalesce anything else. */ - return; - } - - for (x = 0; x < tpa_num_trees (tpa); x++) - { - while (tpa_first_partition (tpa, x) != TPA_NONE) - { - int p1, p2; - /* Coalesce first partition with anything that doesn't conflict. */ - y = tpa_first_partition (tpa, x); - tpa_remove_partition (tpa, x, y); - - var = partition_to_var (map, y); - /* p1 is the partition representative to which y belongs. */ - p1 = var_to_partition (map, var); - - for (z = tpa_next_partition (tpa, y); - z != TPA_NONE; - z = tpa_next_partition (tpa, z)) - { - tmp = partition_to_var (map, z); - /* p2 is the partition representative to which z belongs. */ - p2 = var_to_partition (map, tmp); - if (debug) - { - fprintf (debug, "Coalesce : "); - print_generic_expr (debug, var, TDF_SLIM); - fprintf (debug, " &"); - print_generic_expr (debug, tmp, TDF_SLIM); - fprintf (debug, " (%d ,%d)", p1, p2); - } - - /* If partitions are already merged, don't check for conflict. */ - if (tmp == var) - { - tpa_remove_partition (tpa, x, z); - if (debug) - fprintf (debug, ": Already coalesced\n"); - } - else - if (!conflict_graph_conflict_p (graph, p1, p2)) - { - int v; - if (tpa_find_tree (tpa, y) == TPA_NONE - || tpa_find_tree (tpa, z) == TPA_NONE) - { - if (debug) - fprintf (debug, ": Fail non-TPA member\n"); - continue; - } - if ((v = var_union (map, var, tmp)) == NO_PARTITION) - { - if (debug) - fprintf (debug, ": Fail cannot combine partitions\n"); - continue; - } - - tpa_remove_partition (tpa, x, z); - if (v == p1) - conflict_graph_merge_regs (graph, v, z); - else - { - /* Update the first partition's representative. */ - conflict_graph_merge_regs (graph, v, y); - p1 = v; - } - - /* The root variable of the partition may be changed - now. */ - var = partition_to_var (map, p1); - - if (debug) - fprintf (debug, ": Success -> %d\n", v); - } - else - if (debug) - fprintf (debug, ": Fail, Conflict\n"); - } - } - } -} - - -/* Send debug info for coalesce list CL to file F. */ - -void -dump_coalesce_list (FILE *f, coalesce_list_p cl) -{ - partition_pair_p node; - partition_pair_iterator ppi; - int x; - tree var; - - if (cl->add_mode) - { - fprintf (f, "Coalesce List:\n"); - FOR_EACH_PARTITION_PAIR (node, ppi, cl) - { - tree var1 = partition_to_var (cl->map, node->first_partition); - tree var2 = partition_to_var (cl->map, node->second_partition); - print_generic_expr (f, var1, TDF_SLIM); - fprintf (f, " <-> "); - print_generic_expr (f, var2, TDF_SLIM); - fprintf (f, " (%1d), ", node->cost); - fprintf (f, "\n"); - } - } - else - { - fprintf (f, "Sorted Coalesce list:\n"); - for (x = cl->num_sorted - 1 ; x >=0; x--) - { - node = cl->sorted[x]; - fprintf (f, "(%d) ", node->cost); - var = partition_to_var (cl->map, node->first_partition); - print_generic_expr (f, var, TDF_SLIM); - fprintf (f, " <-> "); - var = partition_to_var (cl->map, node->second_partition); - print_generic_expr (f, var, TDF_SLIM); - fprintf (f, "\n"); - } - } -} - - -/* Output tree_partition_associator object TPA to file F.. */ - -void -tpa_dump (FILE *f, tpa_p tpa) -{ - int x, i; - - if (!tpa) - return; - - for (x = 0; x < tpa_num_trees (tpa); x++) - { - print_generic_expr (f, tpa_tree (tpa, x), TDF_SLIM); - fprintf (f, " : ("); - for (i = tpa_first_partition (tpa, x); - i != TPA_NONE; - i = tpa_next_partition (tpa, i)) - { - fprintf (f, "(%d)",i); - print_generic_expr (f, partition_to_var (tpa->map, i), TDF_SLIM); - fprintf (f, " "); - -#ifdef ENABLE_CHECKING - if (tpa_find_tree (tpa, i) != x) - fprintf (f, "**find tree incorrectly set** "); -#endif - - } - fprintf (f, ")\n"); - } - fflush (f); -} - - /* Output partition map MAP to file F. */ void @@ -1700,8 +788,8 @@ dump_var_map (FILE *f, var_map map) for (x = 0; x < map->num_partitions; x++) { - if (map->compact_to_partition != NULL) - p = map->compact_to_partition[x]; + if (map->view_to_partition != NULL) + p = map->view_to_partition[x]; else p = x; @@ -1712,8 +800,8 @@ dump_var_map (FILE *f, var_map map) for (y = 1; y < num_ssa_names; y++) { p = partition_find (map->var_partition, y); - if (map->partition_to_compact) - p = map->partition_to_compact[p]; + if (map->partition_to_view) + p = map->partition_to_view[p]; if (p == (int)x) { if (t++ == 0) @@ -1771,7 +859,10 @@ dump_live_info (FILE *f, tree_live_info_p live, int flag) } } + #ifdef ENABLE_CHECKING +/* Verify that SSA_VAR is a non-virtual SSA_NAME. */ + void register_ssa_partition_check (tree ssa_var) { @@ -1787,6 +878,7 @@ register_ssa_partition_check (tree ssa_var) /* Verify that the info in LIVE matches the current cfg. */ + static void verify_live_on_entry (tree_live_info_p live) { @@ -1802,7 +894,6 @@ verify_live_on_entry (tree_live_info_p live) /* Check for live on entry partitions and report those with a DEF in the program. This will typically mean an optimization has done something wrong. */ - bb = ENTRY_BLOCK_PTR; num = 0; FOR_EACH_EDGE (e, ei, bb->succs) diff --git a/gcc/tree-ssa-live.h b/gcc/tree-ssa-live.h index 19c708922e8..bddd4ba77c6 100644 --- a/gcc/tree-ssa-live.h +++ b/gcc/tree-ssa-live.h @@ -26,56 +26,83 @@ Boston, MA 02110-1301, USA. */ #include "partition.h" #include "vecprim.h" -/* Used to create the variable mapping when we go out of SSA form. */ + + +/* Used to create the variable mapping when we go out of SSA form. + + Mapping from an ssa_name to a partition number is maintained, as well as + partition number to back to ssa_name. A parition can also be represented + by a non-ssa_name variable. This allows ssa_names and thier partition to + be coalesced with live on entry compiler variables, as well as eventually + having real compiler variables assigned to each partition as part of the + final stage of going of of ssa. + + Non-ssa_names maintain their partition index in the variable annotation. + + This data structure also supports "views", which work on a subset of all + partitions. This allows the coalescer to decide what partitions are + interesting to it, and only work with those partitions. Whenever the view + is changed, the partition numbers change, but none of the partition groupings + change. (ie, it is truly a view since it doesnt change anything) + + The final component of the data structure is the basevar map. This provides + a list of all the different base variables which occue in a partition view, + and a unique index for each one. Routines are provided to quickly produce + the base variable of a partition. + + Note that members of a partition MUST all have the same base variable. */ + typedef struct _var_map { - /* The partition of all variables. */ + /* The partition manager of all variables. */ partition var_partition; - /* Vector for compacting partitions. */ - int *partition_to_compact; - int *compact_to_partition; + /* Vector for managing partitions views. */ + int *partition_to_view; + int *view_to_partition; - /* Mapping of partition numbers to vars. */ + /* Mapping of partition numbers to variables. */ tree *partition_to_var; - /* Current number of partitions. */ + /* Current number of partitions in var_map based on the current view. */ unsigned int num_partitions; - /* Original partition size. */ + /* Original full partition size. */ unsigned int partition_size; + + /* Number of base variables in the base var list. */ + int num_basevars; + + /* Map of partitions numbers to base variable table indexes. */ + int *partition_to_base_index; + + /* Table of base variable's. */ + VEC (tree, heap) *basevars; } *var_map; -#define VAR_ANN_PARTITION(ann) (ann->partition) -#define VAR_ANN_ROOT_INDEX(ann) (ann->root_index) -#define NO_PARTITION -1 +/* Partition number of a non ssa-name variable. */ +#define VAR_ANN_PARTITION(ann) (ann->partition) +/* Index iot the basevar table of a non ssa-name variable. */ +#define VAR_ANN_BASE_INDEX(ann) (ann->base_index) -/* Flags to pass to compact_var_map */ -#define VARMAP_NORMAL 0 -#define VARMAP_NO_SINGLE_DEFS 1 +/* Value used to represent no partition number. */ +#define NO_PARTITION -1 extern var_map init_var_map (int); extern void delete_var_map (var_map); extern void dump_var_map (FILE *, var_map); extern int var_union (var_map, tree, tree); extern void change_partition_var (var_map, tree, int); -extern void compact_var_map (var_map, int); +extern void partition_view_normal (var_map, bool); +extern void partition_view_bitmap (var_map, bitmap, bool); #ifdef ENABLE_CHECKING extern void register_ssa_partition_check (tree ssa_var); #endif -static inline unsigned num_var_partitions (var_map); -static inline tree var_to_partition_to_var (var_map, tree); -static inline tree partition_to_var (var_map, int); -static inline int var_to_partition (var_map, tree); -static inline tree version_to_var (var_map, int); -static inline void register_ssa_partition (var_map, tree); -extern var_map create_ssa_var_map (void); - -/* Number of partitions in MAP. */ +/* Return number of partitions in MAP. */ static inline unsigned num_var_partitions (var_map map) @@ -90,8 +117,8 @@ num_var_partitions (var_map map) static inline tree partition_to_var (var_map map, int i) { - if (map->compact_to_partition) - i = map->compact_to_partition[i]; + if (map->view_to_partition) + i = map->view_to_partition[i]; i = partition_find (map->var_partition, i); return map->partition_to_var[i]; } @@ -100,12 +127,13 @@ partition_to_var (var_map map, int i) /* Given ssa_name VERSION, if it has a partition in MAP, return the var it is associated with. Otherwise return NULL. */ -static inline tree version_to_var (var_map map, int version) +static inline tree +version_to_var (var_map map, int version) { int part; part = partition_find (map->var_partition, version); - if (map->partition_to_compact) - part = map->partition_to_compact[part]; + if (map->partition_to_view) + part = map->partition_to_view[part]; if (part == NO_PARTITION) return NULL_TREE; @@ -125,8 +153,8 @@ var_to_partition (var_map map, tree var) if (TREE_CODE (var) == SSA_NAME) { part = partition_find (map->var_partition, SSA_NAME_VERSION (var)); - if (map->partition_to_compact) - part = map->partition_to_compact[part]; + if (map->partition_to_view) + part = map->partition_to_view[part]; } else { @@ -155,9 +183,29 @@ var_to_partition_to_var (var_map map, tree var) } -/* This routine registers a partition for SSA_VAR with MAP. IS_USE is used - to count references. Any unregistered partitions may be compacted out - later. */ +/* Return the index into the basevar table for PARTITION's base in MAP. */ + +static inline int +basevar_index (var_map map, int partition) +{ + gcc_assert (partition >= 0 + && partition <= (int) num_var_partitions (map)); + return map->partition_to_base_index[partition]; +} + + +/* Return the number of different base variables in MAP. */ + +static inline int +num_basevars (var_map map) +{ + return map->num_basevars; +} + + + +/* This routine registers a partition for SSA_VAR with MAP. Any unregistered + partitions may be filtered out by a view later. */ static inline void register_ssa_partition (var_map map, tree ssa_var) @@ -170,7 +218,7 @@ register_ssa_partition (var_map map, tree ssa_var) version = SSA_NAME_VERSION (ssa_var); if (map->partition_to_var[version] == NULL_TREE) - map->partition_to_var[SSA_NAME_VERSION (ssa_var)] = ssa_var; + map->partition_to_var[version] = ssa_var; } @@ -238,13 +286,6 @@ extern void delete_tree_live_info (tree_live_info_p); #define LIVEDUMP_ALL (LIVEDUMP_ENTRY | LIVEDUMP_EXIT) extern void dump_live_info (FILE *, tree_live_info_p, int); -static inline int partition_is_global (tree_live_info_p, int); -static inline bitmap live_on_entry (tree_live_info_p, basic_block); -static inline bitmap live_on_exit (tree_live_info_p, basic_block); -static inline var_map live_var_map (tree_live_info_p); -static inline void live_merge_and_clear (tree_live_info_p, int, int); -static inline void make_live_on_entry (tree_live_info_p, basic_block, int); - /* Return TRUE if P is marked as a global in LIVE. */ @@ -316,275 +357,9 @@ make_live_on_entry (tree_live_info_p live, basic_block bb , int p) } -/* A tree_partition_associator (TPA)object is a base structure which allows - partitions to be associated with a tree object. - - A varray of tree elements represent each distinct tree item. - A parallel int array represents the first partition number associated with - the tree. - This partition number is then used as in index into the next_partition - array, which returns the index of the next partition which is associated - with the tree. TPA_NONE indicates the end of the list. - A varray paralleling the partition list 'partition_to_tree_map' is used - to indicate which tree index the partition is in. */ - -typedef struct tree_partition_associator_d -{ - VEC(tree,heap) *trees; - VEC(int,heap) *first_partition; - int *next_partition; - int *partition_to_tree_map; - int num_trees; - int uncompressed_num; - var_map map; -} *tpa_p; - -/* Value returned when there are no more partitions associated with a tree. */ -#define TPA_NONE -1 - -static inline tree tpa_tree (tpa_p, int); -static inline int tpa_first_partition (tpa_p, int); -static inline int tpa_next_partition (tpa_p, int); -static inline int tpa_num_trees (tpa_p); -static inline int tpa_find_tree (tpa_p, int); -static inline void tpa_decompact (tpa_p); -extern void tpa_delete (tpa_p); -extern void tpa_dump (FILE *, tpa_p); -extern void tpa_remove_partition (tpa_p, int, int); -extern int tpa_compact (tpa_p); - - -/* Return the number of distinct tree nodes in TPA. */ - -static inline int -tpa_num_trees (tpa_p tpa) -{ - return tpa->num_trees; -} - - -/* Return the tree node for index I in TPA. */ - -static inline tree -tpa_tree (tpa_p tpa, int i) -{ - return VEC_index (tree, tpa->trees, i); -} - - -/* Return the first partition associated with tree list I in TPA. */ - -static inline int -tpa_first_partition (tpa_p tpa, int i) -{ - return VEC_index (int, tpa->first_partition, i); -} - - -/* Return the next partition after partition I in TPA's list. */ - -static inline int -tpa_next_partition (tpa_p tpa, int i) -{ - return tpa->next_partition[i]; -} - - -/* Return the tree index from TPA whose list contains partition I. - TPA_NONE is returned if I is not associated with any list. */ - -static inline int -tpa_find_tree (tpa_p tpa, int i) -{ - int index; - - index = tpa->partition_to_tree_map[i]; - /* When compressed, any index higher than the number of tree elements is - a compressed element, so return TPA_NONE. */ - if (index != TPA_NONE && index >= tpa_num_trees (tpa)) - { - gcc_assert (tpa->uncompressed_num != -1); - index = TPA_NONE; - } - - return index; -} - - -/* This function removes any compaction which was performed on TPA. */ - -static inline void -tpa_decompact(tpa_p tpa) -{ - gcc_assert (tpa->uncompressed_num != -1); - tpa->num_trees = tpa->uncompressed_num; -} - - -/* Once a var_map has been created and compressed, a complementary root_var - object can be built. This creates a list of all the root variables from - which ssa version names are derived. Each root variable has a list of - which partitions are versions of that root. - - This is implemented using the tree_partition_associator. - - The tree vector is used to represent the root variable. - The list of partitions represent SSA versions of the root variable. */ - -typedef tpa_p root_var_p; - -static inline tree root_var (root_var_p, int); -static inline int root_var_first_partition (root_var_p, int); -static inline int root_var_next_partition (root_var_p, int); -static inline int root_var_num (root_var_p); -static inline void root_var_dump (FILE *, root_var_p); -static inline void root_var_remove_partition (root_var_p, int, int); -static inline void root_var_delete (root_var_p); -static inline int root_var_find (root_var_p, int); -static inline int root_var_compact (root_var_p); -static inline void root_var_decompact (tpa_p); - -extern root_var_p root_var_init (var_map); - -/* Value returned when there are no more partitions associated with a root - variable. */ -#define ROOT_VAR_NONE TPA_NONE - - -/* Return the number of distinct root variables in RV. */ - -static inline int -root_var_num (root_var_p rv) -{ - return tpa_num_trees (rv); -} - - -/* Return root variable I from RV. */ - -static inline tree -root_var (root_var_p rv, int i) -{ - return tpa_tree (rv, i); -} - - -/* Return the first partition in RV belonging to root variable list I. */ - -static inline int -root_var_first_partition (root_var_p rv, int i) -{ - return tpa_first_partition (rv, i); -} - - -/* Return the next partition after partition I in a root list from RV. */ - -static inline int -root_var_next_partition (root_var_p rv, int i) -{ - return tpa_next_partition (rv, i); -} - - -/* Send debug info for root_var list RV to file F. */ - -static inline void -root_var_dump (FILE *f, root_var_p rv) -{ - fprintf (f, "\nRoot Var dump\n"); - tpa_dump (f, rv); - fprintf (f, "\n"); -} - +/* From tree-ssa-coalesce.c */ +extern var_map coalesce_ssa_name (void); -/* Destroy root_var object RV. */ - -static inline void -root_var_delete (root_var_p rv) -{ - tpa_delete (rv); -} - - -/* Remove partition PARTITION_INDEX from root_var list ROOT_INDEX in RV. */ - -static inline void -root_var_remove_partition (root_var_p rv, int root_index, int partition_index) -{ - tpa_remove_partition (rv, root_index, partition_index); -} - - -/* Return the root_var list index for partition I in RV. */ - -static inline int -root_var_find (root_var_p rv, int i) -{ - return tpa_find_tree (rv, i); -} - - -/* Hide single element lists in RV. */ - -static inline int -root_var_compact (root_var_p rv) -{ - return tpa_compact (rv); -} - - -/* Expose the single element lists in RV. */ - -static inline void -root_var_decompact (root_var_p rv) -{ - tpa_decompact (rv); -} - - -/* This set of routines implements a coalesce_list. This is an object which - is used to track pairs of partitions which are desirable to coalesce - together at some point. Costs are associated with each pair, and when - all desired information has been collected, the object can be used to - order the pairs for processing. */ - -/* This structure defines a pair entry. */ - -typedef struct partition_pair -{ - int first_partition; - int second_partition; - int cost; -} * partition_pair_p; - -extern unsigned int partition_pair_map_hash (const void *); -extern int partition_pair_map_eq (const void *, const void *); - -/* This structure maintains the list of coalesce pairs. */ - -typedef struct coalesce_list_d -{ - var_map map; - htab_t list; - partition_pair_p *sorted; - int num_sorted; - bool add_mode; -} *coalesce_list_p; - -extern coalesce_list_p create_coalesce_list (var_map); -extern void add_coalesce (coalesce_list_p, int, int, int); -extern int coalesce_cost (int, bool, bool); -extern void sort_coalesce_list (coalesce_list_p); -extern void dump_coalesce_list (FILE *, coalesce_list_p); -extern void delete_coalesce_list (coalesce_list_p); - -#define NO_BEST_COALESCE -1 - -extern conflict_graph build_tree_conflict_graph (tree_live_info_p, tpa_p, - coalesce_list_p); -extern void coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map, - coalesce_list_p cl, FILE *); /* From tree-ssa-ter.c */ extern tree *find_replaceable_exprs (var_map); diff --git a/gcc/tree-ssa-ter.c b/gcc/tree-ssa-ter.c index 2bd58cc38f2..78f8a121f09 100644 --- a/gcc/tree-ssa-ter.c +++ b/gcc/tree-ssa-ter.c @@ -25,29 +25,11 @@ Boston, MA 02110-1301, USA. */ #include "coretypes.h" #include "tm.h" #include "tree.h" -#include "flags.h" -#include "rtl.h" -#include "tm_p.h" -#include "ggc.h" -#include "langhooks.h" -#include "hard-reg-set.h" -#include "basic-block.h" -#include "output.h" -#include "expr.h" -#include "function.h" #include "diagnostic.h" #include "bitmap.h" #include "tree-flow.h" -#include "tree-gimple.h" -#include "tree-inline.h" -#include "varray.h" -#include "timevar.h" -#include "hashtab.h" #include "tree-dump.h" #include "tree-ssa-live.h" -#include "tree-pass.h" -#include "toplev.h" -#include "vecprim.h" /* Temporary Expression Replacement (TER) |