- tree_live_info_p live;
- int num, i;
- basic_block bb;
- bitmap saw_def;
- tree phi, var, stmt;
- tree op;
- edge e;
- varray_type stack;
- block_stmt_iterator bsi;
- 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 = PHI_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 = 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);
- get_stmt_operands (stmt);
- ann = stmt_ann (stmt);
-
- uses = USE_OPS (ann);
- num = NUM_USES (uses);
- for (i = 0; i < num; i++)
- {
- op = USE_OP (uses, i);
- add_livein_if_notdef (live, saw_def, op, bb);
- }
-
- defs = DEF_OPS (ann);
- num = NUM_DEFS (defs);
- for (i = 0; i < num; i++)
- {
- op = DEF_OP (defs, i);
- set_if_valid (map, saw_def, op);
- }
- }
- }
-
- 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 = 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");
- }
- }
- }
- if (num > 0)
- abort ();
-#endif
-
- BITMAP_XFREE (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;
- 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 = PHI_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. */