- /* Set all the live-on-exit bits for uses in PHIs. */
- FOR_EACH_BB (bb)
- {
- for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
- for (i = 0; i < (unsigned)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++)
- {
- bitmap_iterator bi;
-
- on_entry = live_entry_blocks (liveinfo, i);
- EXECUTE_IF_SET_IN_BITMAP (on_entry, 0, b, bi)
- {
- edge_iterator ei;
- FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds)
- 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. */
-
-static tpa_p
-tpa_init (var_map map)
-{
- tpa_p tpa;
- int num_partitions = num_var_partitions (map);
- int x;
-
- if (num_partitions == 0)
- return NULL;
-
- tpa = (tpa_p) xmalloc (sizeof (struct tree_partition_associator_d));
- tpa->num_trees = 0;
- tpa->uncompressed_num = -1;
- tpa->map = map;
- tpa->next_partition = (int *)xmalloc (num_partitions * sizeof (int));
- memset (tpa->next_partition, TPA_NONE, num_partitions * sizeof (int));
-
- tpa->partition_to_tree_map = (int *)xmalloc (num_partitions * sizeof (int));
- memset (tpa->partition_to_tree_map, TPA_NONE, num_partitions * sizeof (int));
-
- x = MAX (40, (num_partitions / 20));
- 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 entries from TPA which have only a single
- element. This will help keep the size of the conflict graph down. The
- function returns the number of remaining tree lists. */
-
-int
-tpa_compact (tpa_p tpa)
-{
- int last, x, y, first, swap_i;
- tree swap_t;
-
- /* Find the last list which has more than 1 partition. */
- for (last = tpa->num_trees - 1; last > 0; last--)
- {
- first = tpa_first_partition (tpa, last);
- if (tpa_next_partition (tpa, first) != NO_PARTITION)
- break;
- }
-
- x = 0;
- while (x < last)
- {
- first = tpa_first_partition (tpa, x);
-
- /* If there is not more than one partition, swap with the current end
- of the tree list. */
- if (tpa_next_partition (tpa, first) == NO_PARTITION)
- {
- swap_t = 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);
-
- gcc_assert (p != NO_PARTITION);
-
- /* Make sure we only put coalesced partitions into the list once. */
- if (TEST_BIT (seen, p))
- continue;
- SET_BIT (seen, p);
- if (TREE_CODE (t) == SSA_NAME)
- t = SSA_NAME_VAR (t);
- ann = var_ann (t);
- if (ann->root_var_processed)
- {
- rv->next_partition[p] = 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_IGNORED_P (t)
- || DECL_RTL_SET_P (t))))
- continue;
-
- p = var_to_partition (map, t);
-
- gcc_assert (p != NO_PARTITION);
-
- /* 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;
- }