X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fdf-problems.c;h=f48da9bc8dc081d7de60b4fee2a7f18221826b56;hb=c4c8f6ce1b77ca228e33566f9e990cb775c65f5f;hp=ff5a4ad03da37a8d0c2cc2dc19737549013cb588;hpb=a7bc23c029616a02510a0adfe9783e2918520922;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/df-problems.c b/gcc/df-problems.c index ff5a4ad03da..f48da9bc8dc 100644 --- a/gcc/df-problems.c +++ b/gcc/df-problems.c @@ -1,6 +1,6 @@ /* Standard problems for dataflow support routines. - Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007 - Free Software Foundation, Inc. + Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, + 2008, 2009 Free Software Foundation, Inc. Originally contributed by Michael P. Hayes (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com) Major rewrite contributed by Danny Berlin (dberlin@dberlin.org) @@ -109,8 +109,7 @@ df_grow_bb_info (struct dataflow *dflow) if (dflow->block_info_size < new_size) { new_size += new_size / 4; - dflow->block_info = xrealloc (dflow->block_info, - new_size *sizeof (void*)); + dflow->block_info = XRESIZEVEC (void *, dflow->block_info, new_size); memset (dflow->block_info + dflow->block_info_size, 0, (new_size - dflow->block_info_size) *sizeof (void *)); dflow->block_info_size = new_size; @@ -129,7 +128,7 @@ df_chain_dump (struct df_link *link, FILE *file) DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u', DF_REF_ID (link->ref), DF_REF_BBNO (link->ref), - DF_REF_INSN (link->ref) ? DF_REF_INSN_UID (link->ref) : -1); + DF_REF_IS_ARTIFICIAL (link->ref) ? -1 : DF_REF_INSN_UID (link->ref)); } fprintf (file, "}"); } @@ -317,16 +316,70 @@ df_rd_alloc (bitmap all_blocks) } -/* Process a list of DEFs for df_rd_bb_local_compute. */ +/* Add the effect of the top artificial defs of BB to the reaching definitions + bitmap LOCAL_RD. */ + +void +df_rd_simulate_artificial_defs_at_top (basic_block bb, bitmap local_rd) +{ + int bb_index = bb->index; + df_ref *def_rec; + for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++) + { + df_ref def = *def_rec; + if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) + { + unsigned int dregno = DF_REF_REGNO (def); + if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))) + bitmap_clear_range (local_rd, + DF_DEFS_BEGIN (dregno), + DF_DEFS_COUNT (dregno)); + bitmap_set_bit (local_rd, DF_REF_ID (def)); + } + } +} + +/* Add the effect of the defs of INSN to the reaching definitions bitmap + LOCAL_RD. */ + +void +df_rd_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx insn, + bitmap local_rd) +{ + unsigned uid = INSN_UID (insn); + df_ref *def_rec; + + for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) + { + df_ref def = *def_rec; + unsigned int dregno = DF_REF_REGNO (def); + if ((!(df->changeable_flags & DF_NO_HARD_REGS)) + || (dregno >= FIRST_PSEUDO_REGISTER)) + { + if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))) + bitmap_clear_range (local_rd, + DF_DEFS_BEGIN (dregno), + DF_DEFS_COUNT (dregno)); + if (!(DF_REF_FLAGS (def) + & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))) + bitmap_set_bit (local_rd, DF_REF_ID (def)); + } + } +} + +/* Process a list of DEFs for df_rd_bb_local_compute. This is a bit + more complicated than just simulating, because we must produce the + gen and kill sets and hence deal with the two possible representations + of kill sets. */ static void df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info, - struct df_ref **def_rec, - enum df_ref_flags top_flag) + df_ref *def_rec, + int top_flag) { while (*def_rec) { - struct df_ref *def = *def_rec; + df_ref def = *def_rec; if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP)) { unsigned int regno = DF_REF_REGNO (def); @@ -444,7 +497,7 @@ df_rd_local_compute (bitmap all_blocks) } /* Set up the knockout bit vectors to be applied across EH_EDGES. */ - EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi) + EXECUTE_IF_SET_IN_BITMAP (regs_invalidated_by_call_regset, 0, regno, bi) { if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD) bitmap_set_bit (sparse_invalidated, regno); @@ -482,6 +535,9 @@ df_rd_confluence_n (edge e) bitmap op1 = df_rd_get_bb_info (e->dest->index)->in; bitmap op2 = df_rd_get_bb_info (e->src->index)->out; + if (e->flags & EDGE_FAKE) + return; + if (e->flags & EDGE_EH) { struct df_rd_problem_data *problem_data @@ -563,28 +619,12 @@ df_rd_transfer_function (int bb_index) static void df_rd_free (void) { - unsigned int i; struct df_rd_problem_data *problem_data = (struct df_rd_problem_data *) df_rd->problem_data; if (problem_data) { - for (i = 0; i < df_rd->block_info_size; i++) - { - struct df_rd_bb_info *bb_info = df_rd_get_bb_info (i); - if (bb_info) - { - BITMAP_FREE (bb_info->kill); - BITMAP_FREE (bb_info->sparse_kill); - BITMAP_FREE (bb_info->gen); - BITMAP_FREE (bb_info->in); - BITMAP_FREE (bb_info->out); - } - } - free_alloc_pool (df_rd->block_pool); - BITMAP_FREE (problem_data->sparse_invalidated_by_call); - BITMAP_FREE (problem_data->dense_invalidated_by_call); bitmap_obstack_release (&problem_data->rd_bitmaps); df_rd->block_info_size = 0; @@ -703,7 +743,7 @@ df_rd_add_problem (void) Find the locations in the function where any use of a pseudo can reach in the backwards direction. In and out bitvectors are built - for each basic block. The regnum is used to index into these sets. + for each basic block. The regno is used to index into these sets. See df.h for details. ----------------------------------------------------------------------------*/ @@ -809,13 +849,13 @@ df_lr_bb_local_compute (unsigned int bb_index) basic_block bb = BASIC_BLOCK (bb_index); struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index); rtx insn; - struct df_ref **def_rec; - struct df_ref **use_rec; + df_ref *def_rec; + df_ref *use_rec; /* Process the registers set in an exception handler. */ for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++) { - struct df_ref *def = *def_rec; + df_ref def = *def_rec; if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0) { unsigned int dregno = DF_REF_REGNO (def); @@ -827,7 +867,7 @@ df_lr_bb_local_compute (unsigned int bb_index) /* Process the hardware registers that are always live. */ for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++) { - struct df_ref *use = *use_rec; + df_ref use = *use_rec; /* Add use to set of uses in this BB. */ if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0) bitmap_set_bit (bb_info->use, DF_REF_REGNO (use)); @@ -842,7 +882,7 @@ df_lr_bb_local_compute (unsigned int bb_index) for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) { - struct df_ref *def = *def_rec; + df_ref def = *def_rec; /* If the def is to only part of the reg, it does not kill the other defs that reach here. */ if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))) @@ -855,7 +895,7 @@ df_lr_bb_local_compute (unsigned int bb_index) for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++) { - struct df_ref *use = *use_rec; + df_ref use = *use_rec; /* Add use to set of uses in this BB. */ bitmap_set_bit (bb_info->use, DF_REF_REGNO (use)); } @@ -866,7 +906,7 @@ df_lr_bb_local_compute (unsigned int bb_index) goto. */ for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++) { - struct df_ref *def = *def_rec; + df_ref def = *def_rec; if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) { unsigned int dregno = DF_REF_REGNO (def); @@ -879,7 +919,7 @@ df_lr_bb_local_compute (unsigned int bb_index) /* Process the uses that are live into an exception handler. */ for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++) { - struct df_ref *use = *use_rec; + df_ref use = *use_rec; /* Add use to set of uses in this BB. */ if (DF_REF_FLAGS (use) & DF_REF_AT_TOP) bitmap_set_bit (bb_info->use, DF_REF_REGNO (use)); @@ -989,7 +1029,7 @@ df_lr_confluence_n (edge e) /* ??? Abnormal call edges ignored for the moment, as this gets confused by sibling call edges, which crashes reg-stack. */ if (e->flags & EDGE_EH) - bitmap_ior_and_compl_into (op1, op2, df_invalidated_by_call); + bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset); else bitmap_ior_into (op1, op2); @@ -1015,25 +1055,34 @@ df_lr_transfer_function (int bb_index) /* Run the fast dce as a side effect of building LR. */ static void -df_lr_local_finalize (bitmap all_blocks ATTRIBUTE_UNUSED) +df_lr_finalize (bitmap all_blocks) { + df_lr->solutions_dirty = false; if (df->changeable_flags & DF_LR_RUN_DCE) { run_fast_df_dce (); - if (df_lr->problem_data && df_lr->solutions_dirty) + + /* If dce deletes some instructions, we need to recompute the lr + solution before proceeding further. The problem is that fast + dce is a pessimestic dataflow algorithm. In the case where + it deletes a statement S inside of a loop, the uses inside of + S may not be deleted from the dataflow solution because they + were carried around the loop. While it is conservatively + correct to leave these extra bits, the standards of df + require that we maintain the best possible (least fixed + point) solution. The only way to do that is to redo the + iteration from the beginning. See PR35805 for an + example. */ + if (df_lr->solutions_dirty) { - /* If we are here, then it is because we are both verifying - the solution and the dce changed the function. In that case - the verification info built will be wrong. So we leave the - dirty flag true so that the verifier will skip the checking - part and just clean up.*/ - df_lr->solutions_dirty = true; + df_clear_flags (DF_LR_RUN_DCE); + df_lr_alloc (all_blocks); + df_lr_local_compute (all_blocks); + df_worklist_dataflow (df_lr, all_blocks, df->postorder, df->n_blocks); + df_lr_finalize (all_blocks); + df_set_flags (DF_LR_RUN_DCE); } - else - df_lr->solutions_dirty = false; } - else - df_lr->solutions_dirty = false; } @@ -1161,7 +1210,7 @@ df_lr_verify_solution_end (void) if (df_lr->solutions_dirty) /* Do not check if the solution is still dirty. See the comment - in df_lr_local_finalize for details. */ + in df_lr_finalize for details. */ df_lr->solutions_dirty = false; else FOR_ALL_BB (bb) @@ -1204,7 +1253,7 @@ static struct df_problem problem_LR = df_lr_confluence_0, /* Confluence operator 0. */ df_lr_confluence_n, /* Confluence operator n. */ df_lr_transfer_function, /* Transfer function. */ - df_lr_local_finalize, /* Finalize function. */ + df_lr_finalize, /* Finalize function. */ df_lr_free, /* Free all of the problem information. */ NULL, /* Remove this problem from the stack of dataflow problems. */ NULL, /* Debugging. */ @@ -1429,7 +1478,7 @@ df_live_bb_local_compute (unsigned int bb_index) basic_block bb = BASIC_BLOCK (bb_index); struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index); rtx insn; - struct df_ref **def_rec; + df_ref *def_rec; int luid = 0; FOR_BB_INSNS (bb, insn) @@ -1442,17 +1491,17 @@ df_live_bb_local_compute (unsigned int bb_index) if (!insn_info) { gcc_assert (!INSN_P (insn)); - df_insn_create_insn_record (insn); + insn_info = df_insn_create_insn_record (insn); } - DF_INSN_LUID (insn) = luid; + DF_INSN_INFO_LUID (insn_info) = luid; if (!INSN_P (insn)) continue; luid++; - for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) + for (def_rec = DF_INSN_INFO_DEFS (insn_info); *def_rec; def_rec++) { - struct df_ref *def = *def_rec; + df_ref def = *def_rec; unsigned int regno = DF_REF_REGNO (def); if (DF_REF_FLAGS_IS_SET (def, @@ -1471,7 +1520,7 @@ df_live_bb_local_compute (unsigned int bb_index) for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++) { - struct df_ref *def = *def_rec; + df_ref def = *def_rec; bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def)); } } @@ -1560,7 +1609,7 @@ df_live_transfer_function (int bb_index) /* And the LR info with the must-initialized registers, to produce the LIVE info. */ static void -df_live_local_finalize (bitmap all_blocks) +df_live_finalize (bitmap all_blocks) { if (df_live->solutions_dirty) @@ -1751,7 +1800,7 @@ static struct df_problem problem_LIVE = NULL, /* Confluence operator 0. */ df_live_confluence_n, /* Confluence operator n. */ df_live_transfer_function, /* Transfer function. */ - df_live_local_finalize, /* Finalize function. */ + df_live_finalize, /* Finalize function. */ df_live_free, /* Free all of the problem information. */ df_live_free, /* Remove this problem from the stack of dataflow problems. */ NULL, /* Debugging. */ @@ -1872,10 +1921,10 @@ df_live_verify_transfer_functions (void) /* Create a du or ud chain from SRC to DST and link it into SRC. */ struct df_link * -df_chain_create (struct df_ref *src, struct df_ref *dst) +df_chain_create (df_ref src, df_ref dst) { struct df_link *head = DF_REF_CHAIN (src); - struct df_link *link = pool_alloc (df_chain->block_pool);; + struct df_link *link = (struct df_link *) pool_alloc (df_chain->block_pool); DF_REF_CHAIN (src) = link; link->next = head; @@ -1887,7 +1936,7 @@ df_chain_create (struct df_ref *src, struct df_ref *dst) /* Delete any du or ud chains that start at REF and point to TARGET. */ static void -df_chain_unlink_1 (struct df_ref *ref, struct df_ref *target) +df_chain_unlink_1 (df_ref ref, df_ref target) { struct df_link *chain = DF_REF_CHAIN (ref); struct df_link *prev = NULL; @@ -1912,7 +1961,7 @@ df_chain_unlink_1 (struct df_ref *ref, struct df_ref *target) /* Delete a du or ud chain that leave or point to REF. */ void -df_chain_unlink (struct df_ref *ref) +df_chain_unlink (df_ref ref) { struct df_link *chain = DF_REF_CHAIN (ref); while (chain) @@ -1931,7 +1980,7 @@ df_chain_unlink (struct df_ref *ref) TO_REF. */ void -df_chain_copy (struct df_ref *to_ref, +df_chain_copy (df_ref to_ref, struct df_link *from_ref) { while (from_ref) @@ -1957,8 +2006,8 @@ df_chain_remove_problem (void) EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi) { rtx insn; - struct df_ref **def_rec; - struct df_ref **use_rec; + df_ref *def_rec; + df_ref *use_rec; basic_block bb = BASIC_BLOCK (bb_index); if (df_chain_problem_p (DF_DU_CHAIN)) @@ -2029,15 +2078,15 @@ df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED) static void df_chain_create_bb_process_use (bitmap local_rd, - struct df_ref **use_rec, - enum df_ref_flags top_flag) + df_ref *use_rec, + int top_flag) { bitmap_iterator bi; unsigned int def_index; while (*use_rec) { - struct df_ref *use = *use_rec; + df_ref use = *use_rec; unsigned int uregno = DF_REF_REGNO (use); if ((!(df->changeable_flags & DF_NO_HARD_REGS)) || (uregno >= FIRST_PSEUDO_REGISTER)) @@ -2053,7 +2102,7 @@ df_chain_create_bb_process_use (bitmap local_rd, EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi) { - struct df_ref *def; + df_ref def; if (def_index > last_index) break; @@ -2081,7 +2130,6 @@ df_chain_create_bb (unsigned int bb_index) struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index); rtx insn; bitmap cpy = BITMAP_ALLOC (NULL); - struct df_ref **def_rec; bitmap_copy (cpy, bb_info->in); bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index); @@ -2100,57 +2148,23 @@ df_chain_create_bb (unsigned int bb_index) DF_REF_AT_TOP); #endif - for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++) - { - struct df_ref *def = *def_rec; - if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) - { - unsigned int dregno = DF_REF_REGNO (def); - if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))) - bitmap_clear_range (cpy, - DF_DEFS_BEGIN (dregno), - DF_DEFS_COUNT (dregno)); - bitmap_set_bit (cpy, DF_REF_ID (def)); - } - } + df_rd_simulate_artificial_defs_at_top (bb, cpy); /* Process the regular instructions next. */ FOR_BB_INSNS (bb, insn) - { - struct df_ref **def_rec; - unsigned int uid = INSN_UID (insn); - - if (!INSN_P (insn)) - continue; - - /* Now scan the uses and link them up with the defs that remain - in the cpy vector. */ - - df_chain_create_bb_process_use (cpy, DF_INSN_UID_USES (uid), 0); - - if (df->changeable_flags & DF_EQ_NOTES) - df_chain_create_bb_process_use (cpy, DF_INSN_UID_EQ_USES (uid), 0); + if (INSN_P (insn)) + { + unsigned int uid = INSN_UID (insn); + /* First scan the uses and link them up with the defs that remain + in the cpy vector. */ + df_chain_create_bb_process_use (cpy, DF_INSN_UID_USES (uid), 0); + if (df->changeable_flags & DF_EQ_NOTES) + df_chain_create_bb_process_use (cpy, DF_INSN_UID_EQ_USES (uid), 0); - /* Since we are going forwards, process the defs second. This - pass only changes the bits in cpy. */ - for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) - { - struct df_ref *def = *def_rec; - unsigned int dregno = DF_REF_REGNO (def); - if ((!(df->changeable_flags & DF_NO_HARD_REGS)) - || (dregno >= FIRST_PSEUDO_REGISTER)) - { - if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))) - bitmap_clear_range (cpy, - DF_DEFS_BEGIN (dregno), - DF_DEFS_COUNT (dregno)); - if (!(DF_REF_FLAGS (def) - & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))) - bitmap_set_bit (cpy, DF_REF_ID (def)); - } - } - } + /* Since we are going forwards, process the defs second. */ + df_rd_simulate_one_insn (bb, insn, cpy); + } /* Create the chains for the artificial uses of the hard registers at the end of the block. */ @@ -2197,14 +2211,14 @@ df_chain_top_dump (basic_block bb, FILE *file) if (df_chain_problem_p (DF_DU_CHAIN)) { rtx insn; - struct df_ref **def_rec = df_get_artificial_defs (bb->index); + df_ref *def_rec = df_get_artificial_defs (bb->index); if (*def_rec) { fprintf (file, ";; DU chains for artificial defs\n"); while (*def_rec) { - struct df_ref *def = *def_rec; + df_ref def = *def_rec; fprintf (file, ";; reg %d ", DF_REF_REGNO (def)); df_chain_dump (DF_REF_CHAIN (def), file); fprintf (file, "\n"); @@ -2214,20 +2228,20 @@ df_chain_top_dump (basic_block bb, FILE *file) FOR_BB_INSNS (bb, insn) { - unsigned int uid = INSN_UID (insn); if (INSN_P (insn)) { - def_rec = DF_INSN_UID_DEFS (uid); + struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); + def_rec = DF_INSN_INFO_DEFS (insn_info); if (*def_rec) { fprintf (file, ";; DU chains for insn luid %d uid %d\n", - DF_INSN_LUID (insn), uid); + DF_INSN_INFO_LUID (insn_info), INSN_UID (insn)); while (*def_rec) { - struct df_ref *def = *def_rec; + df_ref def = *def_rec; fprintf (file, ";; reg %d ", DF_REF_REGNO (def)); - if (def->flags & DF_REF_READ_WRITE) + if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE) fprintf (file, "read/write "); df_chain_dump (DF_REF_CHAIN (def), file); fprintf (file, "\n"); @@ -2246,14 +2260,14 @@ df_chain_bottom_dump (basic_block bb, FILE *file) if (df_chain_problem_p (DF_UD_CHAIN)) { rtx insn; - struct df_ref **use_rec = df_get_artificial_uses (bb->index); + df_ref *use_rec = df_get_artificial_uses (bb->index); if (*use_rec) { fprintf (file, ";; UD chains for artificial uses\n"); while (*use_rec) { - struct df_ref *use = *use_rec; + df_ref use = *use_rec; fprintf (file, ";; reg %d ", DF_REF_REGNO (use)); df_chain_dump (DF_REF_CHAIN (use), file); fprintf (file, "\n"); @@ -2263,21 +2277,21 @@ df_chain_bottom_dump (basic_block bb, FILE *file) FOR_BB_INSNS (bb, insn) { - unsigned int uid = INSN_UID (insn); if (INSN_P (insn)) { - struct df_ref **eq_use_rec = DF_INSN_UID_EQ_USES (uid); - use_rec = DF_INSN_UID_USES (uid); + struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); + df_ref *eq_use_rec = DF_INSN_INFO_EQ_USES (insn_info); + use_rec = DF_INSN_INFO_USES (insn_info); if (*use_rec || *eq_use_rec) { fprintf (file, ";; UD chains for insn luid %d uid %d\n", - DF_INSN_LUID (insn), uid); + DF_INSN_INFO_LUID (insn_info), INSN_UID (insn)); while (*use_rec) { - struct df_ref *use = *use_rec; + df_ref use = *use_rec; fprintf (file, ";; reg %d ", DF_REF_REGNO (use)); - if (use->flags & DF_REF_READ_WRITE) + if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE) fprintf (file, "read/write "); df_chain_dump (DF_REF_CHAIN (use), file); fprintf (file, "\n"); @@ -2285,7 +2299,7 @@ df_chain_bottom_dump (basic_block bb, FILE *file) } while (*eq_use_rec) { - struct df_ref *use = *eq_use_rec; + df_ref use = *eq_use_rec; fprintf (file, ";; eq_note reg %d ", DF_REF_REGNO (use)); df_chain_dump (DF_REF_CHAIN (use), file); fprintf (file, "\n"); @@ -2330,10 +2344,10 @@ static struct df_problem problem_CHAIN = solution. */ void -df_chain_add_problem (enum df_chain_flags chain_flags) +df_chain_add_problem (unsigned int chain_flags) { df_add_problem (&problem_CHAIN); - df_chain->local_flags = (unsigned int)chain_flags; + df_chain->local_flags = chain_flags; df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (NULL); } @@ -2341,189 +2355,916 @@ df_chain_add_problem (enum df_chain_flags chain_flags) /*---------------------------------------------------------------------------- - This pass computes REG_DEAD and REG_UNUSED notes. + BYTE LEVEL LIVE REGISTERS + + Find the locations in the function where any use of a pseudo can + reach in the backwards direction. In and out bitvectors are built + for each basic block. There are two mapping functions, + df_byte_lr_get_regno_start and df_byte_lr_get_regno_len that are + used to map regnos into bit vector positions. + + This problem differs from the regular df_lr function in the way + that subregs, *_extracts and strict_low_parts are handled. In lr + these are consider partial kills, here, the exact set of bytes is + modeled. Note that any reg that has none of these operations is + only modeled with a single bit since all operations access the + entire register. + + This problem is more brittle that the regular lr. It currently can + be used in dce incrementally, but cannot be used in an environment + where insns are created or modified. The problem is that the + mapping of regnos to bitmap positions is relatively compact, in + that if a pseudo does not do any of the byte wise operations, only + one slot is allocated, rather than a slot for each byte. If insn + are created, where a subreg is used for a reg that had no subregs, + the mapping would be wrong. Likewise, there are no checks to see + that new pseudos have been added. These issues could be addressed + by adding a problem specific flag to not use the compact mapping, + if there was a need to do so. + ----------------------------------------------------------------------------*/ -static void -df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED) +/* Private data used to verify the solution for this problem. */ +struct df_byte_lr_problem_data { - df_note->optional_p = true; -} + /* Expanded versions of bitvectors used in lr. */ + bitmap invalidated_by_call; + bitmap hardware_regs_used; -#ifdef REG_DEAD_DEBUGGING -static void -df_print_note (const char *prefix, rtx insn, rtx note) -{ - if (dump_file) - { - fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn)); - print_rtl (dump_file, note); - fprintf (dump_file, "\n"); - } -} -#endif + /* Indexed by regno, this is true if there are subregs, extracts or + strict_low_parts for this regno. */ + bitmap needs_expansion; + /* The start position and len for each regno in the various bit + vectors. */ + unsigned int* regno_start; + unsigned int* regno_len; + /* An obstack for the bitmaps we need for this problem. */ + bitmap_obstack byte_lr_bitmaps; +}; -/* After reg-stack, the x86 floating point stack regs are difficult to - analyze because of all of the pushes, pops and rotations. Thus, we - just leave the notes alone. */ -#ifdef STACK_REGS -static inline bool -df_ignore_stack_reg (int regno) +/* Get the starting location for REGNO in the df_byte_lr bitmaps. */ + +int +df_byte_lr_get_regno_start (unsigned int regno) { - return regstack_completed - && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG); + struct df_byte_lr_problem_data *problem_data + = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;; + return problem_data->regno_start[regno]; } -#else -static inline bool -df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED) -{ - return false; + + +/* Get the len for REGNO in the df_byte_lr bitmaps. */ + +int +df_byte_lr_get_regno_len (unsigned int regno) +{ + struct df_byte_lr_problem_data *problem_data + = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;; + return problem_data->regno_len[regno]; } -#endif -/* Remove all of the REG_DEAD or REG_UNUSED notes from INSN and add - them to OLD_DEAD_NOTES and OLD_UNUSED_NOTES. */ +/* Set basic block info. */ static void -df_kill_notes (rtx insn, rtx *old_dead_notes, rtx *old_unused_notes) +df_byte_lr_set_bb_info (unsigned int index, + struct df_byte_lr_bb_info *bb_info) { - rtx *pprev = ®_NOTES (insn); - rtx link = *pprev; - rtx dead = NULL; - rtx unused = NULL; + gcc_assert (df_byte_lr); + gcc_assert (index < df_byte_lr->block_info_size); + df_byte_lr->block_info[index] = bb_info; +} - while (link) - { - switch (REG_NOTE_KIND (link)) - { - case REG_DEAD: - /* After reg-stack, we need to ignore any unused notes - for the stack registers. */ - if (df_ignore_stack_reg (REGNO (XEXP (link, 0)))) - { - pprev = &XEXP (link, 1); - link = *pprev; - } - else - { - rtx next = XEXP (link, 1); -#ifdef REG_DEAD_DEBUGGING - df_print_note ("deleting: ", insn, link); -#endif - XEXP (link, 1) = dead; - dead = link; - *pprev = link = next; - } - break; + +/* Free basic block info. */ - case REG_UNUSED: - /* After reg-stack, we need to ignore any unused notes - for the stack registers. */ - if (df_ignore_stack_reg (REGNO (XEXP (link, 0)))) - { - pprev = &XEXP (link, 1); - link = *pprev; - } - else - { - rtx next = XEXP (link, 1); -#ifdef REG_DEAD_DEBUGGING - df_print_note ("deleting: ", insn, link); -#endif - XEXP (link, 1) = unused; - unused = link; - *pprev = link = next; - } - break; - - default: - pprev = &XEXP (link, 1); - link = *pprev; - break; - } +static void +df_byte_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, + void *vbb_info) +{ + struct df_byte_lr_bb_info *bb_info = (struct df_byte_lr_bb_info *) vbb_info; + if (bb_info) + { + BITMAP_FREE (bb_info->use); + BITMAP_FREE (bb_info->def); + BITMAP_FREE (bb_info->in); + BITMAP_FREE (bb_info->out); + pool_free (df_byte_lr->block_pool, bb_info); } - - *old_dead_notes = dead; - *old_unused_notes = unused; } -/* Set a NOTE_TYPE note for REG in INSN. Try to pull it from the OLD - list, otherwise create a new one. */ +/* Check all of the refs in REF_REC to see if any of them are + extracts, subregs or strict_low_parts. */ -static inline rtx -df_set_note (enum reg_note note_type, rtx insn, rtx old, rtx reg) +static void +df_byte_lr_check_regs (df_ref *ref_rec) { - rtx this = old; - rtx prev = NULL; + struct df_byte_lr_problem_data *problem_data + = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data; - while (this) - if (XEXP (this, 0) == reg) - { - if (prev) - XEXP (prev, 1) = XEXP (this, 1); - else - old = XEXP (this, 1); - XEXP (this, 1) = REG_NOTES (insn); - REG_NOTES (insn) = this; - return old; - } - else - { - prev = this; - this = XEXP (this, 1); - } - - /* Did not find the note. */ - REG_NOTES (insn) = alloc_EXPR_LIST (note_type, reg, REG_NOTES (insn)); - return old; + for (; *ref_rec; ref_rec++) + { + df_ref ref = *ref_rec; + if (DF_REF_FLAGS_IS_SET (ref, DF_REF_SIGN_EXTRACT + | DF_REF_ZERO_EXTRACT + | DF_REF_STRICT_LOW_PART) + || GET_CODE (DF_REF_REG (ref)) == SUBREG) + bitmap_set_bit (problem_data->needs_expansion, DF_REF_REGNO (ref)); + } } -/* A subroutine of df_set_unused_notes_for_mw, with a selection of its - arguments. Return true if the register value described by MWS's - mw_reg is known to be completely unused, and if mw_reg can therefore - be used in a REG_UNUSED note. */ - -static bool -df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws, - bitmap live, bitmap artificial_uses) -{ - unsigned int r; - /* If MWS describes a partial reference, create REG_UNUSED notes for - individual hard registers. */ - if (mws->flags & DF_REF_PARTIAL) - return false; +/* Expand bitmap SRC which is indexed by regno to DEST which is indexed by + regno_start and regno_len. */ - /* Likewise if some part of the register is used. */ - for (r = mws->start_regno; r <= mws->end_regno; r++) - if (bitmap_bit_p (live, r) - || bitmap_bit_p (artificial_uses, r)) - return false; +static void +df_byte_lr_expand_bitmap (bitmap dest, bitmap src) +{ + struct df_byte_lr_problem_data *problem_data + = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data; + bitmap_iterator bi; + unsigned int i; - gcc_assert (REG_P (mws->mw_reg)); - return true; + bitmap_clear (dest); + EXECUTE_IF_SET_IN_BITMAP (src, 0, i, bi) + { + bitmap_set_range (dest, problem_data->regno_start[i], + problem_data->regno_len[i]); + } } -/* Set the REG_UNUSED notes for the multiword hardreg defs in INSN - based on the bits in LIVE. Do not generate notes for registers in - artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are - not generated if the reg is both read and written by the - instruction. -*/ -static rtx -df_set_unused_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws, - bitmap live, bitmap do_not_gen, - bitmap artificial_uses) +/* Allocate or reset bitmaps for DF_BYTE_LR blocks. The solution bits are + not touched unless the block is new. */ + +static void +df_byte_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED) { - unsigned int r; + unsigned int bb_index; + bitmap_iterator bi; + basic_block bb; + unsigned int regno; + unsigned int index = 0; + unsigned int max_reg = max_reg_num(); + struct df_byte_lr_problem_data *problem_data + = problem_data = XNEW (struct df_byte_lr_problem_data); + + df_byte_lr->problem_data = problem_data; + + if (!df_byte_lr->block_pool) + df_byte_lr->block_pool = create_alloc_pool ("df_byte_lr_block pool", + sizeof (struct df_byte_lr_bb_info), 50); + + df_grow_bb_info (df_byte_lr); + + /* Create the mapping from regnos to slots. This does not change + unless the problem is destroyed and recreated. In particular, if + we end up deleting the only insn that used a subreg, we do not + want to redo the mapping because this would invalidate everything + else. */ + + bitmap_obstack_initialize (&problem_data->byte_lr_bitmaps); + problem_data->regno_start = XNEWVEC (unsigned int, max_reg); + problem_data->regno_len = XNEWVEC (unsigned int, max_reg); + problem_data->hardware_regs_used = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps); + problem_data->invalidated_by_call = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps); + problem_data->needs_expansion = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps); -#ifdef REG_DEAD_DEBUGGING - if (dump_file) + /* Discover which regno's use subregs, extracts or + strict_low_parts. */ + FOR_EACH_BB (bb) + { + rtx insn; + FOR_BB_INSNS (bb, insn) + { + if (INSN_P (insn)) + { + struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); + df_byte_lr_check_regs (DF_INSN_INFO_DEFS (insn_info)); + df_byte_lr_check_regs (DF_INSN_INFO_USES (insn_info)); + } + } + bitmap_set_bit (df_byte_lr->out_of_date_transfer_functions, bb->index); + } + + bitmap_set_bit (df_byte_lr->out_of_date_transfer_functions, ENTRY_BLOCK); + bitmap_set_bit (df_byte_lr->out_of_date_transfer_functions, EXIT_BLOCK); + + /* Allocate the slots for each regno. */ + for (regno = 0; regno < max_reg; regno++) + { + int len; + problem_data->regno_start[regno] = index; + if (bitmap_bit_p (problem_data->needs_expansion, regno)) + len = GET_MODE_SIZE (GET_MODE (regno_reg_rtx[regno])); + else + len = 1; + + problem_data->regno_len[regno] = len; + index += len; + } + + df_byte_lr_expand_bitmap (problem_data->hardware_regs_used, + df->hardware_regs_used); + df_byte_lr_expand_bitmap (problem_data->invalidated_by_call, + regs_invalidated_by_call_regset); + + EXECUTE_IF_SET_IN_BITMAP (df_byte_lr->out_of_date_transfer_functions, 0, bb_index, bi) + { + struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index); + if (bb_info) + { + bitmap_clear (bb_info->def); + bitmap_clear (bb_info->use); + } + else + { + bb_info = (struct df_byte_lr_bb_info *) pool_alloc (df_byte_lr->block_pool); + df_byte_lr_set_bb_info (bb_index, bb_info); + bb_info->use = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps); + bb_info->def = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps); + bb_info->in = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps); + bb_info->out = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps); + } + } + + df_byte_lr->optional_p = true; +} + + +/* Reset the global solution for recalculation. */ + +static void +df_byte_lr_reset (bitmap all_blocks) +{ + unsigned int bb_index; + bitmap_iterator bi; + + EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) + { + struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index); + gcc_assert (bb_info); + bitmap_clear (bb_info->in); + bitmap_clear (bb_info->out); + } +} + + +/* Compute local live register info for basic block BB. */ + +static void +df_byte_lr_bb_local_compute (unsigned int bb_index) +{ + struct df_byte_lr_problem_data *problem_data + = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data; + basic_block bb = BASIC_BLOCK (bb_index); + struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index); + rtx insn; + df_ref *def_rec; + df_ref *use_rec; + + /* Process the registers set in an exception handler. */ + for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++) + { + df_ref def = *def_rec; + if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0) + { + unsigned int dregno = DF_REF_REGNO (def); + unsigned int start = problem_data->regno_start[dregno]; + unsigned int len = problem_data->regno_len[dregno]; + bitmap_set_range (bb_info->def, start, len); + bitmap_clear_range (bb_info->use, start, len); + } + } + + /* Process the hardware registers that are always live. */ + for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++) + { + df_ref use = *use_rec; + /* Add use to set of uses in this BB. */ + if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0) + { + unsigned int uregno = DF_REF_REGNO (use); + unsigned int start = problem_data->regno_start[uregno]; + unsigned int len = problem_data->regno_len[uregno]; + bitmap_set_range (bb_info->use, start, len); + } + } + + FOR_BB_INSNS_REVERSE (bb, insn) + { + unsigned int uid = INSN_UID (insn); + + if (!INSN_P (insn)) + continue; + + for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) + { + df_ref def = *def_rec; + /* If the def is to only part of the reg, it does + not kill the other defs that reach here. */ + if (!(DF_REF_FLAGS (def) & (DF_REF_CONDITIONAL))) + { + unsigned int dregno = DF_REF_REGNO (def); + unsigned int start = problem_data->regno_start[dregno]; + unsigned int len = problem_data->regno_len[dregno]; + unsigned int sb; + unsigned int lb; + if (!df_compute_accessed_bytes (def, DF_MM_MUST, &sb, &lb)) + { + start += sb; + len = lb - sb; + } + if (len) + { + bitmap_set_range (bb_info->def, start, len); + bitmap_clear_range (bb_info->use, start, len); + } + } + } + + for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++) + { + df_ref use = *use_rec; + unsigned int uregno = DF_REF_REGNO (use); + unsigned int start = problem_data->regno_start[uregno]; + unsigned int len = problem_data->regno_len[uregno]; + unsigned int sb; + unsigned int lb; + if (!df_compute_accessed_bytes (use, DF_MM_MAY, &sb, &lb)) + { + start += sb; + len = lb - sb; + } + /* Add use to set of uses in this BB. */ + if (len) + bitmap_set_range (bb_info->use, start, len); + } + } + + /* Process the registers set in an exception handler or the hard + frame pointer if this block is the target of a non local + goto. */ + for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++) + { + df_ref def = *def_rec; + if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) + { + unsigned int dregno = DF_REF_REGNO (def); + unsigned int start = problem_data->regno_start[dregno]; + unsigned int len = problem_data->regno_len[dregno]; + bitmap_set_range (bb_info->def, start, len); + bitmap_clear_range (bb_info->use, start, len); + } + } + +#ifdef EH_USES + /* Process the uses that are live into an exception handler. */ + for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++) + { + df_ref use = *use_rec; + /* Add use to set of uses in this BB. */ + if (DF_REF_FLAGS (use) & DF_REF_AT_TOP) + { + unsigned int uregno = DF_REF_REGNO (use); + unsigned int start = problem_data->regno_start[uregno]; + unsigned int len = problem_data->regno_len[uregno]; + bitmap_set_range (bb_info->use, start, len); + } + } +#endif +} + + +/* Compute local live register info for each basic block within BLOCKS. */ + +static void +df_byte_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED) +{ + unsigned int bb_index; + bitmap_iterator bi; + + EXECUTE_IF_SET_IN_BITMAP (df_byte_lr->out_of_date_transfer_functions, 0, bb_index, bi) + { + if (bb_index == EXIT_BLOCK) + { + /* The exit block is special for this problem and its bits are + computed from thin air. */ + struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (EXIT_BLOCK); + df_byte_lr_expand_bitmap (bb_info->use, df->exit_block_uses); + } + else + df_byte_lr_bb_local_compute (bb_index); + } + + bitmap_clear (df_byte_lr->out_of_date_transfer_functions); +} + + +/* Initialize the solution vectors. */ + +static void +df_byte_lr_init (bitmap all_blocks) +{ + unsigned int bb_index; + bitmap_iterator bi; + + EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) + { + struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index); + bitmap_copy (bb_info->in, bb_info->use); + bitmap_clear (bb_info->out); + } +} + + +/* Confluence function that processes infinite loops. This might be a + noreturn function that throws. And even if it isn't, getting the + unwind info right helps debugging. */ +static void +df_byte_lr_confluence_0 (basic_block bb) +{ + struct df_byte_lr_problem_data *problem_data + = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data; + bitmap op1 = df_byte_lr_get_bb_info (bb->index)->out; + if (bb != EXIT_BLOCK_PTR) + bitmap_copy (op1, problem_data->hardware_regs_used); +} + + +/* Confluence function that ignores fake edges. */ + +static void +df_byte_lr_confluence_n (edge e) +{ + struct df_byte_lr_problem_data *problem_data + = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data; + bitmap op1 = df_byte_lr_get_bb_info (e->src->index)->out; + bitmap op2 = df_byte_lr_get_bb_info (e->dest->index)->in; + + /* Call-clobbered registers die across exception and call edges. */ + /* ??? Abnormal call edges ignored for the moment, as this gets + confused by sibling call edges, which crashes reg-stack. */ + if (e->flags & EDGE_EH) + bitmap_ior_and_compl_into (op1, op2, problem_data->invalidated_by_call); + else + bitmap_ior_into (op1, op2); + + bitmap_ior_into (op1, problem_data->hardware_regs_used); +} + + +/* Transfer function. */ + +static bool +df_byte_lr_transfer_function (int bb_index) +{ + struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index); + bitmap in = bb_info->in; + bitmap out = bb_info->out; + bitmap use = bb_info->use; + bitmap def = bb_info->def; + + return bitmap_ior_and_compl (in, use, out, def); +} + + +/* Free all storage associated with the problem. */ + +static void +df_byte_lr_free (void) +{ + struct df_byte_lr_problem_data *problem_data + = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data; + + + if (df_byte_lr->block_info) + { + free_alloc_pool (df_byte_lr->block_pool); + df_byte_lr->block_info_size = 0; + free (df_byte_lr->block_info); + } + + BITMAP_FREE (df_byte_lr->out_of_date_transfer_functions); + bitmap_obstack_release (&problem_data->byte_lr_bitmaps); + free (problem_data->regno_start); + free (problem_data->regno_len); + free (problem_data); + free (df_byte_lr); +} + + +/* Debugging info at top of bb. */ + +static void +df_byte_lr_top_dump (basic_block bb, FILE *file) +{ + struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb->index); + if (!bb_info || !bb_info->in) + return; + + fprintf (file, ";; blr in \t"); + df_print_byte_regset (file, bb_info->in); + fprintf (file, ";; blr use \t"); + df_print_byte_regset (file, bb_info->use); + fprintf (file, ";; blr def \t"); + df_print_byte_regset (file, bb_info->def); +} + + +/* Debugging info at bottom of bb. */ + +static void +df_byte_lr_bottom_dump (basic_block bb, FILE *file) +{ + struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb->index); + if (!bb_info || !bb_info->out) + return; + + fprintf (file, ";; blr out \t"); + df_print_byte_regset (file, bb_info->out); +} + + +/* All of the information associated with every instance of the problem. */ + +static struct df_problem problem_BYTE_LR = +{ + DF_BYTE_LR, /* Problem id. */ + DF_BACKWARD, /* Direction. */ + df_byte_lr_alloc, /* Allocate the problem specific data. */ + df_byte_lr_reset, /* Reset global information. */ + df_byte_lr_free_bb_info, /* Free basic block info. */ + df_byte_lr_local_compute, /* Local compute function. */ + df_byte_lr_init, /* Init the solution specific data. */ + df_worklist_dataflow, /* Worklist solver. */ + df_byte_lr_confluence_0, /* Confluence operator 0. */ + df_byte_lr_confluence_n, /* Confluence operator n. */ + df_byte_lr_transfer_function, /* Transfer function. */ + NULL, /* Finalize function. */ + df_byte_lr_free, /* Free all of the problem information. */ + df_byte_lr_free, /* Remove this problem from the stack of dataflow problems. */ + NULL, /* Debugging. */ + df_byte_lr_top_dump, /* Debugging start block. */ + df_byte_lr_bottom_dump, /* Debugging end block. */ + NULL, /* Incremental solution verify start. */ + NULL, /* Incremental solution verify end. */ + NULL, /* Dependent problem. */ + TV_DF_BYTE_LR, /* Timing variable. */ + false /* Reset blocks on dropping out of blocks_to_analyze. */ +}; + + +/* Create a new DATAFLOW instance and add it to an existing instance + of DF. The returned structure is what is used to get at the + solution. */ + +void +df_byte_lr_add_problem (void) +{ + df_add_problem (&problem_BYTE_LR); + /* These will be initialized when df_scan_blocks processes each + block. */ + df_byte_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL); +} + + +/* Simulate the effects of the defs of INSN on LIVE. */ + +void +df_byte_lr_simulate_defs (rtx insn, bitmap live) +{ + struct df_byte_lr_problem_data *problem_data + = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data; + df_ref *def_rec; + unsigned int uid = INSN_UID (insn); + + for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) + { + df_ref def = *def_rec; + + /* If the def is to only part of the reg, it does + not kill the other defs that reach here. */ + if (!(DF_REF_FLAGS (def) & DF_REF_CONDITIONAL)) + { + unsigned int dregno = DF_REF_REGNO (def); + unsigned int start = problem_data->regno_start[dregno]; + unsigned int len = problem_data->regno_len[dregno]; + unsigned int sb; + unsigned int lb; + if (!df_compute_accessed_bytes (def, DF_MM_MUST, &sb, &lb)) + { + start += sb; + len = lb - sb; + } + + if (len) + bitmap_clear_range (live, start, len); + } + } +} + + +/* Simulate the effects of the uses of INSN on LIVE. */ + +void +df_byte_lr_simulate_uses (rtx insn, bitmap live) +{ + struct df_byte_lr_problem_data *problem_data + = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data; + df_ref *use_rec; + unsigned int uid = INSN_UID (insn); + + for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++) + { + df_ref use = *use_rec; + unsigned int uregno = DF_REF_REGNO (use); + unsigned int start = problem_data->regno_start[uregno]; + unsigned int len = problem_data->regno_len[uregno]; + unsigned int sb; + unsigned int lb; + + if (!df_compute_accessed_bytes (use, DF_MM_MAY, &sb, &lb)) + { + start += sb; + len = lb - sb; + } + + /* Add use to set of uses in this BB. */ + if (len) + bitmap_set_range (live, start, len); + } +} + + +/* Apply the artificial uses and defs at the top of BB in a forwards + direction. */ + +void +df_byte_lr_simulate_artificial_refs_at_top (basic_block bb, bitmap live) +{ + struct df_byte_lr_problem_data *problem_data + = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data; + df_ref *def_rec; +#ifdef EH_USES + df_ref *use_rec; +#endif + int bb_index = bb->index; + +#ifdef EH_USES + for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++) + { + df_ref use = *use_rec; + if (DF_REF_FLAGS (use) & DF_REF_AT_TOP) + { + unsigned int uregno = DF_REF_REGNO (use); + unsigned int start = problem_data->regno_start[uregno]; + unsigned int len = problem_data->regno_len[uregno]; + bitmap_set_range (live, start, len); + } + } +#endif + + for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++) + { + df_ref def = *def_rec; + if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) + { + unsigned int dregno = DF_REF_REGNO (def); + unsigned int start = problem_data->regno_start[dregno]; + unsigned int len = problem_data->regno_len[dregno]; + bitmap_clear_range (live, start, len); + } + } +} + + +/* Apply the artificial uses and defs at the end of BB in a backwards + direction. */ + +void +df_byte_lr_simulate_artificial_refs_at_end (basic_block bb, bitmap live) +{ + struct df_byte_lr_problem_data *problem_data + = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data; + df_ref *def_rec; + df_ref *use_rec; + int bb_index = bb->index; + + for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++) + { + df_ref def = *def_rec; + if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0) + { + unsigned int dregno = DF_REF_REGNO (def); + unsigned int start = problem_data->regno_start[dregno]; + unsigned int len = problem_data->regno_len[dregno]; + bitmap_clear_range (live, start, len); + } + } + + for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++) + { + df_ref use = *use_rec; + if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0) + { + unsigned int uregno = DF_REF_REGNO (use); + unsigned int start = problem_data->regno_start[uregno]; + unsigned int len = problem_data->regno_len[uregno]; + bitmap_set_range (live, start, len); + } + } +} + + + +/*---------------------------------------------------------------------------- + This problem computes REG_DEAD and REG_UNUSED notes. + ----------------------------------------------------------------------------*/ + +static void +df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED) +{ + df_note->optional_p = true; +} + +#ifdef REG_DEAD_DEBUGGING +static void +df_print_note (const char *prefix, rtx insn, rtx note) +{ + if (dump_file) + { + fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn)); + print_rtl (dump_file, note); + fprintf (dump_file, "\n"); + } +} +#endif + + +/* After reg-stack, the x86 floating point stack regs are difficult to + analyze because of all of the pushes, pops and rotations. Thus, we + just leave the notes alone. */ + +#ifdef STACK_REGS +static inline bool +df_ignore_stack_reg (int regno) +{ + return regstack_completed + && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG); +} +#else +static inline bool +df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED) +{ + return false; +} +#endif + + +/* Remove all of the REG_DEAD or REG_UNUSED notes from INSN and add + them to OLD_DEAD_NOTES and OLD_UNUSED_NOTES. */ + +static void +df_kill_notes (rtx insn, rtx *old_dead_notes, rtx *old_unused_notes) +{ + rtx *pprev = ®_NOTES (insn); + rtx link = *pprev; + rtx dead = NULL; + rtx unused = NULL; + + while (link) + { + switch (REG_NOTE_KIND (link)) + { + case REG_DEAD: + /* After reg-stack, we need to ignore any unused notes + for the stack registers. */ + if (df_ignore_stack_reg (REGNO (XEXP (link, 0)))) + { + pprev = &XEXP (link, 1); + link = *pprev; + } + else + { + rtx next = XEXP (link, 1); +#ifdef REG_DEAD_DEBUGGING + df_print_note ("deleting: ", insn, link); +#endif + XEXP (link, 1) = dead; + dead = link; + *pprev = link = next; + } + break; + + case REG_UNUSED: + /* After reg-stack, we need to ignore any unused notes + for the stack registers. */ + if (df_ignore_stack_reg (REGNO (XEXP (link, 0)))) + { + pprev = &XEXP (link, 1); + link = *pprev; + } + else + { + rtx next = XEXP (link, 1); +#ifdef REG_DEAD_DEBUGGING + df_print_note ("deleting: ", insn, link); +#endif + XEXP (link, 1) = unused; + unused = link; + *pprev = link = next; + } + break; + + default: + pprev = &XEXP (link, 1); + link = *pprev; + break; + } + } + + *old_dead_notes = dead; + *old_unused_notes = unused; +} + + +/* Set a NOTE_TYPE note for REG in INSN. Try to pull it from the OLD + list, otherwise create a new one. */ + +static inline rtx +df_set_note (enum reg_note note_type, rtx insn, rtx old, rtx reg) +{ + rtx curr = old; + rtx prev = NULL; + + while (curr) + if (XEXP (curr, 0) == reg) + { + if (prev) + XEXP (prev, 1) = XEXP (curr, 1); + else + old = XEXP (curr, 1); + XEXP (curr, 1) = REG_NOTES (insn); + REG_NOTES (insn) = curr; + return old; + } + else + { + prev = curr; + curr = XEXP (curr, 1); + } + + /* Did not find the note. */ + add_reg_note (insn, note_type, reg); + return old; +} + +/* A subroutine of df_set_unused_notes_for_mw, with a selection of its + arguments. Return true if the register value described by MWS's + mw_reg is known to be completely unused, and if mw_reg can therefore + be used in a REG_UNUSED note. */ + +static bool +df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws, + bitmap live, bitmap artificial_uses) +{ + unsigned int r; + + /* If MWS describes a partial reference, create REG_UNUSED notes for + individual hard registers. */ + if (mws->flags & DF_REF_PARTIAL) + return false; + + /* Likewise if some part of the register is used. */ + for (r = mws->start_regno; r <= mws->end_regno; r++) + if (bitmap_bit_p (live, r) + || bitmap_bit_p (artificial_uses, r)) + return false; + + gcc_assert (REG_P (mws->mw_reg)); + return true; +} + +/* Set the REG_UNUSED notes for the multiword hardreg defs in INSN + based on the bits in LIVE. Do not generate notes for registers in + artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are + not generated if the reg is both read and written by the + instruction. +*/ + +static rtx +df_set_unused_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws, + bitmap live, bitmap do_not_gen, + bitmap artificial_uses) +{ + unsigned int r; + +#ifdef REG_DEAD_DEBUGGING + if (dump_file) fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n", mws->start_regno, mws->end_regno); #endif @@ -2638,7 +3379,7 @@ df_set_dead_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws, LIVE. Do not generate notes for registers in ARTIFICIAL_USES. */ static rtx -df_create_unused_note (rtx insn, rtx old, struct df_ref *def, +df_create_unused_note (rtx insn, rtx old, df_ref def, bitmap live, bitmap artificial_uses) { unsigned int dregno = DF_REF_REGNO (def); @@ -2678,8 +3419,8 @@ df_note_bb_compute (unsigned int bb_index, { basic_block bb = BASIC_BLOCK (bb_index); rtx insn; - struct df_ref **def_rec; - struct df_ref **use_rec; + df_ref *def_rec; + df_ref *use_rec; bitmap_copy (live, df_get_live_out (bb)); bitmap_clear (artificial_uses); @@ -2696,7 +3437,7 @@ df_note_bb_compute (unsigned int bb_index, to begin processing. */ for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++) { - struct df_ref *def = *def_rec; + df_ref def = *def_rec; #ifdef REG_DEAD_DEBUGGING if (dump_file) fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def)); @@ -2708,7 +3449,7 @@ df_note_bb_compute (unsigned int bb_index, for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++) { - struct df_ref *use = *use_rec; + df_ref use = *use_rec; if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0) { unsigned int regno = DF_REF_REGNO (use); @@ -2757,7 +3498,7 @@ df_note_bb_compute (unsigned int bb_index, while (*mws_rec) { struct df_mw_hardreg *mws = *mws_rec; - if ((mws->type == DF_REF_REG_DEF) + if ((DF_MWS_REG_DEF_P (mws)) && !df_ignore_stack_reg (mws->start_regno)) old_unused_notes = df_set_unused_notes_for_mw (insn, old_unused_notes, @@ -2770,7 +3511,7 @@ df_note_bb_compute (unsigned int bb_index, clobber. This code is for the return. */ for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) { - struct df_ref *def = *def_rec; + df_ref def = *def_rec; unsigned int dregno = DF_REF_REGNO (def); if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)) { @@ -2791,7 +3532,7 @@ df_note_bb_compute (unsigned int bb_index, while (*mws_rec) { struct df_mw_hardreg *mws = *mws_rec; - if (mws->type == DF_REF_REG_DEF) + if (DF_MWS_REG_DEF_P (mws)) old_unused_notes = df_set_unused_notes_for_mw (insn, old_unused_notes, mws, live, do_not_gen, @@ -2801,7 +3542,7 @@ df_note_bb_compute (unsigned int bb_index, for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) { - struct df_ref *def = *def_rec; + df_ref def = *def_rec; unsigned int dregno = DF_REF_REGNO (def); old_unused_notes = df_create_unused_note (insn, old_unused_notes, @@ -2820,7 +3561,7 @@ df_note_bb_compute (unsigned int bb_index, while (*mws_rec) { struct df_mw_hardreg *mws = *mws_rec; - if ((mws->type != DF_REF_REG_DEF) + if ((DF_MWS_REG_DEF_P (mws)) && !df_ignore_stack_reg (mws->start_regno)) old_dead_notes = df_set_dead_notes_for_mw (insn, old_dead_notes, @@ -2831,7 +3572,7 @@ df_note_bb_compute (unsigned int bb_index, for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++) { - struct df_ref *use = *use_rec; + df_ref use = *use_rec; unsigned int uregno = DF_REF_REGNO (use); #ifdef REG_DEAD_DEBUGGING @@ -2968,7 +3709,6 @@ df_note_add_problem (void) DF_LR_IN. If you start at the bottom of the block use one of DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS, THEY WILL BE DESTROYED. - ----------------------------------------------------------------------------*/ @@ -2977,12 +3717,12 @@ df_note_add_problem (void) void df_simulate_find_defs (rtx insn, bitmap defs) { - struct df_ref **def_rec; + df_ref *def_rec; unsigned int uid = INSN_UID (insn); for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) { - struct df_ref *def = *def_rec; + df_ref def = *def_rec; /* If the def is to only part of the reg, it does not kill the other defs that reach here. */ if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))) @@ -2996,12 +3736,12 @@ df_simulate_find_defs (rtx insn, bitmap defs) void df_simulate_defs (rtx insn, bitmap live) { - struct df_ref **def_rec; + df_ref *def_rec; unsigned int uid = INSN_UID (insn); for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) { - struct df_ref *def = *def_rec; + df_ref def = *def_rec; unsigned int dregno = DF_REF_REGNO (def); /* If the def is to only part of the reg, it does @@ -3017,12 +3757,12 @@ df_simulate_defs (rtx insn, bitmap live) void df_simulate_uses (rtx insn, bitmap live) { - struct df_ref **use_rec; + df_ref *use_rec; unsigned int uid = INSN_UID (insn); for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++) { - struct df_ref *use = *use_rec; + df_ref use = *use_rec; /* Add use to set of uses in this BB. */ bitmap_set_bit (live, DF_REF_REGNO (use)); } @@ -3043,83 +3783,170 @@ df_simulate_fixup_sets (basic_block bb, bitmap live) } -/* Apply the artificial uses and defs at the top of BB in a forwards +/*---------------------------------------------------------------------------- + The following three functions are used only for BACKWARDS scanning: + i.e. they process the defs before the uses. + + df_simulate_initialize_backwards should be called first with a + bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT. Then + df_simulate_one_insn_backwards should be called for each insn in + the block, starting with the last on. Finally, + df_simulate_finalize_backwards can be called to get a new value + of the sets at the top of the block (this is rarely used). + ----------------------------------------------------------------------------*/ + +/* Apply the artificial uses and defs at the end of BB in a backwards direction. */ void -df_simulate_artificial_refs_at_top (basic_block bb, bitmap live) +df_simulate_initialize_backwards (basic_block bb, bitmap live) { - struct df_ref **def_rec; - struct df_ref **use_rec; + df_ref *def_rec; + df_ref *use_rec; int bb_index = bb->index; - for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++) + for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++) { - struct df_ref *use = *use_rec; - if (DF_REF_FLAGS (use) & DF_REF_AT_TOP) - bitmap_set_bit (live, DF_REF_REGNO (use)); + df_ref def = *def_rec; + if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0) + bitmap_clear_bit (live, DF_REF_REGNO (def)); } - for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++) + for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++) { - struct df_ref *def = *def_rec; - if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) - bitmap_clear_bit (live, DF_REF_REGNO (def)); + df_ref use = *use_rec; + if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0) + bitmap_set_bit (live, DF_REF_REGNO (use)); } } -/* Simulate the forwards effects of INSN on the bitmap LIVE. */ +/* Simulate the backwards effects of INSN on the bitmap LIVE. */ void -df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live) +df_simulate_one_insn_backwards (basic_block bb, rtx insn, bitmap live) { if (! INSN_P (insn)) return; - df_simulate_uses (insn, live); df_simulate_defs (insn, live); + df_simulate_uses (insn, live); df_simulate_fixup_sets (bb, live); } -/* Apply the artificial uses and defs at the end of BB in a backwards +/* Apply the artificial uses and defs at the top of BB in a backwards direction. */ void -df_simulate_artificial_refs_at_end (basic_block bb, bitmap live) +df_simulate_finalize_backwards (basic_block bb, bitmap live) { - struct df_ref **def_rec; - struct df_ref **use_rec; + df_ref *def_rec; +#ifdef EH_USES + df_ref *use_rec; +#endif int bb_index = bb->index; for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++) { - struct df_ref *def = *def_rec; - if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0) + df_ref def = *def_rec; + if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) bitmap_clear_bit (live, DF_REF_REGNO (def)); } +#ifdef EH_USES for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++) { - struct df_ref *use = *use_rec; - if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0) + df_ref use = *use_rec; + if (DF_REF_FLAGS (use) & DF_REF_AT_TOP) bitmap_set_bit (live, DF_REF_REGNO (use)); } +#endif } +/*---------------------------------------------------------------------------- + The following three functions are used only for FORWARDS scanning: + i.e. they process the defs and the REG_DEAD and REG_UNUSED notes. + Thus it is important to add the DF_NOTES problem to the stack of + problems computed before using these functions. + + df_simulate_initialize_forwards should be called first with a + bitvector copyied from the DF_LIVE_IN or DF_LR_IN. Then + df_simulate_one_insn_forwards should be called for each insn in + the block, starting with the last on. Finally, + df_simulate_finalize_forwards can be called to get a new value + of the sets at the bottom of the block (this is rarely used). + ----------------------------------------------------------------------------*/ +/* Apply the artificial uses and defs at the top of BB in a backwards + direction. */ + +void +df_simulate_initialize_forwards (basic_block bb, bitmap live) +{ + df_ref *def_rec; + int bb_index = bb->index; + + for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++) + { + df_ref def = *def_rec; + if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) + bitmap_clear_bit (live, DF_REF_REGNO (def)); + } +} /* Simulate the backwards effects of INSN on the bitmap LIVE. */ void -df_simulate_one_insn_backwards (basic_block bb, rtx insn, bitmap live) +df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live) { + rtx link; if (! INSN_P (insn)) return; - + + /* Make sure that the DF_NOTES really is an active df problem. */ + gcc_assert (df_note); + df_simulate_defs (insn, live); - df_simulate_uses (insn, live); + + /* Clear all of the registers that go dead. */ + for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) + { + switch (REG_NOTE_KIND (link)) + case REG_DEAD: + case REG_UNUSED: + { + rtx reg = XEXP (link, 0); + int regno = REGNO (reg); + if (regno < FIRST_PSEUDO_REGISTER) + { + int n = hard_regno_nregs[regno][GET_MODE (reg)]; + while (--n >= 0) + bitmap_clear_bit (live, regno + n); + } + else + bitmap_clear_bit (live, regno); + break; + default: + break; + } + } df_simulate_fixup_sets (bb, live); } +/* Apply the artificial uses and defs at the end of BB in a backwards + direction. */ + +void +df_simulate_finalize_forwards (basic_block bb, bitmap live) +{ + df_ref *def_rec; + int bb_index = bb->index; + + for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++) + { + df_ref def = *def_rec; + if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0) + bitmap_clear_bit (live, DF_REF_REGNO (def)); + } +}