- bitmap_iterator bi;
- int *tos = stack;
-
- 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, bi)
- {
- *tos++ = b;
- }
-
- while (tos != stack)
- {
- b = *--tos;
-
- FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds)
- 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);
- *tos++ = 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;
- unsigned i;
- basic_block bb;
- bitmap saw_def;
- tree phi, var, stmt;
- tree op;
- edge e;
- int *stack;
- block_stmt_iterator bsi;
- ssa_op_iter iter;
- bitmap_iterator bi;
-#ifdef ENABLE_CHECKING
- int num;
- edge_iterator ei;
-#endif
-
- saw_def = BITMAP_ALLOC (NULL);
-
- live = new_tree_live_info (map);
-
- FOR_EACH_BB (bb)
- {
- bitmap_clear (saw_def);
-
- for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
- {
- for (i = 0; i < (unsigned)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 = EDGE_PRED (bb, 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 = PHI_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);
-
- FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
- {
- add_livein_if_notdef (live, saw_def, op, bb);
- }
-
- FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
- {
- set_if_valid (map, saw_def, op);
- }
- }
- }
-
- stack = XNEWVEC (int, last_basic_block);
- EXECUTE_IF_SET_IN_BITMAP (live->global, 0, i, bi)
- {
- live_worklist (live, stack, i);
- }
- free (stack);
-
-#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_EACH_EDGE (e, ei, bb->succs)
- {
- int entry_block = e->dest->index;
- if (e->dest == EXIT_BLOCK_PTR)
- continue;
- for (i = 0; i < (unsigned)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 = gimple_default_def (cfun, 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 = PHI_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");
- }
- }
- }
- gcc_assert (num <= 0);
-#endif
-
- BITMAP_FREE (saw_def);
-
- 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;
- unsigned 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 < (unsigned)last_basic_block; x++)
- on_exit[x] = BITMAP_ALLOC (NULL);
-
- /* 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));
- tpa->trees = VEC_alloc (tree, heap, x);
- tpa->first_partition = VEC_alloc (int, heap, x);
-
- 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)
- {
- VEC_replace (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;
-
- VEC_free (tree, heap, tpa->trees);
- VEC_free (int, heap, tpa->first_partition);
- 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 = VEC_index (tree, tpa->trees, last);
- swap_i = VEC_index (int, tpa->first_partition, last);
-
- /* Update the last entry. Since it is known to only have one
- partition, there is nothing else to update. */
- VEC_replace (tree, tpa->trees, last,
- VEC_index (tree, tpa->trees, x));
- VEC_replace (int, tpa->first_partition, last,
- VEC_index (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. */
- VEC_replace (tree, tpa->trees, x, swap_t);
- VEC_replace (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] = VEC_index (int, rv->first_partition,
- VAR_ANN_ROOT_INDEX (ann));
- VEC_replace (int, rv->first_partition, VAR_ANN_ROOT_INDEX (ann), p);
- }
- else
- {
- ann->root_var_processed = 1;
- VAR_ANN_ROOT_INDEX (ann) = rv->num_trees++;
- VEC_safe_push (tree, heap, rv->trees, t);
- VEC_safe_push (int, heap, 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 = VEC_index (tree, rv->trees, x);
- var_ann (t)->root_var_processed = 0;
- }
-
- sbitmap_free (seen);
- return rv;
-}
-
-
-/* Hash function for 2 integer coalesce pairs. */
-#define COALESCE_HASH_FN(R1, R2) ((R2) * ((R2) - 1) / 2 + (R1))
-
-
-/* Return hash value for partition pair PAIR. */
-
-unsigned int
-partition_pair_map_hash (const void *pair)
-{
- hashval_t a = (hashval_t)(((partition_pair_p)pair)->first_partition);
- hashval_t b = (hashval_t)(((partition_pair_p)pair)->second_partition);
-
- return COALESCE_HASH_FN (a,b);
-}
-
-
-/* Return TRUE if PAIR1 is equivilent to PAIR2. */
-
-int
-partition_pair_map_eq (const void *pair1, const void *pair2)
-{
- partition_pair_p p1 = (partition_pair_p) pair1;
- partition_pair_p p2 = (partition_pair_p) pair2;
-
- return (p1->first_partition == p2->first_partition
- && p1->second_partition == p2->second_partition);
-}
-
-
-/* Create a new coalesce list object from MAP and return it. */
-
-coalesce_list_p
-create_coalesce_list (var_map map)
-{
- coalesce_list_p list;
- unsigned size = num_ssa_names * 3;
-
- if (size < 40)
- size = 40;
-
- list = xmalloc (sizeof (struct coalesce_list_d));
- list->list = htab_create (size, partition_pair_map_hash,
- partition_pair_map_eq, NULL);
-
- list->map = map;
- list->sorted = NULL;
- list->add_mode = true;
- list->num_sorted = 0;
- return list;
-}
-
-
-/* Delete coalesce list CL. */
-
-void
-delete_coalesce_list (coalesce_list_p cl)
-{
- htab_delete (cl->list);
- if (cl->sorted)
- free (cl->sorted);
- gcc_assert (cl->num_sorted == 0);
- 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)
-{
- struct partition_pair p, *pair;
- void **slot;
- unsigned int hash;
-
- /* normalize so that p1 is the smaller value. */
- if (p2 < p1)
- {
- p.first_partition = p2;
- p.second_partition = p1;
- }
- else
- {
- p.first_partition = p1;
- p.second_partition = p2;
- }
-
-
- hash = partition_pair_map_hash (&p);
- pair = (struct partition_pair *) htab_find_with_hash (cl->list, &p, hash);
-
- if (create && !pair)
- {
- gcc_assert (cl->add_mode);
- pair = xmalloc (sizeof (struct partition_pair));
- pair->first_partition = p.first_partition;
- pair->second_partition = p.second_partition;
- pair->cost = 0;
- slot = htab_find_slot_with_hash (cl->list, pair, hash, INSERT);
- *(struct partition_pair **)slot = pair;
- }
-
- return pair;
-}
-
-/* Return cost of execution of copy instruction with FREQUENCY
- possibly on CRITICAL edge and in HOT basic block. */
-int
-coalesce_cost (int frequency, bool hot, bool critical)
-{
- /* Base costs on BB frequencies bounded by 1. */
- int cost = frequency;
-
- if (!cost)
- cost = 1;
- if (optimize_size || hot)
- cost = 1;
- /* Inserting copy on critical edge costs more
- than inserting it elsewhere. */
- if (critical)
- cost *= 2;
- return cost;
-}
-
-/* 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;
-
- gcc_assert (cl->add_mode);
-
- 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 Ascendiong order. */
-
-static
-int compare_pairs (const void *p1, const void *p2)
-{
- return (*(partition_pair_p *)p1)->cost - (*(partition_pair_p *)p2)->cost;
-}
-
-
-static inline int
-num_coalesce_pairs (coalesce_list_p cl)
-{
- return htab_elements (cl->list);
-}
-
-typedef struct
-{
- htab_iterator hti;
-} partition_pair_iterator;
-
-static inline partition_pair_p
-first_partition_pair (coalesce_list_p cl, partition_pair_iterator *iter)
-{
- partition_pair_p pair;
-
- pair = (partition_pair_p) first_htab_element (&(iter->hti), cl->list);
- return pair;
-}
OSDN Git Service
