/* Routines for liveness in SSA trees.
- Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005, 2007, 2008 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)
+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,
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
+<http://www.gnu.org/licenses/>. */
#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 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
+/* 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;
- }
+ gcc_assert (TREE_CODE (var) == SSA_NAME);
+ part = partition_find (map->var_partition, SSA_NAME_VERSION (var));
+ if (map->partition_to_view)
+ part = map->partition_to_view[part];
return part;
}
}
-/* 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)
+{
+ 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)
{
- int version;
+ 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
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.
-
+
----------------------------------------------------------------------- */
/* 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. */
}
-/* 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_assert (bb != ENTRY_BLOCK_PTR);
+ gcc_assert (bb != EXIT_BLOCK_PTR);
+
+ return live->livein[bb->index];
}
/* 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;
/* 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_assert (live->livein[p1]);
+ gcc_assert (live->livein[p2]);
bitmap_ior_into (live->livein[p1], live->livein[p2]);
bitmap_zero (live->livein[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 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. */
+/* From tree-ssa-coalesce.c */
+extern var_map coalesce_ssa_name (void);
-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);
-}
-
-
-/* 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 bitmap find_replaceable_exprs (var_map);
+extern void dump_replaceable_exprs (FILE *, bitmap);
#endif /* _TREE_SSA_LIVE_H */
OSDN Git Service
