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. */
+the Free Software Foundation, 51 Franklin Street, Fifth Floor,
+Boston, MA 02110-1301, USA. */
#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;
+ /* 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;
- /* 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
+/* 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 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)
}
-/* 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
partition. */
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];
}
/* 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;
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
{
ann = var_ann (var);
- if (ann->out_of_ssa_tag)
+ if (ann && ann->out_of_ssa_tag)
part = VAR_ANN_PARTITION (ann);
else
part = NO_PARTITION;
}
-/* 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, bool is_use)
+register_ssa_partition (var_map map, tree ssa_var)
{
int version;
#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;
+ map->partition_to_var[version] = ssa_var;
}
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
/* 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);
#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. */
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_assert (bb != ENTRY_BLOCK_PTR);
+ gcc_assert (bb != EXIT_BLOCK_PTR);
+
+ return live->livein[bb->index];
}
static inline void
live_merge_and_clear (tree_live_info_p live, int p1, int p2)
{
+ gcc_assert (live->livein[p1]);
+ gcc_assert (live->livein[p2]);
bitmap_ior_into (live->livein[p1], live->livein[p2]);
bitmap_zero (live->livein[p2]);
}
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 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 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");
-}
-
-
-/* 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 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);
+extern void dump_replaceable_exprs (FILE *, tree *);
#endif /* _TREE_SSA_LIVE_H */