X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-ssa-live.h;h=8158577eaab577900b2428481c9091b577522c7c;hb=bb86bcdff1719073969ec745e24ebd4e1dbd1a80;hp=ee6ee4c4b76f6269e5e186becf237083e8d675d3;hpb=73b04688db0c71affd8ed35e5bb0ebc60458e631;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-ssa-live.h b/gcc/tree-ssa-live.h index ee6ee4c4b76..8158577eaab 100644 --- a/gcc/tree-ssa-live.h +++ b/gcc/tree-ssa-live.h @@ -1,12 +1,13 @@ /* Routines for liveness in SSA trees. - Copyright (C) 2003, 2004 Free Software Foundation, Inc. + Copyright (C) 2003, 2004, 2005, 2007, 2008, 2010 + Free Software Foundation, Inc. Contributed by Andrew MacLeod 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) +the Free Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, @@ -15,72 +16,87 @@ 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, 59 Temple Place - Suite 330, -Boston, MA 02111-1307, USA. */ +along with GCC; see the file COPYING3. If not see +. */ #ifndef _TREE_SSA_LIVE_H #define _TREE_SSA_LIVE_H 1 #include "partition.h" +#include "vecprim.h" + + + +/* 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 partition can also be represented + by a non-ssa_name variable. This allows ssa_names and their 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 doesn't change anything) + + The final component of the data structure is the basevar map. This provides + a list of all the different base variables which occur 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. */ -/* Used to create the variable mapping when we go out of SSA form. */ 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; - - /* Mapping of partition numbers to vars. */ - tree *partition_to_var; + /* Vector for managing partitions views. */ + int *partition_to_view; + int *view_to_partition; - /* 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; - /* Reference count, if required. */ - int *ref_count; + /* 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 +/* Index to 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 tree make_ssa_temp (tree); +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 int version_ref_count (var_map, tree); -static inline void register_ssa_partition (var_map, tree, bool); - -#define SSA_VAR_MAP_REF_COUNT 0x01 -extern var_map create_ssa_var_map (int); -/* Number of partitions in MAP. */ +/* Return number of partitions in MAP. */ static inline unsigned num_var_partitions (var_map map) @@ -89,69 +105,49 @@ num_var_partitions (var_map map) } -/* Return the reference count for SSA_VAR's partition in MAP. */ - -static inline int -version_ref_count (var_map map, tree ssa_var) -{ - int version = SSA_NAME_VERSION (ssa_var); - gcc_assert (map->ref_count); - return map->ref_count[version]; -} - - -/* Given partition index I from MAP, return the variable which represents that +/* Given partition index I from MAP, return the variable which represents that partition. */ - + static inline tree partition_to_var (var_map map, int i) { - if (map->compact_to_partition) - i = map->compact_to_partition[i]; + tree name; + if (map->view_to_partition) + i = map->view_to_partition[i]; i = partition_find (map->var_partition, i); - return map->partition_to_var[i]; + name = ssa_name (i); + return name; } -/* Given ssa_name VERSION, if it has a partition in MAP, return the var it +/* 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; - + return partition_to_var (map, part); } - -/* Given VAR, return the partition number in MAP which contains it. + +/* Given VAR, return the partition number in MAP which contains it. NO_PARTITION is returned if it's not in any partition. */ static inline int var_to_partition (var_map map, tree var) { - var_ann_t ann; int part; - 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]; - } - else - { - ann = var_ann (var); - if (ann->out_of_ssa_tag) - part = VAR_ANN_PARTITION (ann); - else - part = NO_PARTITION; - } + part = partition_find (map->var_partition, SSA_NAME_VERSION (var)); + if (map->partition_to_view) + part = map->partition_to_view[part]; return part; } @@ -171,44 +167,56 @@ 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 void -register_ssa_partition (var_map map, tree ssa_var, bool is_use) +static inline int +basevar_index (var_map map, int partition) { - int version; + gcc_checking_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 ATTRIBUTE_UNUSED, + tree ssa_var ATTRIBUTE_UNUSED) +{ #if defined ENABLE_CHECKING register_ssa_partition_check (ssa_var); #endif - - version = SSA_NAME_VERSION (ssa_var); - if (is_use && map->ref_count) - map->ref_count[version]++; - - if (map->partition_to_var[version] == NULL_TREE) - map->partition_to_var[SSA_NAME_VERSION (ssa_var)] = ssa_var; } -/* ---------------- live on entry/exit info ------------------------------ +/* ---------------- live on entry/exit info ------------------------------ This structure is used to represent live range information on SSA based trees. A partition map must be provided, and based on the active partitions, live-on-entry information and live-on-exit information can be calculated. - As well, partitions are marked as to whether they are global (live + As well, partitions are marked as to whether they are global (live outside the basic block they are defined in). - The live-on-entry information is per variable. It provide a bitmap for - each variable which has a bit set for each basic block that the variable - is live on entry to that block. + The live-on-entry information is per block. It provide a bitmap for + each block which has a bit set for each partition that is live on entry to + that block. - The live-on-exit information is per block. It provides a bitmap for each + The live-on-exit information is per block. It provides a bitmap for each block indicating which partitions are live on exit from the block. - For the purposes of this implementation, we treat the elements of a PHI + For the purposes of this implementation, we treat the elements of a PHI as follows: Uses in a PHI are considered LIVE-ON-EXIT to the block from which they @@ -217,9 +225,9 @@ register_ssa_partition (var_map map, tree ssa_var, bool is_use) The Def of a PHI node is *not* considered live on entry to the block. It is considered to be "define early" in the block. Picture it as each - block having a stmt (or block-preheader) before the first real stmt in + block having a stmt (or block-preheader) before the first real stmt in the block which defines all the variables that are defined by PHIs. - + ----------------------------------------------------------------------- */ @@ -237,12 +245,18 @@ typedef struct tree_live_info_d /* Number of basic blocks when live on exit calculated. */ int num_blocks; + /* Vector used when creating live ranges as a visited stack. */ + int *work_stack; + + /* Top of workstack. */ + int *stack_top; + /* Bitmap of what variables are live on exit for a basic blocks. */ bitmap *liveout; } *tree_live_info_p; -extern tree_live_info_p calculate_live_on_entry (var_map); +extern tree_live_info_p calculate_live_ranges (var_map); extern void calculate_live_on_exit (tree_live_info_p); extern void delete_tree_live_info (tree_live_info_p); @@ -251,32 +265,28 @@ 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_entry_blocks (tree_live_info_p, int); -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. */ static inline int partition_is_global (tree_live_info_p live, int p) { - gcc_assert (live->global); + gcc_checking_assert (live->global); return bitmap_bit_p (live->global, p); } -/* Return the bitmap from LIVE representing the live on entry blocks for +/* Return the bitmap from LIVE representing the live on entry blocks for partition P. */ static inline bitmap -live_entry_blocks (tree_live_info_p live, int p) +live_on_entry (tree_live_info_p live, basic_block bb) { - gcc_assert (live->livein); - return live->livein[p]; + gcc_checking_assert (live->livein + && bb != ENTRY_BLOCK_PTR + && bb != EXIT_BLOCK_PTR); + + return live->livein[bb->index]; } @@ -286,9 +296,9 @@ live_entry_blocks (tree_live_info_p live, int p) static inline bitmap live_on_exit (tree_live_info_p live, basic_block bb) { - gcc_assert (live->liveout); - gcc_assert (bb != ENTRY_BLOCK_PTR); - gcc_assert (bb != EXIT_BLOCK_PTR); + gcc_checking_assert (live->liveout + && bb != ENTRY_BLOCK_PTR + && bb != EXIT_BLOCK_PTR); return live->liveout[bb->index]; } @@ -296,7 +306,7 @@ live_on_exit (tree_live_info_p live, basic_block bb) /* Return the partition map which the information in LIVE utilizes. */ -static inline var_map +static inline var_map live_var_map (tree_live_info_p live) { return live->map; @@ -306,9 +316,10 @@ live_var_map (tree_live_info_p live) /* Merge the live on entry information in LIVE for partitions P1 and P2. Place the result into P1. Clear P2. */ -static inline void +static inline void live_merge_and_clear (tree_live_info_p live, int p1, int p2) { + gcc_checking_assert (live->livein[p1] && live->livein[p2]); bitmap_ior_into (live->livein[p1], live->livein[p2]); bitmap_zero (live->livein[p2]); } @@ -316,403 +327,21 @@ live_merge_and_clear (tree_live_info_p live, int p1, int p2) /* Mark partition P as live on entry to basic block BB in LIVE. */ -static inline void +static inline void make_live_on_entry (tree_live_info_p live, basic_block bb , int p) { - bitmap_set_bit (live->livein[p], bb->index); + bitmap_set_bit (live->livein[bb->index], p); bitmap_set_bit (live->global, 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 -{ - varray_type trees; - varray_type 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 tpa_p tpa_init (var_map); -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 VARRAY_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 VARRAY_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 complimentary 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"); -} - - -/* 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); -} - - -/* A TYPE_VAR object is similar to a root_var object, except this associates - partitions with their type rather than their root variable. This is used to - coalesce memory locations based on type. */ - -typedef tpa_p type_var_p; - -static inline tree type_var (type_var_p, int); -static inline int type_var_first_partition (type_var_p, int); -static inline int type_var_next_partition (type_var_p, int); -static inline int type_var_num (type_var_p); -static inline void type_var_dump (FILE *, type_var_p); -static inline void type_var_remove_partition (type_var_p, int, int); -static inline void type_var_delete (type_var_p); -static inline int type_var_find (type_var_p, int); -static inline int type_var_compact (type_var_p); -static inline void type_var_decompact (type_var_p); - -extern type_var_p type_var_init (var_map); - -/* Value returned when there is no partitions associated with a list. */ -#define TYPE_VAR_NONE TPA_NONE - - -/* Return the number of distinct type lists in TV. */ - -static inline int -type_var_num (type_var_p tv) -{ - return tpa_num_trees (tv); -} - - -/* Return the type of list I in TV. */ - -static inline tree -type_var (type_var_p tv, int i) -{ - return tpa_tree (tv, i); -} - - -/* Return the first partition belonging to type list I in TV. */ - -static inline int -type_var_first_partition (type_var_p tv, int i) -{ - return tpa_first_partition (tv, i); -} - - -/* Return the next partition after partition I in a type list within TV. */ - -static inline int -type_var_next_partition (type_var_p tv, int i) -{ - return tpa_next_partition (tv, i); -} - - -/* Send debug info for type_var object TV to file F. */ - -static inline void -type_var_dump (FILE *f, type_var_p tv) -{ - fprintf (f, "\nType Var dump\n"); - tpa_dump (f, tv); - fprintf (f, "\n"); -} - - -/* Delete type_var object TV. */ - -static inline void -type_var_delete (type_var_p tv) -{ - tpa_delete (tv); -} +/* From tree-ssa-coalesce.c */ +extern var_map coalesce_ssa_name (void); -/* Remove partition PARTITION_INDEX from type list TYPE_INDEX in TV. */ - -static inline void -type_var_remove_partition (type_var_p tv, int type_index, int partition_index) -{ - tpa_remove_partition (tv, type_index, partition_index); -} - - -/* Return the type index in TV for the list partition I is in. */ - -static inline int -type_var_find (type_var_p tv, int i) -{ - return tpa_find_tree (tv, i); -} - - -/* Hide single element lists in TV. */ - -static inline int -type_var_compact (type_var_p tv) -{ - return tpa_compact (tv); -} - - -/* Expose single element lists in TV. */ - -static inline void -type_var_decompact (type_var_p tv) -{ - tpa_decompact (tv); -} - -/* 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 for coalescing. */ - -typedef struct partition_pair_d -{ - int first_partition; - int second_partition; - int cost; - struct partition_pair_d *next; -} *partition_pair_p; - -/* This structure maintains the list of coalesce pairs. - When add_mode is true, list is a triangular shaped list of coalesce pairs. - The smaller partition number is used to index the list, and the larger is - index is located in a partition_pair_p object. These lists are sorted from - smallest to largest by 'second_partition'. New coalesce pairs are allowed - to be added in this mode. - When add_mode is false, the lists have all been merged into list[0]. The - rest of the lists are not used. list[0] is ordered from most desirable - coalesce to least desirable. pop_best_coalesce() retrieves the pairs - one at a time. */ - -typedef struct coalesce_list_d -{ - var_map map; - partition_pair_p *list; - 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 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 int pop_best_coalesce (coalesce_list_p, int *, int *); - -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 bitmap find_replaceable_exprs (var_map); +extern void dump_replaceable_exprs (FILE *, bitmap); #endif /* _TREE_SSA_LIVE_H */