From 40b4234b4927a6c770c7127947a6bac651532ceb Mon Sep 17 00:00:00 2001 From: Andrew Macleod Date: Sat, 19 Aug 2006 01:32:59 +0000 Subject: rewrite the live on entry routines to use the immediate use links. rewrite the live on exit routines to be calculated on demand as they are needed. 2006-08-18 Andrew MacLeod * tree-ssa-live.c (new_tree_live_info): Don't initialize global bitmap and initialize livein vectors to NULL rather than an empty bitmap. (delete_tree_live_info): Free live bitmaps only if allocated. (live_worklist): Use stack which is in liveinfo struct. Stack is already initially set upon entry now. (add_livein_if_notdef): Remove. (set_var_live_on_entry): New. Calculate the initial set of live on entry blocks using immediate use links. (calculate_live_on_entry): Call set_var_live_on_entry for each var. Split out the data verification code. (calculate_live_on_exit): Remove. (calc_live_at_exit): New. Calculate the live on exit data for a single basic block. (build_tree_conflict_graph): Use calc_live_at_exit. (dump_live_info): Use calc_live_at_exit, check for empty live-on-entry vectors. (verify_live_on_entry): New. Split out verification code from calculate_live_on_entry. * tree-ssa-live.h (struct tree_live_info_d): Remove global and liveout bitmaps. Add succ_mask and integer work stack fields. (partition_is_global): Check for existance of live on entry info. (live_on_exit): Remove. (live_merge_and_clear): Add asserts. (make_live_on_entry): Allocate a bitmap if needed. * tree-outof-ssa.c (coalesce_ssa_name, coalesce_vars): Remove call to calculate_live_on_exit. git-svn-id: https://gcc.gnu.org/svn/gcc/branches/out-of-ssa-the-sequel@116257 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 29 +++ gcc/tree-outof-ssa.c | 3 - gcc/tree-ssa-live.c | 534 +++++++++++++++++++++++++++------------------------ gcc/tree-ssa-live.h | 41 ++-- 4 files changed, 326 insertions(+), 281 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 02e00bb9366..27c7c1685f8 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,32 @@ +2006-08-18 Andrew MacLeod + + * tree-ssa-live.c (new_tree_live_info): Don't initialize global bitmap + and initialize livein vectors to NULL rather than an empty bitmap. + (delete_tree_live_info): Free live bitmaps only if allocated. + (live_worklist): Use stack which is in liveinfo struct. Stack is + already initially set upon entry now. + (add_livein_if_notdef): Remove. + (set_var_live_on_entry): New. Calculate the initial set of live on + entry blocks using immediate use links. + (calculate_live_on_entry): Call set_var_live_on_entry for each var. + Split out the data verification code. + (calculate_live_on_exit): Remove. + (calc_live_at_exit): New. Calculate the live on exit data for a + single basic block. + (build_tree_conflict_graph): Use calc_live_at_exit. + (dump_live_info): Use calc_live_at_exit, check for empty live-on-entry + vectors. + (verify_live_on_entry): New. Split out verification code from + calculate_live_on_entry. + * tree-ssa-live.h (struct tree_live_info_d): Remove global and liveout + bitmaps. Add succ_mask and integer work stack fields. + (partition_is_global): Check for existance of live on entry info. + (live_on_exit): Remove. + (live_merge_and_clear): Add asserts. + (make_live_on_entry): Allocate a bitmap if needed. + * tree-outof-ssa.c (coalesce_ssa_name, coalesce_vars): Remove call to + calculate_live_on_exit. + 2006-08-04 Andrew MacLeod * tree-ssa-copyrename.c (copy_rename_partition_coalesce): Change parms diff --git a/gcc/tree-outof-ssa.c b/gcc/tree-outof-ssa.c index a169eb6b8e8..ba7e1223a6b 100644 --- a/gcc/tree-outof-ssa.c +++ b/gcc/tree-outof-ssa.c @@ -824,7 +824,6 @@ coalesce_ssa_name (var_map map, int flags) return NULL; liveinfo = calculate_live_on_entry (map); - calculate_live_on_exit (liveinfo); rv = root_var_init (map); /* Remove single element variable from the list. */ @@ -1194,8 +1193,6 @@ coalesce_vars (var_map map, tree_live_info_p liveinfo) } - /* Re-calculate live on exit info. */ - calculate_live_on_exit (liveinfo); if (dump_file && (dump_flags & TDF_DETAILS)) { diff --git a/gcc/tree-ssa-live.c b/gcc/tree-ssa-live.c index a78e0f3eaa7..8c183178615 100644 --- a/gcc/tree-ssa-live.c +++ b/gcc/tree-ssa-live.c @@ -40,15 +40,17 @@ Boston, MA 02110-1301, USA. */ #include "toplev.h" #include "vecprim.h" -static void live_worklist (tree_live_info_p, int *, int); +static void live_worklist (tree_live_info_p, 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 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); +#ifdef ENABLE_CHECKING +static void verify_live_on_entry (tree_live_info_p); +#endif + /* This is where the mapping from SSA version number to real storage variable is tracked. @@ -491,7 +493,6 @@ create_ssa_var_map (void) /* Allocate and return a new live range information object base on MAP. */ - static tree_live_info_p new_tree_live_info (var_map map) { @@ -502,69 +503,69 @@ new_tree_live_info (var_map map) live->map = map; live->num_blocks = last_basic_block; - live->global = BITMAP_ALLOC (NULL); - live->livein = (bitmap *)xmalloc (num_var_partitions (map) * sizeof (bitmap)); for (x = 0; x < num_var_partitions (map); x++) - live->livein[x] = BITMAP_ALLOC (NULL); + live->livein[x] = NULL; + + live->work_stack = XNEWVEC (int, last_basic_block); + live->stack_top = live->work_stack; + live->succ_mask = NULL; - /* 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_FREE (live->liveout[x]); - free (live->liveout); - } if (live->livein) { for (x = num_var_partitions (live->map) - 1; x >= 0; x--) - BITMAP_FREE (live->livein[x]); + if (live->livein[x]) + BITMAP_FREE (live->livein[x]); free (live->livein); } - if (live->global) - BITMAP_FREE (live->global); - + + if (live->succ_mask) + BITMAP_FREE (live->succ_mask); + + free (live->work_stack); 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. */ - + for partition I. */ static void -live_worklist (tree_live_info_p live, int *stack, int i) +live_worklist (tree_live_info_p live, int i) { - unsigned b; - tree var; - basic_block def_bb = NULL; edge e; - var_map map = live->map; + tree var; + unsigned b; edge_iterator ei; - bitmap_iterator bi; - int *tos = stack; + basic_block def_bb = NULL; + int *tos = live->stack_top; + int *empty_stack = live->work_stack; - var = partition_to_var (map, i); + var = partition_to_var (live->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; - } +#ifdef ENABLE_CHECKING + { + int x = 0; + bitmap_iterator bi; - while (tos != stack) + /* Make sure the stack has the same number of elements as liveins. */ + EXECUTE_IF_SET_IN_BITMAP (live->livein[i], 0, b, bi) + x++; + gcc_assert (x == (tos - empty_stack)); + } +#endif + + while (tos != empty_stack) { b = *--tos; @@ -581,260 +582,167 @@ live_worklist (tree_live_info_p live, int *stack, int i) } } } -} - -/* 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); + /* Reset stack top pointer. */ + live->stack_top = live->work_stack; } -/* 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) +/* Calulate the live on entry vector for the SSA_NAME using immediate_use + links. Set the live on entry fields in LIVE. */ +static void +set_var_live_on_entry (tree ssa_name, tree_live_info_p live) { - 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. */ + int p; + tree stmt; + use_operand_p use; + bitmap on_entry = NULL; + basic_block def_bb = NULL; + imm_use_iterator imm_iter; -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 + p = var_to_partition (live->map, ssa_name); + if (p == NO_PARTITION) + return; - saw_def = BITMAP_ALLOC (NULL); + stmt = SSA_NAME_DEF_STMT (ssa_name); + if (stmt) + def_bb = bb_for_stmt (stmt); + else + def_bb = ENTRY_BLOCK_PTR; - live = new_tree_live_info (map); + gcc_assert (live->stack_top == live->work_stack); - FOR_EACH_BB (bb) + /* Visit each use of SSA_NAME and if it isn't in the same block as the def, + add it to the list of live on entry blocks. */ + FOR_EACH_IMM_USE_FAST (use, imm_iter, ssa_name) { - 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 - b_3 = PHI - The a_3 referred to in b_3's PHI node is the one incoming on the - edge, *not* the PHI node just seen. */ + tree use_stmt = USE_STMT (use); + basic_block add_block = NULL; - for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) + if (TREE_CODE (use_stmt) == PHI_NODE) { - var = PHI_RESULT (phi); - set_if_valid (map, saw_def, var); + /* Uses in PHI's are considered to be live at exit of the SRC block + as this is where a copy would be inserted. Check to see if it is + defined in that block, or whether its live on entry. */ + int index = PHI_ARG_INDEX_FROM_USE (use); + edge e = PHI_ARG_EDGE (use_stmt, index); + if (e->src != def_bb && e->src != ENTRY_BLOCK_PTR) + add_block = e->src; } - - for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) + else { - 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) + /* If its not defined in this block, its live on entry. */ + basic_block use_bb = bb_for_stmt (use_stmt); + if (use_bb != def_bb) + add_block = use_bb; + } + + /* If there was a live on entry use, set the bit. */ + if (add_block) + { + /* Don't allocate a bitmap until its needed. */ + if (!on_entry) + on_entry = BITMAP_ALLOC (NULL); + if (!bitmap_bit_p (on_entry, add_block->index)) { - set_if_valid (map, saw_def, op); + bitmap_set_bit (on_entry, add_block->index); + *(live->stack_top)++ = add_block->index; } } } - stack = XNEWVEC (int, last_basic_block); - EXECUTE_IF_SET_IN_BITMAP (live->global, 0, i, bi) + /* If SSA_NAME is live on entry to at least one block, fill in all the live + on entry blocks between the def and all the uses. */ + if (on_entry) { - live_worklist (live, stack, i); + live->livein[p] = on_entry; + live_worklist (live, p); } - 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 = default_def (SSA_NAME_VAR (var)); +/* Given partition map MAP, calculate all the live on entry bitmaps for + each partition. Return a new live info object. */ +tree_live_info_p +calculate_live_on_entry (var_map map) +{ + tree var; + unsigned i; + tree_live_info_p live; - 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"); - } - } + live = new_tree_live_info (map); + for (i = 0; i < num_var_partitions (map); i++) + { + var = partition_to_var (map, i); + if (var != NULL_TREE) + set_var_live_on_entry (var, live); } - gcc_assert (num <= 0); -#endif - - BITMAP_FREE (saw_def); +#ifdef ENABLE_CHECKING + verify_live_on_entry (live); +#endif return live; } -/* Calculate the live on exit vectors based on the entry info in LIVEINFO. */ - +/* Calculate live at exit on demand for basic block BB. Use the live on entry + info in LIVEINFO, and return the results in the already allocated bitmap + AT_EXIT. */ void -calculate_live_on_exit (tree_live_info_p liveinfo) +calc_live_at_exit (basic_block bb, tree_live_info_p liveinfo, bitmap at_exit) { - unsigned b; - unsigned i, x; - bitmap *on_exit; - basic_block bb; edge e; - tree t, phi; + unsigned x; + tree phi, use; + int partition; bitmap on_entry; + edge_iterator ei; var_map map = liveinfo->map; + bitmap succ_mask; + + if (liveinfo->succ_mask == NULL) + liveinfo->succ_mask = BITMAP_ALLOC (NULL); + succ_mask = liveinfo->succ_mask; - on_exit = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap)); - for (x = 0; x < (unsigned)last_basic_block; x++) - on_exit[x] = BITMAP_ALLOC (NULL); + bitmap_clear (succ_mask); + bitmap_clear (at_exit); - /* Set all the live-on-exit bits for uses in PHIs. */ - FOR_EACH_BB (bb) + FOR_EACH_EDGE (e, ei, bb->succs) { - 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); - } - } + basic_block succ = e->dest; - /* Set live on exit for all predecessors of live on entry's. */ - for (i = 0; i < num_var_partitions (map); i++) - { - bitmap_iterator bi; + /* Set a bit in succ_mask for each edge. At the end of the edge loop, + succ_mask will have a bit set for each successor edge of this + block. */ + if (succ != EXIT_BLOCK_PTR) + bitmap_set_bit (succ_mask, succ->index); - on_entry = live_entry_blocks (liveinfo, i); - EXECUTE_IF_SET_IN_BITMAP (on_entry, 0, b, bi) + /* Visit all the PHI nodes on the edge, and mark any phi arguments on + this edge as live at exit. */ + for (phi = phi_nodes (succ); phi; phi = PHI_CHAIN (phi)) { - 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); + use = PHI_ARG_DEF_FROM_EDGE (phi, e); + if (TREE_CODE (use) != SSA_NAME) + continue; + partition = var_to_partition (map, use); + if (partition == NO_PARTITION) + continue; + bitmap_set_bit (at_exit, partition); } } - - liveinfo->liveout = on_exit; + + /* Loop over each partition, and if it has a live on entry bitmap, check to + see if it is live on any successor block of BB. This is easily determined + by checking if live on entry intersects succ_mask. */ + for (x = 0; x < num_var_partitions (map); x++) + { + /* iF any variable is live on entry to any succ block, add to live + at exit bitmap. */ + on_entry = live_entry_blocks (liveinfo, x); + if (on_entry && !bitmap_bit_p (at_exit, x) + && bitmap_intersect_p (on_entry, succ_mask)) + bitmap_set_bit (at_exit, x); + } } @@ -1418,6 +1326,19 @@ add_conflicts_if_valid (tpa_p tpa, conflict_graph graph, } } + +/* 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); +} + + + /* 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. */ @@ -1455,8 +1376,8 @@ build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa, tree phi; int idx; - /* Start with live on exit temporaries. */ - bitmap_copy (live, live_on_exit (liveinfo, bb)); + /* Start with live at exit temporaries. */ + calc_live_at_exit (bb, liveinfo, live); for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi)) { @@ -1891,7 +1812,8 @@ dump_live_info (FILE *f, tree_live_info_p live, int flag) 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)) + bitmap loe = live_entry_blocks (live, i); + if (loe && bitmap_bit_p (loe, bb->index)) { print_generic_expr (f, partition_to_var (map, i), TDF_SLIM); fprintf (f, " "); @@ -1901,21 +1823,25 @@ dump_live_info (FILE *f, tree_live_info_p live, int flag) } } - if ((flag & LIVEDUMP_EXIT) && live->liveout) + if (flag & LIVEDUMP_EXIT) { + bitmap liveout = BITMAP_ALLOC (NULL); 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, bi) + calc_live_at_exit (bb, live, liveout); + fprintf (f, "\nLive at exit from BB%d : ", bb->index); + EXECUTE_IF_SET_IN_BITMAP (liveout, 0, i, bi) { print_generic_expr (f, partition_to_var (map, i), TDF_SLIM); fprintf (f, " "); } fprintf (f, "\n"); } + BITMAP_FREE (liveout); } } + #ifdef ENABLE_CHECKING void register_ssa_partition_check (tree ssa_var) @@ -1929,4 +1855,106 @@ register_ssa_partition_check (tree ssa_var) internal_error ("SSA corruption"); } } + + +/* Verify that the info in LIVE matches the current cfg. */ +static void +verify_live_on_entry (tree_live_info_p live) +{ + unsigned i; + tree var; + tree phi, stmt; + basic_block bb; + edge e; + int num; + edge_iterator ei; + var_map map = live->map; + + /* 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; + bitmap loe; + var = partition_to_var (map, i); + stmt = SSA_NAME_DEF_STMT (var); + tmp = bb_for_stmt (stmt); + d = default_def (SSA_NAME_VAR (var)); + + loe = live_entry_blocks (live, i); + if (loe && bitmap_bit_p (loe, 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 + + + diff --git a/gcc/tree-ssa-live.h b/gcc/tree-ssa-live.h index 7427ba50577..f539a8dbde4 100644 --- a/gcc/tree-ssa-live.h +++ b/gcc/tree-ssa-live.h @@ -209,23 +209,26 @@ typedef struct tree_live_info_d /* Var map this relates to. */ var_map map; - /* Bitmap indicating which partitions are global. */ - bitmap global; - /* Bitmap of live on entry blocks for partition elements. */ bitmap *livein; /* Number of basic blocks when live on exit calculated. */ int num_blocks; - /* Bitmap of what variables are live on exit for a basic blocks. */ - bitmap *liveout; + /* Vector used when creating live ranges as a visited stack. */ + int *work_stack; + + /* Top of woirkstack. */ + int *stack_top; + + /* Temporary working bitmap used by calc_live_at_exit. */ + bitmap succ_mask; } *tree_live_info_p; extern tree_live_info_p calculate_live_on_entry (var_map); -extern void calculate_live_on_exit (tree_live_info_p); extern void delete_tree_live_info (tree_live_info_p); +extern void calc_live_at_exit (basic_block, tree_live_info_p, bitmap); #define LIVEDUMP_ENTRY 0x01 #define LIVEDUMP_EXIT 0x02 @@ -234,7 +237,6 @@ 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); @@ -245,13 +247,13 @@ static inline void make_live_on_entry (tree_live_info_p, basic_block, int); static inline int partition_is_global (tree_live_info_p live, int p) { - gcc_assert (live->global); - return bitmap_bit_p (live->global, p); + gcc_assert (live->livein); + return (live->livein[p] != NULL); } /* Return the bitmap from LIVE representing the live on entry blocks for - partition P. */ + partition P. A NULL means there are NO live blocks. */ static inline bitmap live_entry_blocks (tree_live_info_p live, int p) @@ -261,20 +263,6 @@ live_entry_blocks (tree_live_info_p live, int p) } -/* Return the bitmap from LIVE representing the live on exit partitions from - block BB. */ - -static inline bitmap -live_on_exit (tree_live_info_p live, basic_block bb) -{ - gcc_assert (live->liveout); - gcc_assert (bb != ENTRY_BLOCK_PTR); - gcc_assert (bb != EXIT_BLOCK_PTR); - - return live->liveout[bb->index]; -} - - /* Return the partition map which the information in LIVE utilizes. */ static inline var_map @@ -290,6 +278,8 @@ live_var_map (tree_live_info_p live) 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]); } @@ -300,8 +290,9 @@ live_merge_and_clear (tree_live_info_p live, int p1, int p2) static inline void make_live_on_entry (tree_live_info_p live, basic_block bb , int p) { + if (live->livein[p] == NULL) + live->livein[p] = BITMAP_ALLOC (NULL); bitmap_set_bit (live->livein[p], bb->index); - bitmap_set_bit (live->global, p); } -- cgit v1.2.3