diff options
Diffstat (limited to 'gcc/tree-ssa-live.c')
| -rw-r--r-- | gcc/tree-ssa-live.c | 1912 |
1 files changed, 1912 insertions, 0 deletions
diff --git a/gcc/tree-ssa-live.c b/gcc/tree-ssa-live.c new file mode 100644 index 00000000000..931ec780279 --- /dev/null +++ b/gcc/tree-ssa-live.c @@ -0,0 +1,1912 @@ +/* Liveness for SSA trees. + Copyright (C) 2003 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, 59 Temple Place - Suite 330, +Boston, MA 02111-1307, USA. */ + +#include "config.h" +#include "system.h" +#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-simple.h" +#include "tree-inline.h" +#include "varray.h" +#include "timevar.h" +#include "tree-alias-common.h" +#include "hashtab.h" +#include "tree-dump.h" +#include "tree-ssa-live.h" + +static void live_worklist (tree_live_info_p, varray_type, int); +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_livein_if_notdef (tree_live_info_p, bitmap, + tree, basic_block); +static inline void register_ssa_partition (var_map, tree, bool); +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); + +/* 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. + + 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. */ + +/* Create a variable partition map of SIZE, initialize and return it. */ + +var_map +init_var_map (int size) +{ + var_map map; + + map = (var_map) xmalloc (sizeof (struct _var_map)); + map->var_partition = partition_new (size); + map->partition_to_var + = (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->num_partitions = size; + map->partition_size = size; + map->ref_count = NULL; + return map; +} + + +/* Free memory associated with MAP. */ + +void +delete_var_map (var_map 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->ref_count) + free (map->ref_count); + free (map); +} + + +/* This function will combine the partitions in MAP for VAR1 and VAR2. It + Returns the partition which represents the new partition. If the two + partitions cannot be combined, NO_PARTITION is returned. */ + +int +var_union (var_map map, tree var1, tree var2) +{ + int p1, p2, p3; + tree root_var = NULL_TREE; + tree other_var = NULL_TREE; + + /* This is independent of partition_to_compact. If partition_to_compact is + on, then whichever one of these partitions is absorbed will never have a + dereference into the partition_to_compact 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]; + root_var = var1; + } + + if (TREE_CODE (var2) == SSA_NAME) + p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2)); + else + { + p2 = var_to_partition (map, var2); + if (map->compact_to_partition) + p2 = map->compact_to_partition[p2]; + + /* If there is no root_var set, or its not a user variable, set the + root_var to this one. */ + if (!root_var || is_gimple_tmp_var (root_var)) + { + other_var = root_var; + root_var = var2; + } + else + other_var = var2; + } + + if (p1 == NO_PARTITION || p2 == NO_PARTITION) + abort (); + + if (p1 == p2) + p3 = p1; + else + p3 = partition_union (map->var_partition, p1, p2); + + if (map->partition_to_compact) + p3 = map->partition_to_compact[p3]; + + if (root_var) + change_partition_var (map, root_var, p3); + if (other_var) + change_partition_var (map, other_var, p3); + + 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. + + This is implemented such that compaction doesn't affect partitioning. + Ie., once partitions are created and possibly merged, running one + or more different kind of compaction will not affect the partitions + themselves. Their index might change, but all the same variables will + still be members of the same partition group. This allows work on reduced + sets, and no loss of information when a larger set is later desired. + + In particular, coalescing can work on partitions which have 2 or more + 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) +{ + sbitmap used; + int x, limit, count, tmp, root, root_i; + tree var; + root_var_p rv = NULL; + + limit = map->partition_size; + used = sbitmap_alloc (limit); + sbitmap_zero (used); + + /* Already compressed? Abandon the old one. */ + if (map->partition_to_compact) + { + free (map->partition_to_compact); + map->partition_to_compact = NULL; + } + if (map->compact_to_partition) + { + free (map->compact_to_partition); + map->compact_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++) + { + 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++; + } + } + + /* Build a compacted partitioning. */ + if (count != limit) + { + 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, + { + map->partition_to_compact[x] = count; + map->compact_to_partition[count] = x; + var = map->partition_to_var[x]; + if (TREE_CODE (var) != SSA_NAME) + change_partition_var (map, var, count); + count++; + }); + } + else + { + free (map->partition_to_compact); + map->partition_to_compact = NULL; + } + + map->num_partitions = count; + + if (rv) + root_var_delete (rv); + sbitmap_free (used); +} + + +/* 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. */ + +void +change_partition_var (var_map map, tree var, int part) +{ + var_ann_t ann; + + if (TREE_CODE (var) == SSA_NAME) + abort(); + + 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; +} + + +/* 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 (int flags) +{ + block_stmt_iterator bsi; + basic_block bb; + tree *dest, *use; + tree stmt; + stmt_ann_t ann; + vuse_optype vuses; + vdef_optype vdefs; + use_optype uses; + def_optype defs; + unsigned x; + var_map map; +#if defined ENABLE_CHECKING + sbitmap used_in_real_ops; + sbitmap used_in_virtual_ops; +#endif + + map = init_var_map (highest_ssa_version + 1); + +#if defined ENABLE_CHECKING + used_in_real_ops = sbitmap_alloc (num_referenced_vars); + sbitmap_zero (used_in_real_ops); + + used_in_virtual_ops = sbitmap_alloc (num_referenced_vars); + sbitmap_zero (used_in_virtual_ops); +#endif + + if (flags & SSA_VAR_MAP_REF_COUNT) + { + map->ref_count + = (int *)xmalloc (((highest_ssa_version + 1) * sizeof (int))); + memset (map->ref_count, 0, (highest_ssa_version + 1) * sizeof (int)); + } + + FOR_EACH_BB (bb) + { + tree phi, arg; + for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) + { + int i; + register_ssa_partition (map, PHI_RESULT (phi), false); + 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, true); + } + } + + for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) + { + stmt = bsi_stmt (bsi); + get_stmt_operands (stmt); + ann = stmt_ann (stmt); + + /* Register USE and DEF operands in each statement. */ + uses = USE_OPS (ann); + for (x = 0; x < NUM_USES (uses); x++) + { + use = USE_OP_PTR (uses, x); + register_ssa_partition (map, *use, true); + +#if defined ENABLE_CHECKING + SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (*use))->uid); +#endif + } + + defs = DEF_OPS (ann); + for (x = 0; x < NUM_DEFS (defs); x++) + { + dest = DEF_OP_PTR (defs, x); + register_ssa_partition (map, *dest, false); + +#if defined ENABLE_CHECKING + SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (*dest))->uid); +#endif + } + + /* While we do not care about virtual operands for + out of SSA, we do need to look at them to make sure + we mark all the variables which are used. */ + vuses = VUSE_OPS (ann); + for (x = 0; x < NUM_VUSES (vuses); x++) + { + tree var = VUSE_OP (vuses, x); + set_is_used (var); + +#if defined ENABLE_CHECKING + SET_BIT (used_in_virtual_ops, var_ann (SSA_NAME_VAR (var))->uid); +#endif + } + + vdefs = VDEF_OPS (ann); + for (x = 0; x < NUM_VDEFS (vdefs); x++) + { + tree var = VDEF_OP (vdefs, x); + set_is_used (var); + +#if defined ENABLE_CHECKING + SET_BIT (used_in_virtual_ops, var_ann (SSA_NAME_VAR (var))->uid); +#endif + } + } + } + +#if defined ENABLE_CHECKING + { + unsigned i; + sbitmap both = sbitmap_alloc (num_referenced_vars); + sbitmap_a_and_b (both, used_in_real_ops, used_in_virtual_ops); + if (sbitmap_first_set_bit (both) >= 0) + { + EXECUTE_IF_SET_IN_SBITMAP (both, 0, i, + fprintf (stderr, "Variable %s used in real and virtual operands\n", + get_name (referenced_var (i)))); + abort (); + } + + sbitmap_free (used_in_real_ops); + sbitmap_free (used_in_virtual_ops); + sbitmap_free (both); + } +#endif + + return map; +} + + +/* Allocate and return a new live range information object base on MAP. */ + +static tree_live_info_p +new_tree_live_info (var_map map) +{ + tree_live_info_p live; + int x; + + live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d)); + live->map = map; + live->num_blocks = last_basic_block; + + live->global = BITMAP_XMALLOC (); + + live->livein = (bitmap *)xmalloc (num_var_partitions (map) * sizeof (bitmap)); + for (x = 0; x < num_var_partitions (map); x++) + live->livein[x] = BITMAP_XMALLOC (); + + /* liveout is deferred until it is actually requested. */ + live->liveout = NULL; + return live; +} + + +/* Free storage for live range info object LIVE. */ + +void +delete_tree_live_info (tree_live_info_p live) +{ + int x; + if (live->liveout) + { + for (x = live->num_blocks - 1; x >= 0; x--) + BITMAP_XFREE (live->liveout[x]); + free (live->liveout); + } + if (live->livein) + { + for (x = num_var_partitions (live->map) - 1; x >= 0; x--) + BITMAP_XFREE (live->livein[x]); + free (live->livein); + } + if (live->global) + BITMAP_XFREE (live->global); + + free (live); +} + + +/* Using LIVE, fill in all the live-on-entry blocks between the defs and uses + for partition I. STACK is a varray used for temporary memory which is + passed in rather than being allocated on every call. */ + +static void +live_worklist (tree_live_info_p live, varray_type stack, int i) +{ + int b; + tree var; + basic_block def_bb = NULL; + edge e; + var_map map = live->map; + + var = partition_to_var (map, i); + if (SSA_NAME_DEF_STMT (var)) + def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var)); + + EXECUTE_IF_SET_IN_BITMAP (live->livein[i], 0, b, + { + VARRAY_PUSH_INT (stack, b); + }); + + while (VARRAY_ACTIVE_SIZE (stack) > 0) + { + b = VARRAY_TOP_INT (stack); + VARRAY_POP (stack); + + for (e = BASIC_BLOCK (b)->pred; e; e = e->pred_next) + if (e->src != ENTRY_BLOCK_PTR) + { + /* Its not live on entry to the block its defined in. */ + if (e->src == def_bb) + continue; + if (!bitmap_bit_p (live->livein[i], e->src->index)) + { + bitmap_set_bit (live->livein[i], e->src->index); + VARRAY_PUSH_INT (stack, e->src->index); + } + } + } +} + + +/* 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); +} + + +/* If VAR is in a partition and it isn't defined in DEF_VEC, set the livein and + global bit for it in the LIVE object. BB is the block being processed. */ + +static inline void +add_livein_if_notdef (tree_live_info_p live, bitmap def_vec, + tree var, basic_block bb) +{ + int p = var_to_partition (live->map, var); + if (p == NO_PARTITION || bb == ENTRY_BLOCK_PTR) + return; + if (!bitmap_bit_p (def_vec, p)) + { + bitmap_set_bit (live->livein[p], bb->index); + bitmap_set_bit (live->global, p); + } +} + + +/* Given partition map MAP, calculate all the live on entry bitmaps for + each basic block. Return a live info object. */ + +tree_live_info_p +calculate_live_on_entry (var_map map) +{ + tree_live_info_p live; + int num, i; + basic_block bb; + bitmap saw_def; + tree phi, var, stmt; + tree *vec; + edge e; + varray_type stack; + block_stmt_iterator bsi; + vuse_optype vuses; + vdef_optype vdefs; + use_optype uses; + def_optype defs; + stmt_ann_t ann; + + saw_def = BITMAP_XMALLOC (); + + live = new_tree_live_info (map); + + FOR_EACH_BB (bb) + { + bitmap_clear (saw_def); + + for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) + { + for (i = 0; i < PHI_NUM_ARGS (phi); i++) + { + var = PHI_ARG_DEF (phi, i); + if (!phi_ssa_name_p (var)) + continue; + stmt = SSA_NAME_DEF_STMT (var); + e = PHI_ARG_EDGE (phi, i); + + /* Any uses in PHIs which either don't have def's or are not + defined in the block from which the def comes, will be live + on entry to that block. */ + if (!stmt || e->src != bb_for_stmt (stmt)) + add_livein_if_notdef (live, saw_def, var, e->src); + } + } + + /* Don't mark PHI results as defined until all the PHI nodes have + been processed. If the PHI sequence is: + a_3 = PHI <a_1, a_2> + b_3 = PHI <b_1, a_3> + The a_3 referred to in b_3's PHI node is the one incoming on the + edge, *not* the PHI node just seen. */ + + for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) + { + var = PHI_RESULT (phi); + set_if_valid (map, saw_def, var); + } + + for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) + { + stmt = bsi_stmt (bsi); + get_stmt_operands (stmt); + ann = stmt_ann (stmt); + + uses = USE_OPS (ann); + num = NUM_USES (uses); + for (i = 0; i < num; i++) + { + vec = USE_OP_PTR (uses, i); + add_livein_if_notdef (live, saw_def, *vec, bb); + } + + vuses = VUSE_OPS (ann); + num = NUM_VUSES (vuses); + for (i = 0; i < num; i++) + { + var = VUSE_OP (vuses, i); + add_livein_if_notdef (live, saw_def, var, bb); + } + + vdefs = VDEF_OPS (ann); + num = NUM_VDEFS (vdefs); + for (i = 0; i < num; i++) + { + var = VDEF_OP (vdefs, i); + add_livein_if_notdef (live, saw_def, var, bb); + } + + defs = DEF_OPS (ann); + num = NUM_DEFS (defs); + for (i = 0; i < num; i++) + { + vec = DEF_OP_PTR (defs, i); + set_if_valid (map, saw_def, *vec); + } + + num = NUM_VDEFS (vdefs); + for (i = 0; i < num; i++) + { + var = VDEF_RESULT (vdefs, i); + set_if_valid (map, saw_def, var); + } + } + } + + VARRAY_INT_INIT (stack, last_basic_block, "stack"); + EXECUTE_IF_SET_IN_BITMAP (live->global, 0, i, + { + live_worklist (live, stack, i); + }); + +#ifdef ENABLE_CHECKING + /* 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 (e = bb->succ; e; e = e->succ_next) + { + int entry_block = e->dest->index; + if (e->dest == EXIT_BLOCK_PTR) + continue; + for (i = 0; i < num_var_partitions (map); i++) + { + basic_block tmp; + tree d; + var = partition_to_var (map, i); + stmt = SSA_NAME_DEF_STMT (var); + tmp = bb_for_stmt (stmt); + d = default_def (SSA_NAME_VAR (var)); + + if (bitmap_bit_p (live_entry_blocks (live, i), entry_block)) + { + if (!IS_EMPTY_STMT (stmt)) + { + num++; + print_generic_expr (stderr, var, TDF_SLIM); + fprintf (stderr, " is defined "); + if (tmp) + fprintf (stderr, " in BB%d, ", tmp->index); + fprintf (stderr, "by:\n"); + print_generic_expr (stderr, stmt, TDF_SLIM); + fprintf (stderr, "\nIt is also live-on-entry to entry BB %d", + entry_block); + fprintf (stderr, " So it appears to have multiple defs.\n"); + } + else + { + if (d != var) + { + num++; + print_generic_expr (stderr, var, TDF_SLIM); + fprintf (stderr, " is live-on-entry to BB%d ",entry_block); + if (d) + { + fprintf (stderr, " but is not the default def of "); + print_generic_expr (stderr, d, TDF_SLIM); + fprintf (stderr, "\n"); + } + else + fprintf (stderr, " and there is no default def.\n"); + } + } + } + else + if (d == var) + { + /* The only way this var shouldn't be marked live on entry is + if it occurs in a PHI argument of the block. */ + int z, ok = 0; + for (phi = phi_nodes (e->dest); + phi && !ok; + phi = TREE_CHAIN (phi)) + { + for (z = 0; z < PHI_NUM_ARGS (phi); z++) + if (var == PHI_ARG_DEF (phi, z)) + { + ok = 1; + break; + } + } + if (ok) + continue; + num++; + print_generic_expr (stderr, var, TDF_SLIM); + fprintf (stderr, " is not marked live-on-entry to entry BB%d ", + entry_block); + fprintf (stderr, "but it is a default def so it should be.\n"); + } + } + } + if (num > 0) + abort (); +#endif + + return live; +} + + +/* Calculate the live on exit vectors based on the entry info in LIVEINFO. */ + +void +calculate_live_on_exit (tree_live_info_p liveinfo) +{ + unsigned b; + int i, x; + bitmap *on_exit; + basic_block bb; + edge e; + tree t, phi; + bitmap on_entry; + var_map map = liveinfo->map; + + on_exit = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap)); + for (x = 0; x < last_basic_block; x++) + on_exit[x] = BITMAP_XMALLOC (); + + /* Set all the live-on-exit bits for uses in PHIs. */ + FOR_EACH_BB (bb) + { + for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) + for (i = 0; i < PHI_NUM_ARGS (phi); i++) + { + t = PHI_ARG_DEF (phi, i); + e = PHI_ARG_EDGE (phi, i); + if (!phi_ssa_name_p (t) || e->src == ENTRY_BLOCK_PTR) + continue; + set_if_valid (map, on_exit[e->src->index], t); + } + } + + /* Set live on exit for all predecessors of live on entry's. */ + for (i = 0; i < num_var_partitions (map); i++) + { + on_entry = live_entry_blocks (liveinfo, i); + EXECUTE_IF_SET_IN_BITMAP (on_entry, 0, b, + { + for (e = BASIC_BLOCK(b)->pred; e; e = e->pred_next) + if (e->src != ENTRY_BLOCK_PTR) + bitmap_set_bit (on_exit[e->src->index], i); + }); + } + + liveinfo->liveout = on_exit; +} + + +/* Initialize a tree_partition_associator object using MAP. */ + +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)); + VARRAY_TREE_INIT (tpa->trees, x, "trees"); + VARRAY_INT_INIT (tpa->first_partition, x, "first_partition"); + + 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) + { + VARRAY_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; + + free (tpa->partition_to_tree_map); + free (tpa->next_partition); + free (tpa); +} + + +/* This function will remove any tree entires 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 = VARRAY_TREE (tpa->trees, last); + swap_i = VARRAY_INT (tpa->first_partition, last); + + /* Update the last entry. Since it is known to only have one + partition, there is nothing else to update. */ + VARRAY_TREE (tpa->trees, last) = VARRAY_TREE (tpa->trees, x); + VARRAY_INT (tpa->first_partition, last) + = VARRAY_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. */ + VARRAY_TREE (tpa->trees, x) = swap_t; + VARRAY_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); + +#ifdef ENABLE_CHECKING + if (p == NO_PARTITION) + abort (); +#endif + + /* 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] = VARRAY_INT (rv->first_partition, + VAR_ANN_ROOT_INDEX (ann)); + VARRAY_INT (rv->first_partition, VAR_ANN_ROOT_INDEX (ann)) = p; + } + else + { + ann->root_var_processed = 1; + VAR_ANN_ROOT_INDEX (ann) = rv->num_trees++; + VARRAY_PUSH_TREE (rv->trees, t); + VARRAY_PUSH_INT (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 = VARRAY_TREE (rv->trees, x); + var_ann (t)->root_var_processed = 0; + } + + sbitmap_free (seen); + return rv; +} + + +/* Initialize a type_var structure which associates all the partitions in MAP + of the same type to the type node's index. Volatiles are ignored. */ + +type_var_p +type_var_init (var_map map) +{ + type_var_p tv; + int x, y, p; + int num_partitions = num_var_partitions (map); + tree t; + sbitmap seen; + + seen = sbitmap_alloc (num_partitions); + sbitmap_zero (seen); + + tv = tpa_init (map); + if (!tv) + return NULL; + + for (x = num_partitions - 1; x >= 0; x--) + { + t = partition_to_var (map, x); + + /* Disallow coalescing of these types of variables. */ + if (!t + || TREE_THIS_VOLATILE (t) + || TREE_CODE (t) == RESULT_DECL + || TREE_CODE (t) == PARM_DECL + || (DECL_P (t) + && (DECL_REGISTER (t) + || !DECL_ARTIFICIAL (t) + || DECL_RTL_SET_P (t)))) + continue; + + p = var_to_partition (map, t); + +#ifdef ENABLE_CHECKING + if (p == NO_PARTITION) + abort (); +#endif + + /* If partitions have been coalesced, only add the representative + for the partition to the list once. */ + if (TEST_BIT (seen, p)) + continue; + SET_BIT (seen, p); + t = TREE_TYPE (t); + + /* Find the list for this type. */ + for (y = 0; y < tv->num_trees; y++) + if (t == VARRAY_TREE (tv->trees, y)) + break; + if (y == tv->num_trees) + { + tv->num_trees++; + VARRAY_PUSH_TREE (tv->trees, t); + VARRAY_PUSH_INT (tv->first_partition, p); + } + else + { + tv->next_partition[p] = VARRAY_INT (tv->first_partition, y); + VARRAY_INT (tv->first_partition, y) = p; + } + tv->partition_to_tree_map[p] = y; + } + sbitmap_free (seen); + return tv; +} + + +/* Create a new coalesce list object from MAP and return it. */ + +coalesce_list_p +create_coalesce_list (var_map map) +{ + coalesce_list_p list; + + list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d)); + + list->map = map; + list->add_mode = true; + list->list = (partition_pair_p *) xcalloc (num_var_partitions (map), + sizeof (struct partition_pair_d)); + return list; +} + + +/* Delete coalesce list CL. */ + +void +delete_coalesce_list (coalesce_list_p cl) +{ + free (cl->list); + 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) +{ + partition_pair_p node, tmp; + int s; + + /* Normalize so that p1 is the smaller value. */ + if (p2 < p1) + { + s = p1; + p1 = p2; + p2 = s; + } + + tmp = NULL; + + /* The list is sorted such that if we find a value greater than p2, + p2 is not in the list. */ + for (node = cl->list[p1]; node; node = node->next) + { + if (node->second_partition == p2) + return node; + else + if (node->second_partition > p2) + break; + tmp = node; + } + + if (!create) + return NULL; + + node = (partition_pair_p) xmalloc (sizeof (struct partition_pair_d)); + node->first_partition = p1; + node->second_partition = p2; + node->cost = 0; + + if (tmp != NULL) + { + node->next = tmp->next; + tmp->next = node; + } + else + { + /* This is now the first node in the list. */ + node->next = cl->list[p1]; + cl->list[p1] = node; + } + + return node; +} + + +/* 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; + +#ifdef ENABLE_CHECKING + if (!cl->add_mode) + abort(); +#endif + + 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 descending order. */ + +static +int compare_pairs (const void *p1, const void *p2) +{ + return (*(partition_pair_p *)p2)->cost - (*(partition_pair_p *)p1)->cost; +} + + +/* 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) +{ + int x, num, count; + partition_pair_p chain, p; + partition_pair_p *list; + + if (!cl->add_mode) + abort(); + + cl->add_mode = false; + + /* Compact the array of lists to a single list, and count the elements. */ + num = 0; + chain = NULL; + for (x = 0; x < num_var_partitions (cl->map); x++) + if (cl->list[x] != NULL) + { + for (p = cl->list[x]; p->next != NULL; p = p->next) + num++; + num++; + p->next = chain; + chain = cl->list[x]; + cl->list[x] = NULL; + } + + /* Only call qsort if there are more than 2 items. */ + if (num > 2) + { + list = xmalloc (sizeof (partition_pair_p) * num); + count = 0; + for (p = chain; p != NULL; p = p->next) + list[count++] = p; + +#ifdef ENABLE_CHECKING + if (count != num) + abort (); +#endif + + qsort (list, count, sizeof (partition_pair_p), compare_pairs); + + p = list[0]; + for (x = 1; x < num; x++) + { + p->next = list[x]; + p = list[x]; + } + p->next = NULL; + cl->list[0] = list[0]; + free (list); + } + else + { + cl->list[0] = chain; + if (num == 2) + { + /* Simply swap the two elements if they are in the wrong order. */ + if (chain->cost < chain->next->cost) + { + cl->list[0] = chain->next; + cl->list[0]->next = chain; + chain->next = NULL; + } + } + } +} + + +/* 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. */ + +int +pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2) +{ + partition_pair_p node; + int ret; + + if (cl->add_mode) + abort(); + + node = cl->list[0]; + if (!node) + return NO_BEST_COALESCE; + + cl->list[0] = node->next; + + *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); + } + } +} + + +/* 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; + int num, x, y, i; + basic_block bb; + varray_type partition_link, tpa_to_clear, tpa_nodes; + def_optype defs; + use_optype uses; + unsigned l; + + map = live_var_map (liveinfo); + graph = conflict_graph_new (num_var_partitions (map)); + + if (tpa_num_trees (tpa) == 0) + return graph; + + live = BITMAP_XMALLOC (); + + VARRAY_INT_INIT (partition_link, num_var_partitions (map) + 1, "part_link"); + VARRAY_INT_INIT (tpa_nodes, tpa_num_trees (tpa), "tpa nodes"); + VARRAY_INT_INIT (tpa_to_clear, 50, "tpa to clear"); + + FOR_EACH_BB (bb) + { + block_stmt_iterator bsi; + tree phi; + + /* 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); + stmt_ann_t ann; + + get_stmt_operands (stmt); + ann = stmt_ann (stmt); + + /* 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) == MODIFY_EXPR) + { + tree lhs = TREE_OPERAND (stmt, 0); + tree rhs = TREE_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, 1); + set_if_valid (map, live, rhs); + } + } + + if (!is_a_copy) + { + tree *var_p; + + defs = DEF_OPS (ann); + num = NUM_DEFS (defs); + for (x = 0; x < num; x++) + { + var_p = DEF_OP_PTR (defs, x); + add_conflicts_if_valid (tpa, graph, map, live, *var_p); + } + + uses = USE_OPS (ann); + num = NUM_USES (uses); + for (x = 0; x < num; x++) + { + var_p = USE_OP_PTR (uses, x); + set_if_valid (map, live, *var_p); + } + } + } + + /* 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 = TREE_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 non-zero + 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, + { + i = tpa_find_tree (tpa, x); + if (i != TPA_NONE) + { + int start = VARRAY_INT (tpa_nodes, i); + /* If start is 0, a new root reference list is being started. + Register it to be cleared. */ + if (!start) + VARRAY_PUSH_INT (tpa_to_clear, i); + + /* Add interferences to other tpa members seen. */ + for (y = start; y != 0; y = VARRAY_INT (partition_link, y)) + conflict_graph_add (graph, x, y - 1); + VARRAY_INT (tpa_nodes, i) = x + 1; + VARRAY_INT (partition_link, x + 1) = start; + } + }); + + /* Now clear the used tpa root references. */ + for (l = 0; l < VARRAY_ACTIVE_SIZE (tpa_to_clear); l++) + VARRAY_INT (tpa_nodes, VARRAY_INT (tpa_to_clear, l)) = 0; + VARRAY_POP_ALL (tpa_to_clear); + } + + BITMAP_XFREE (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; + int x, num; + tree var; + + if (cl->add_mode) + { + fprintf (f, "Coalesce List:\n"); + num = num_var_partitions (cl->map); + for (x = 0; x < num; x++) + { + node = cl->list[x]; + if (node) + { + fprintf (f, "["); + print_generic_expr (f, partition_to_var (cl->map, x), TDF_SLIM); + fprintf (f, "] - "); + for ( ; node; node = node->next) + { + var = partition_to_var (cl->map, node->second_partition); + print_generic_expr (f, var, TDF_SLIM); + fprintf (f, "(%1d), ", node->cost); + } + fprintf (f, "\n"); + } + } + } + else + { + fprintf (f, "Sorted Coalesce list:\n"); + for (node = cl->list[0]; node; node = node->next) + { + 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 +dump_var_map (FILE *f, var_map map) +{ + int t; + unsigned x, y; + int p; + + fprintf (f, "\nPartition map \n\n"); + + for (x = 0; x < map->num_partitions; x++) + { + if (map->compact_to_partition != NULL) + p = map->compact_to_partition[x]; + else + p = x; + + if (map->partition_to_var[p] == NULL_TREE) + continue; + + t = 0; + for (y = 1; y < highest_ssa_version; y++) + { + p = partition_find (map->var_partition, y); + if (map->partition_to_compact) + p = map->partition_to_compact[p]; + if (p == (int)x) + { + if (t++ == 0) + { + fprintf(f, "Partition %d (", x); + print_generic_expr (f, partition_to_var (map, p), TDF_SLIM); + fprintf (f, " - "); + } + fprintf (f, "%d ", y); + } + } + if (t != 0) + fprintf (f, ")\n"); + } + fprintf (f, "\n"); +} + + +/* Output live range info LIVE to file F, controlled by FLAG. */ + +void +dump_live_info (FILE *f, tree_live_info_p live, int flag) +{ + basic_block bb; + int i; + var_map map = live->map; + + if ((flag & LIVEDUMP_ENTRY) && live->livein) + { + FOR_EACH_BB (bb) + { + fprintf (f, "\nLive on entry to BB%d : ", bb->index); + for (i = 0; i < num_var_partitions (map); i++) + { + if (bitmap_bit_p (live_entry_blocks (live, i), bb->index)) + { + print_generic_expr (f, partition_to_var (map, i), TDF_SLIM); + fprintf (f, " "); + } + } + fprintf (f, "\n"); + } + } + + if ((flag & LIVEDUMP_EXIT) && live->liveout) + { + FOR_EACH_BB (bb) + { + fprintf (f, "\nLive on exit from BB%d : ", bb->index); + EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, + { + print_generic_expr (f, partition_to_var (map, i), TDF_SLIM); + fprintf (f, " "); + }); + fprintf (f, "\n"); + } + } +} + +/* Register partitions in MAP so that we can take VARS out of SSA form. + This requires a walk over all the PHI nodes and all the statements. */ + +void +register_ssa_partitions_for_vars (bitmap vars, var_map map) +{ + basic_block bb; + + if (bitmap_first_set_bit (vars) >= 0) + { + + /* Find every instance (SSA_NAME) of variables in VARs and + register a new partition for them. This requires examining + every statement and every PHI node once. */ + FOR_EACH_BB (bb) + { + block_stmt_iterator bsi; + tree next; + tree phi; + + /* Register partitions for SSA_NAMEs appearing in the PHI + nodes in this basic block. + + Note we delete PHI nodes in this loop if they are + associated with virtual vars which are going to be + renamed. */ + for (phi = phi_nodes (bb); phi; phi = next) + { + tree result = SSA_NAME_VAR (PHI_RESULT (phi)); + + next = TREE_CHAIN (phi); + if (bitmap_bit_p (vars, var_ann (result)->uid)) + { + if (! is_gimple_reg (result)) + remove_phi_node (phi, NULL_TREE, bb); + else + { + int i; + + /* Register a partition for the result. */ + register_ssa_partition (map, PHI_RESULT (phi), 0); + + /* Register a partition for each argument as needed. */ + for (i = 0; i < PHI_NUM_ARGS (phi); i++) + { + tree arg = PHI_ARG_DEF (phi, i); + + if (TREE_CODE (arg) != SSA_NAME) + continue; + if (!bitmap_bit_p (vars, + var_ann (SSA_NAME_VAR (arg))->uid)) + continue; + + register_ssa_partition (map, arg, 1); + } + } + } + } + + /* Now register partitions for SSA_NAMEs appearing in each + statement in this block. */ + for (bsi = bsi_start (bb); ! bsi_end_p (bsi); bsi_next (&bsi)) + { + stmt_ann_t ann = stmt_ann (bsi_stmt (bsi)); + use_optype uses = USE_OPS (ann); + def_optype defs = DEF_OPS (ann); + unsigned int i; + + for (i = 0; i < NUM_USES (uses); i++) + { + tree op = USE_OP (uses, i); + + if (TREE_CODE (op) == SSA_NAME + && bitmap_bit_p (vars, var_ann (SSA_NAME_VAR (op))->uid)) + register_ssa_partition (map, op, 1); + } + + for (i = 0; i < NUM_DEFS (defs); i++) + { + tree op = DEF_OP (defs, i); + + if (TREE_CODE (op) == SSA_NAME + && bitmap_bit_p (vars, + var_ann (SSA_NAME_VAR (op))->uid)) + register_ssa_partition (map, op, 0); + } + } + } + } +} + |