X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;ds=sidebyside;f=gcc%2Fdf-problems.c;h=4afdd6fd4d0ebe89b8173735038c8ddb84b25fbb;hb=4be60539825c7a422e1351a8129df0453a4771f6;hp=ecc8eab6627f35365e42076dfd15259497feb4b2;hpb=d0802b3933a538b24bfdf5cb4b3ee44e4a1a660a;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/df-problems.c b/gcc/df-problems.c index ecc8eab6627..4afdd6fd4d0 100644 --- a/gcc/df-problems.c +++ b/gcc/df-problems.c @@ -1,7 +1,7 @@ /* Standard problems for dataflow support routines. - Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006 - Free Software Foundation, Inc. - Originally contributed by Michael P. Hayes + Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, + 2008, 2009, 2010, 2011, 2012 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) and Kenneth Zadeck (zadeck@naturalbridge.com). @@ -10,7 +10,7 @@ This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free -Software Foundation; either version 2, or (at your option) any later +Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY @@ -19,9 +19,8 @@ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING. If not, write to the Free -Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA -02110-1301, USA. */ +along with GCC; see the file COPYING3. If not see +. */ #include "config.h" #include "system.h" @@ -40,182 +39,84 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA #include "basic-block.h" #include "sbitmap.h" #include "bitmap.h" +#include "target.h" #include "timevar.h" #include "df.h" +#include "except.h" +#include "dce.h" +#include "vecprim.h" + +/* Note that turning REG_DEAD_DEBUGGING on will cause + gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints + addresses in the dumps. */ +#if 0 +#define REG_DEAD_DEBUGGING +#endif #define DF_SPARSE_THRESHOLD 32 -static bitmap seen_in_block = NULL; -static bitmap seen_in_insn = NULL; +static bitmap_head seen_in_block; +static bitmap_head seen_in_insn; /*---------------------------------------------------------------------------- Public functions access functions for the dataflow problems. ----------------------------------------------------------------------------*/ - -/* Get the instance of the problem that DFLOW is dependent on. */ - -struct dataflow * -df_get_dependent_problem (struct dataflow *dflow) -{ - struct df *df = dflow->df; - struct df_problem *dependent_problem = dflow->problem->dependent_problem; - - gcc_assert (dependent_problem); - return df->problems_by_index[dependent_problem->id]; -} - - -/* Create a du or ud chain from SRC to DST and link it into SRC. */ - -struct df_link * -df_chain_create (struct dataflow *dflow, struct df_ref *src, struct df_ref *dst) -{ - struct df_link *head = DF_REF_CHAIN (src); - struct df_link *link = pool_alloc (dflow->block_pool);; - - DF_REF_CHAIN (src) = link; - link->next = head; - link->ref = dst; - return link; -} - - -/* Delete a du or ud chain for REF. If LINK is NULL, delete all - chains for ref and check to see if the reverse chains can also be - deleted. If LINK is not NULL it must be a link off of ref. In - this case, the other end is not deleted. */ - -void -df_chain_unlink (struct dataflow *dflow, struct df_ref *ref, struct df_link *link) -{ - struct df_link *chain = DF_REF_CHAIN (ref); - if (link) - { - /* Link was the first element in the chain. */ - if (chain == link) - DF_REF_CHAIN (ref) = link->next; - else - { - /* Link is an internal element in the chain. */ - struct df_link *prev = chain; - while (chain) - { - if (chain == link) - { - prev->next = chain->next; - break; - } - prev = chain; - chain = chain->next; - } - } - pool_free (dflow->block_pool, link); - } - else - { - /* If chain is NULL here, it was because of a recursive call - when the other flavor of chains was not built. Just run thru - the entire chain calling the other side and then deleting the - link. */ - while (chain) - { - struct df_link *next = chain->next; - /* Delete the other side if it exists. */ - df_chain_unlink (dflow, chain->ref, chain); - chain = next; - } - } -} - - -/* Copy the du or ud chain starting at FROM_REF and attach it to - TO_REF. */ - -void -df_chain_copy (struct dataflow *dflow, - struct df_ref *to_ref, - struct df_link *from_ref) -{ - while (from_ref) - { - df_chain_create (dflow, to_ref, from_ref->ref); - from_ref = from_ref->next; - } -} - - -/* Get the live in set for BB no matter what problem happens to be - defined. */ +/* Get the live at out set for BB no matter what problem happens to be + defined. This function is used by the register allocators who + choose different dataflow problems depending on the optimization + level. */ bitmap -df_get_live_in (struct df *df, basic_block bb) +df_get_live_out (basic_block bb) { - gcc_assert (df->problems_by_index[DF_LR]); + gcc_assert (df_lr); - if (df->problems_by_index[DF_UREC]) - return DF_RA_LIVE_IN (df, bb); - else if (df->problems_by_index[DF_UR]) - return DF_LIVE_IN (df, bb); - else - return DF_UPWARD_LIVE_IN (df, bb); + if (df_live) + return DF_LIVE_OUT (bb); + else + return DF_LR_OUT (bb); } - -/* Get the live out set for BB no matter what problem happens to be - defined. */ +/* Get the live at in set for BB no matter what problem happens to be + defined. This function is used by the register allocators who + choose different dataflow problems depending on the optimization + level. */ bitmap -df_get_live_out (struct df *df, basic_block bb) +df_get_live_in (basic_block bb) { - gcc_assert (df->problems_by_index[DF_LR]); + gcc_assert (df_lr); - if (df->problems_by_index[DF_UREC]) - return DF_RA_LIVE_OUT (df, bb); - else if (df->problems_by_index[DF_UR]) - return DF_LIVE_OUT (df, bb); - else - return DF_UPWARD_LIVE_OUT (df, bb); + if (df_live) + return DF_LIVE_IN (bb); + else + return DF_LR_IN (bb); } - /*---------------------------------------------------------------------------- Utility functions. ----------------------------------------------------------------------------*/ /* Generic versions to get the void* version of the block info. Only - used inside the problem instace vectors. */ - -/* Grow the bb_info array. */ - -void -df_grow_bb_info (struct dataflow *dflow) -{ - unsigned int new_size = last_basic_block + 1; - if (dflow->block_info_size < new_size) - { - new_size += new_size / 4; - dflow->block_info = xrealloc (dflow->block_info, - new_size *sizeof (void*)); - memset (dflow->block_info + dflow->block_info_size, 0, - (new_size - dflow->block_info_size) *sizeof (void *)); - dflow->block_info_size = new_size; - } -} + used inside the problem instance vectors. */ /* Dump a def-use or use-def chain for REF to FILE. */ void -df_chain_dump (struct df *df ATTRIBUTE_UNUSED, struct df_link *link, FILE *file) +df_chain_dump (struct df_link *link, FILE *file) { fprintf (file, "{ "); for (; link; link = link->next) { fprintf (file, "%c%d(bb %d insn %d) ", - DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u', + DF_REF_REG_DEF_P (link->ref) + ? 'd' + : (DF_REF_FLAGS (link->ref) & DF_REF_IN_NOTE) ? 'e' : '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, "}"); } @@ -223,458 +124,448 @@ df_chain_dump (struct df *df ATTRIBUTE_UNUSED, struct df_link *link, FILE *file) /* Print some basic block info as part of df_dump. */ -void +void df_print_bb_index (basic_block bb, FILE *file) { edge e; edge_iterator ei; - fprintf (file, "( "); + fprintf (file, "\n( "); FOR_EACH_EDGE (e, ei, bb->preds) { basic_block pred = e->src; - fprintf (file, "%d ", pred->index); - } + fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : ""); + } fprintf (file, ")->[%d]->( ", bb->index); FOR_EACH_EDGE (e, ei, bb->succs) { basic_block succ = e->dest; - fprintf (file, "%d ", succ->index); - } - fprintf (file, ")\n"); -} - - -/* Return the set of reference ids in CHAIN, caching the result in *BMAP. */ - -static inline bitmap -df_ref_bitmap (bitmap *maps, unsigned int regno, int start, int count) -{ - bitmap ids = maps[regno]; - if (!ids) - { - unsigned int i; - unsigned int end = start + count;; - ids = BITMAP_ALLOC (NULL); - maps[regno] = ids; - for (i = start; i < end; i++) - bitmap_set_bit (ids, i); + fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : ""); } - return ids; -} - - -/* Make sure that the seen_in_insn and seen_in_block sbitmaps are set - up correctly. */ - -static void -df_set_seen (void) -{ - seen_in_block = BITMAP_ALLOC (NULL); - seen_in_insn = BITMAP_ALLOC (NULL); -} - - -static void -df_unset_seen (void) -{ - BITMAP_FREE (seen_in_block); - BITMAP_FREE (seen_in_insn); + fprintf (file, ")\n"); } - /*---------------------------------------------------------------------------- - REACHING USES + REACHING DEFINITIONS - Find the locations in the function where each use site for a pseudo - can reach backwards. + Find the locations in the function where each definition site for a + pseudo reaches. In and out bitvectors are built for each basic + block. The id field in the ref is used to index into these sets. + See df.h for details. + ----------------------------------------------------------------------------*/ -----------------------------------------------------------------------------*/ +/* This problem plays a large number of games for the sake of + efficiency. -struct df_ru_problem_data -{ - bitmap *use_sites; /* Bitmap of uses for each pseudo. */ - unsigned int use_sites_size; /* Size of use_sites. */ - /* The set of defs to regs invalidated by call. */ - bitmap sparse_invalidated_by_call; - /* The set of defs to regs invalidate by call for ru. */ - bitmap dense_invalidated_by_call; -}; + 1) The order of the bits in the bitvectors. After the scanning + phase, all of the defs are sorted. All of the defs for the reg 0 + are first, followed by all defs for reg 1 and so on. -/* Get basic block info. */ + 2) There are two kill sets, one if the number of defs is less or + equal to DF_SPARSE_THRESHOLD and another if the number of defs is + greater. -struct df_ru_bb_info * -df_ru_get_bb_info (struct dataflow *dflow, unsigned int index) -{ - return (struct df_ru_bb_info *) dflow->block_info[index]; -} + <= : Data is built directly in the kill set. + > : One level of indirection is used to keep from generating long + strings of 1 bits in the kill sets. Bitvectors that are indexed + by the regnum are used to represent that there is a killing def + for the register. The confluence and transfer functions use + these along with the bitmap_clear_range call to remove ranges of + bits without actually generating a knockout vector. -/* Set basic block info. */ + The kill and sparse_kill and the dense_invalidated_by_call and + sparse_invalidated_by_call both play this game. */ -static void -df_ru_set_bb_info (struct dataflow *dflow, unsigned int index, - struct df_ru_bb_info *bb_info) +/* Private data used to compute the solution for this problem. These + data structures are not accessible outside of this module. */ +struct df_rd_problem_data { - dflow->block_info[index] = bb_info; -} + /* The set of defs to regs invalidated by call. */ + bitmap_head sparse_invalidated_by_call; + /* The set of defs to regs invalidate by call for rd. */ + bitmap_head dense_invalidated_by_call; + /* An obstack for the bitmaps we need for this problem. */ + bitmap_obstack rd_bitmaps; +}; /* Free basic block info. */ static void -df_ru_free_bb_info (struct dataflow *dflow, - basic_block bb ATTRIBUTE_UNUSED, +df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, void *vbb_info) { - struct df_ru_bb_info *bb_info = (struct df_ru_bb_info *) vbb_info; + struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info; 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); - pool_free (dflow->block_pool, bb_info); + bitmap_clear (&bb_info->kill); + bitmap_clear (&bb_info->sparse_kill); + bitmap_clear (&bb_info->gen); + bitmap_clear (&bb_info->in); + bitmap_clear (&bb_info->out); } } -/* Allocate or reset bitmaps for DFLOW blocks. The solution bits are +/* Allocate or reset bitmaps for DF_RD blocks. The solution bits are not touched unless the block is new. */ -static void -df_ru_alloc (struct dataflow *dflow, bitmap blocks_to_rescan) +static void +df_rd_alloc (bitmap all_blocks) { unsigned int bb_index; bitmap_iterator bi; - unsigned int reg_size = max_reg_num (); - - if (! dflow->block_pool) - dflow->block_pool = create_alloc_pool ("df_ru_block pool", - sizeof (struct df_ru_bb_info), 50); + struct df_rd_problem_data *problem_data; - if (dflow->problem_data) + if (df_rd->problem_data) { - unsigned int i; - struct df_ru_problem_data *problem_data = - (struct df_ru_problem_data *) dflow->problem_data; - - for (i = 0; i < problem_data->use_sites_size; i++) - { - bitmap bm = problem_data->use_sites[i]; - if (bm) - { - BITMAP_FREE (bm); - problem_data->use_sites[i] = NULL; - } - } - - if (problem_data->use_sites_size < reg_size) - { - problem_data->use_sites - = xrealloc (problem_data->use_sites, reg_size * sizeof (bitmap)); - memset (problem_data->use_sites + problem_data->use_sites_size, 0, - (reg_size - problem_data->use_sites_size) * sizeof (bitmap)); - problem_data->use_sites_size = reg_size; - } - - bitmap_clear (problem_data->sparse_invalidated_by_call); - bitmap_clear (problem_data->dense_invalidated_by_call); + problem_data = (struct df_rd_problem_data *) df_rd->problem_data; + bitmap_clear (&problem_data->sparse_invalidated_by_call); + bitmap_clear (&problem_data->dense_invalidated_by_call); } - else + else { - struct df_ru_problem_data *problem_data = - xmalloc (sizeof (struct df_ru_problem_data)); - dflow->problem_data = problem_data; - - problem_data->use_sites = xcalloc (reg_size, sizeof (bitmap)); - problem_data->use_sites_size = reg_size; - problem_data->sparse_invalidated_by_call = BITMAP_ALLOC (NULL); - problem_data->dense_invalidated_by_call = BITMAP_ALLOC (NULL); + problem_data = XNEW (struct df_rd_problem_data); + df_rd->problem_data = problem_data; + + bitmap_obstack_initialize (&problem_data->rd_bitmaps); + bitmap_initialize (&problem_data->sparse_invalidated_by_call, + &problem_data->rd_bitmaps); + bitmap_initialize (&problem_data->dense_invalidated_by_call, + &problem_data->rd_bitmaps); } - df_grow_bb_info (dflow); + df_grow_bb_info (df_rd); - /* Because of the clustering of all def sites for the same pseudo, + /* Because of the clustering of all use sites for the same pseudo, we have to process all of the blocks before doing the analysis. */ - EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi) + EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) { - struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb_index); - if (bb_info) - { - bitmap_clear (bb_info->kill); - bitmap_clear (bb_info->sparse_kill); - bitmap_clear (bb_info->gen); + struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index); + + /* When bitmaps are already initialized, just clear them. */ + if (bb_info->kill.obstack) + { + bitmap_clear (&bb_info->kill); + bitmap_clear (&bb_info->sparse_kill); + bitmap_clear (&bb_info->gen); } else - { - bb_info = (struct df_ru_bb_info *) pool_alloc (dflow->block_pool); - df_ru_set_bb_info (dflow, bb_index, bb_info); - bb_info->kill = BITMAP_ALLOC (NULL); - bb_info->sparse_kill = BITMAP_ALLOC (NULL); - bb_info->gen = BITMAP_ALLOC (NULL); - bb_info->in = BITMAP_ALLOC (NULL); - bb_info->out = BITMAP_ALLOC (NULL); + { + bitmap_initialize (&bb_info->kill, &problem_data->rd_bitmaps); + bitmap_initialize (&bb_info->sparse_kill, &problem_data->rd_bitmaps); + bitmap_initialize (&bb_info->gen, &problem_data->rd_bitmaps); + bitmap_initialize (&bb_info->in, &problem_data->rd_bitmaps); + bitmap_initialize (&bb_info->out, &problem_data->rd_bitmaps); } } + df_rd->optional_p = true; } -/* Process a list of DEFs for df_ru_bb_local_compute. */ +/* Add the effect of the top artificial defs of BB to the reaching definitions + bitmap LOCAL_RD. */ -static void -df_ru_bb_local_compute_process_def (struct dataflow *dflow, - struct df_ru_bb_info *bb_info, - struct df_ref *def) +void +df_rd_simulate_artificial_defs_at_top (basic_block bb, bitmap local_rd) { - struct df *df = dflow->df; - while (def) + int bb_index = bb->index; + df_ref *def_rec; + for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++) { - unsigned int regno = DF_REF_REGNO (def); - unsigned int begin = DF_REG_USE_GET (df, regno)->begin; - unsigned int n_uses = DF_REG_USE_GET (df, regno)->n_refs; - if (!bitmap_bit_p (seen_in_block, regno)) + df_ref def = *def_rec; + if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) { - /* The first def for regno, causes the kill info to be - generated and the gen information to cleared. */ - if (!bitmap_bit_p (seen_in_insn, regno)) - { - if (n_uses > DF_SPARSE_THRESHOLD) - { - bitmap_set_bit (bb_info->sparse_kill, regno); - bitmap_clear_range (bb_info->gen, begin, n_uses); - } - else - { - struct df_ru_problem_data *problem_data = - (struct df_ru_problem_data *) dflow->problem_data; - bitmap uses = - df_ref_bitmap (problem_data->use_sites, regno, - begin, n_uses); - bitmap_ior_into (bb_info->kill, uses); - bitmap_and_compl_into (bb_info->gen, uses); - } - } - bitmap_set_bit (seen_in_insn, regno); + 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)); } - def = def->next_ref; } } +/* Add the effect of the defs of INSN to the reaching definitions bitmap + LOCAL_RD. */ -/* Process a list of USEs for df_ru_bb_local_compute. */ +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_ru_bb_local_compute_process_use (struct df_ru_bb_info *bb_info, - struct df_ref *use, - enum df_ref_flags top_flag) +df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info, + df_ref *def_rec, + int top_flag) { - while (use) + while (*def_rec) { - if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP)) + df_ref def = *def_rec; + if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP)) { - /* Add use to set of gens in this BB unless we have seen a - def in a previous instruction. */ - unsigned int regno = DF_REF_REGNO (use); - if (!bitmap_bit_p (seen_in_block, regno)) - bitmap_set_bit (bb_info->gen, DF_REF_ID (use)); + unsigned int regno = DF_REF_REGNO (def); + unsigned int begin = DF_DEFS_BEGIN (regno); + unsigned int n_defs = DF_DEFS_COUNT (regno); + + if ((!(df->changeable_flags & DF_NO_HARD_REGS)) + || (regno >= FIRST_PSEUDO_REGISTER)) + { + /* Only the last def(s) for a regno in the block has any + effect. */ + if (!bitmap_bit_p (&seen_in_block, regno)) + { + /* The first def for regno in insn gets to knock out the + defs from other instructions. */ + if ((!bitmap_bit_p (&seen_in_insn, regno)) + /* If the def is to only part of the reg, it does + not kill the other defs that reach here. */ + && (!(DF_REF_FLAGS (def) & + (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER)))) + { + if (n_defs > DF_SPARSE_THRESHOLD) + { + bitmap_set_bit (&bb_info->sparse_kill, regno); + bitmap_clear_range(&bb_info->gen, begin, n_defs); + } + else + { + bitmap_set_range (&bb_info->kill, begin, n_defs); + bitmap_clear_range (&bb_info->gen, begin, n_defs); + } + } + + bitmap_set_bit (&seen_in_insn, regno); + /* All defs for regno in the instruction may be put into + the gen set. */ + if (!(DF_REF_FLAGS (def) + & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))) + bitmap_set_bit (&bb_info->gen, DF_REF_ID (def)); + } + } } - use = use->next_ref; + def_rec++; } } -/* Compute local reaching use (upward exposed use) info for basic - block BB. USE_INFO->REGS[R] caches the set of uses for register R. */ +/* Compute local reaching def info for basic block BB. */ + static void -df_ru_bb_local_compute (struct dataflow *dflow, unsigned int bb_index) +df_rd_bb_local_compute (unsigned int bb_index) { - struct df *df = dflow->df; basic_block bb = BASIC_BLOCK (bb_index); - struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb_index); + struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index); rtx insn; - /* Set when a def for regno is seen. */ - bitmap_clear (seen_in_block); - bitmap_clear (seen_in_insn); - -#ifdef EH_USES - /* Variables defined in the prolog that are used by the exception - handler. */ - df_ru_bb_local_compute_process_use (bb_info, - df_get_artificial_uses (df, bb_index), - DF_REF_AT_TOP); -#endif + bitmap_clear (&seen_in_block); + bitmap_clear (&seen_in_insn); - /* Process the artificial defs first since these are at the top of - the block. */ - df_ru_bb_local_compute_process_def (dflow, bb_info, - df_get_artificial_defs (df, bb_index)); + /* Artificials are only hard regs. */ + if (!(df->changeable_flags & DF_NO_HARD_REGS)) + df_rd_bb_local_compute_process_def (bb_info, + df_get_artificial_defs (bb_index), + 0); - FOR_BB_INSNS (bb, insn) + FOR_BB_INSNS_REVERSE (bb, insn) { unsigned int uid = INSN_UID (insn); - if (! INSN_P (insn)) - continue; - df_ru_bb_local_compute_process_def (dflow, bb_info, - DF_INSN_UID_GET (df, uid)->defs); + if (!INSN_P (insn)) + continue; - /* The use processing must happen after the defs processing even - though the uses logically happen first since the defs clear - the gen set. Otherwise, a use for regno occuring in the same - instruction as a def for regno would be cleared. */ - df_ru_bb_local_compute_process_use (bb_info, - DF_INSN_UID_GET (df, uid)->uses, 0); + df_rd_bb_local_compute_process_def (bb_info, + DF_INSN_UID_DEFS (uid), 0); - bitmap_ior_into (seen_in_block, seen_in_insn); - bitmap_clear (seen_in_insn); + /* This complex dance with the two bitmaps is required because + instructions can assign twice to the same pseudo. This + generally happens with calls that will have one def for the + result and another def for the clobber. If only one vector + is used and the clobber goes first, the result will be + lost. */ + bitmap_ior_into (&seen_in_block, &seen_in_insn); + bitmap_clear (&seen_in_insn); } - /* Process the hardware registers that are always live. */ - df_ru_bb_local_compute_process_use (bb_info, - df_get_artificial_uses (df, bb_index), 0); + /* Process the artificial defs at the top of the block last since we + are going backwards through the block and these are logically at + the start. */ + if (!(df->changeable_flags & DF_NO_HARD_REGS)) + df_rd_bb_local_compute_process_def (bb_info, + df_get_artificial_defs (bb_index), + DF_REF_AT_TOP); } -/* Compute local reaching use (upward exposed use) info for each basic - block within BLOCKS. */ +/* Compute local reaching def info for each basic block within BLOCKS. */ + static void -df_ru_local_compute (struct dataflow *dflow, - bitmap all_blocks, - bitmap rescan_blocks ATTRIBUTE_UNUSED) +df_rd_local_compute (bitmap all_blocks) { - struct df *df = dflow->df; unsigned int bb_index; bitmap_iterator bi; unsigned int regno; - struct df_ru_problem_data *problem_data = - (struct df_ru_problem_data *) dflow->problem_data; - bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call; - bitmap dense_invalidated = problem_data->dense_invalidated_by_call; + struct df_rd_problem_data *problem_data + = (struct df_rd_problem_data *) df_rd->problem_data; + bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_call; + bitmap dense_invalidated = &problem_data->dense_invalidated_by_call; - df_set_seen (); + bitmap_initialize (&seen_in_block, &df_bitmap_obstack); + bitmap_initialize (&seen_in_insn, &df_bitmap_obstack); - if (!df->use_info.refs_organized) - df_reorganize_refs (&df->use_info); + df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG); EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) { - df_ru_bb_local_compute (dflow, bb_index); + df_rd_bb_local_compute (bb_index); } - + /* 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) { - struct df_reg_info *reg_info = DF_REG_USE_GET (df, regno); - if (reg_info->n_refs > DF_SPARSE_THRESHOLD) + if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD) bitmap_set_bit (sparse_invalidated, regno); else - { - bitmap defs = df_ref_bitmap (problem_data->use_sites, regno, - reg_info->begin, reg_info->n_refs); - bitmap_ior_into (dense_invalidated, defs); - } + bitmap_set_range (dense_invalidated, + DF_DEFS_BEGIN (regno), + DF_DEFS_COUNT (regno)); } - df_unset_seen (); + bitmap_clear (&seen_in_block); + bitmap_clear (&seen_in_insn); } /* Initialize the solution bit vectors for problem. */ -static void -df_ru_init_solution (struct dataflow *dflow, bitmap all_blocks) +static void +df_rd_init_solution (bitmap all_blocks) { unsigned int bb_index; bitmap_iterator bi; EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) { - struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb_index); - bitmap_copy (bb_info->in, bb_info->gen); - bitmap_clear (bb_info->out); + struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index); + + bitmap_copy (&bb_info->out, &bb_info->gen); + bitmap_clear (&bb_info->in); } } +/* In of target gets or of out of source. */ -/* Out of target gets or of in of source. */ - -static void -df_ru_confluence_n (struct dataflow *dflow, edge e) +static bool +df_rd_confluence_n (edge e) { - bitmap op1 = df_ru_get_bb_info (dflow, e->src->index)->out; - bitmap op2 = df_ru_get_bb_info (dflow, e->dest->index)->in; + bitmap op1 = &df_rd_get_bb_info (e->dest->index)->in; + bitmap op2 = &df_rd_get_bb_info (e->src->index)->out; + bool changed = false; + + if (e->flags & EDGE_FAKE) + return false; if (e->flags & EDGE_EH) { - struct df_ru_problem_data *problem_data = - (struct df_ru_problem_data *) dflow->problem_data; - bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call; - bitmap dense_invalidated = problem_data->dense_invalidated_by_call; - struct df *df = dflow->df; + struct df_rd_problem_data *problem_data + = (struct df_rd_problem_data *) df_rd->problem_data; + bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_call; + bitmap dense_invalidated = &problem_data->dense_invalidated_by_call; bitmap_iterator bi; unsigned int regno; - bitmap tmp = BITMAP_ALLOC (NULL); + bitmap_head tmp; - bitmap_copy (tmp, op2); - bitmap_and_compl_into (tmp, dense_invalidated); + bitmap_initialize (&tmp, &df_bitmap_obstack); + bitmap_copy (&tmp, op2); + bitmap_and_compl_into (&tmp, dense_invalidated); EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi) - { - bitmap_clear_range (tmp, - DF_REG_USE_GET (df, regno)->begin, - DF_REG_USE_GET (df, regno)->n_refs); + { + bitmap_clear_range (&tmp, + DF_DEFS_BEGIN (regno), + DF_DEFS_COUNT (regno)); } - bitmap_ior_into (op1, tmp); - BITMAP_FREE (tmp); + changed |= bitmap_ior_into (op1, &tmp); + bitmap_clear (&tmp); + return changed; } else - bitmap_ior_into (op1, op2); + return bitmap_ior_into (op1, op2); } /* Transfer function. */ static bool -df_ru_transfer_function (struct dataflow *dflow, int bb_index) +df_rd_transfer_function (int bb_index) { - struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb_index); + struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index); unsigned int regno; bitmap_iterator bi; - bitmap in = bb_info->in; - bitmap out = bb_info->out; - bitmap gen = bb_info->gen; - bitmap kill = bb_info->kill; - bitmap sparse_kill = bb_info->sparse_kill; + bitmap in = &bb_info->in; + bitmap out = &bb_info->out; + bitmap gen = &bb_info->gen; + bitmap kill = &bb_info->kill; + bitmap sparse_kill = &bb_info->sparse_kill; if (bitmap_empty_p (sparse_kill)) - return bitmap_ior_and_compl (in, gen, out, kill); - else + return bitmap_ior_and_compl (out, gen, in, kill); + else { - struct df *df = dflow->df; + struct df_rd_problem_data *problem_data; bool changed = false; - bitmap tmp = BITMAP_ALLOC (NULL); - bitmap_copy (tmp, in); + bitmap_head tmp; + + /* Note that TMP is _not_ a temporary bitmap if we end up replacing + OUT with TMP. Therefore, allocate TMP in the RD bitmaps obstack. */ + problem_data = (struct df_rd_problem_data *) df_rd->problem_data; + bitmap_initialize (&tmp, &problem_data->rd_bitmaps); + + bitmap_copy (&tmp, in); EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi) { - bitmap_clear_range (tmp, - DF_REG_USE_GET (df, regno)->begin, - DF_REG_USE_GET (df, regno)->n_refs); + bitmap_clear_range (&tmp, + DF_DEFS_BEGIN (regno), + DF_DEFS_COUNT (regno)); } - bitmap_and_compl_into (tmp, kill); - bitmap_ior_into (tmp, gen); - changed = !bitmap_equal_p (tmp, in); + bitmap_and_compl_into (&tmp, kill); + bitmap_ior_into (&tmp, gen); + changed = !bitmap_equal_p (&tmp, out); if (changed) { - BITMAP_FREE (out); - bb_info->in = tmp; + bitmap_clear (out); + bb_info->out = tmp; } - else - BITMAP_FREE (tmp); + else + bitmap_clear (&tmp); return changed; } } @@ -683,491 +574,470 @@ df_ru_transfer_function (struct dataflow *dflow, int bb_index) /* Free all storage associated with the problem. */ static void -df_ru_free (struct dataflow *dflow) +df_rd_free (void) { - unsigned int i; - struct df_ru_problem_data *problem_data = - (struct df_ru_problem_data *) dflow->problem_data; + struct df_rd_problem_data *problem_data + = (struct df_rd_problem_data *) df_rd->problem_data; if (problem_data) { - for (i = 0; i < dflow->block_info_size; i++) - { - struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, 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 (dflow->block_pool); - - for (i = 0; i < problem_data->use_sites_size; i++) - { - bitmap bm = problem_data->use_sites[i]; - if (bm) - BITMAP_FREE (bm); - } - - free (problem_data->use_sites); - BITMAP_FREE (problem_data->sparse_invalidated_by_call); - BITMAP_FREE (problem_data->dense_invalidated_by_call); - - dflow->block_info_size = 0; - free (dflow->block_info); - free (dflow->problem_data); + bitmap_obstack_release (&problem_data->rd_bitmaps); + + df_rd->block_info_size = 0; + free (df_rd->block_info); + df_rd->block_info = NULL; + free (df_rd->problem_data); } - free (dflow); + free (df_rd); } /* Debugging info. */ static void -df_ru_dump (struct dataflow *dflow, FILE *file) +df_rd_start_dump (FILE *file) { - basic_block bb; - struct df *df = dflow->df; - struct df_ru_problem_data *problem_data = - (struct df_ru_problem_data *) dflow->problem_data; - unsigned int m = max_reg_num (); + struct df_rd_problem_data *problem_data + = (struct df_rd_problem_data *) df_rd->problem_data; + unsigned int m = DF_REG_SIZE(df); unsigned int regno; - fprintf (file, "Reaching uses:\n"); + if (!df_rd->block_info) + return; + + fprintf (file, ";; Reaching defs:\n\n"); fprintf (file, " sparse invalidated \t"); - dump_bitmap (file, problem_data->sparse_invalidated_by_call); + dump_bitmap (file, &problem_data->sparse_invalidated_by_call); fprintf (file, " dense invalidated \t"); - dump_bitmap (file, problem_data->dense_invalidated_by_call); - + dump_bitmap (file, &problem_data->dense_invalidated_by_call); + for (regno = 0; regno < m; regno++) - if (DF_REG_USE_GET (df, regno)->n_refs) - fprintf (file, "%d[%d,%d] ", regno, - DF_REG_USE_GET (df, regno)->begin, - DF_REG_USE_GET (df, regno)->n_refs); + if (DF_DEFS_COUNT (regno)) + fprintf (file, "%d[%d,%d] ", regno, + DF_DEFS_BEGIN (regno), + DF_DEFS_COUNT (regno)); fprintf (file, "\n"); - FOR_ALL_BB (bb) - { - struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb->index); - df_print_bb_index (bb, file); - - if (! bb_info->in) - continue; - - fprintf (file, " in \t"); - dump_bitmap (file, bb_info->in); - fprintf (file, " gen \t"); - dump_bitmap (file, bb_info->gen); - fprintf (file, " kill\t"); - dump_bitmap (file, bb_info->kill); - fprintf (file, " out \t"); - dump_bitmap (file, bb_info->out); - } } -/* All of the information associated with every instance of the problem. */ -static struct df_problem problem_RU = +/* Debugging info at top of bb. */ + +static void +df_rd_top_dump (basic_block bb, FILE *file) { - DF_RU, /* Problem id. */ - DF_BACKWARD, /* Direction. */ - df_ru_alloc, /* Allocate the problem specific data. */ - df_ru_free_bb_info, /* Free basic block info. */ - df_ru_local_compute, /* Local compute function. */ - df_ru_init_solution, /* Init the solution specific data. */ - df_iterative_dataflow, /* Iterative solver. */ - NULL, /* Confluence operator 0. */ - df_ru_confluence_n, /* Confluence operator n. */ - df_ru_transfer_function, /* Transfer function. */ - NULL, /* Finalize function. */ - df_ru_free, /* Free all of the problem information. */ - df_ru_dump, /* Debugging. */ - NULL /* Dependent problem. */ -}; + struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index); + if (!bb_info) + return; + fprintf (file, ";; rd in \t(%d)\n", (int) bitmap_count_bits (&bb_info->in)); + dump_bitmap (file, &bb_info->in); + fprintf (file, ";; rd gen \t(%d)\n", (int) bitmap_count_bits (&bb_info->gen)); + dump_bitmap (file, &bb_info->gen); + fprintf (file, ";; rd kill\t(%d)\n", (int) bitmap_count_bits (&bb_info->kill)); + dump_bitmap (file, &bb_info->kill); +} -/* 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. */ +/* Debugging info at top of bb. */ -struct dataflow * -df_ru_add_problem (struct df *df) +static void +df_rd_bottom_dump (basic_block bb, FILE *file) { - return df_add_problem (df, &problem_RU); -} + struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index); + if (!bb_info) + return; - -/*---------------------------------------------------------------------------- - REACHING DEFINITIONS + fprintf (file, ";; rd out \t(%d)\n", (int) bitmap_count_bits (&bb_info->out)); + dump_bitmap (file, &bb_info->out); +} - Find the locations in the function where each definition site for a - pseudo reaches. -----------------------------------------------------------------------------*/ +/* All of the information associated with every instance of the problem. */ -struct df_rd_problem_data +static struct df_problem problem_RD = { - bitmap *def_sites; /* Bitmap of defs for each pseudo. */ - unsigned int def_sites_size; /* Size of def_sites. */ - /* The set of defs to regs invalidated by call. */ - bitmap sparse_invalidated_by_call; - /* The set of defs to regs invalidate by call for ru. */ - bitmap dense_invalidated_by_call; + DF_RD, /* Problem id. */ + DF_FORWARD, /* Direction. */ + df_rd_alloc, /* Allocate the problem specific data. */ + NULL, /* Reset global information. */ + df_rd_free_bb_info, /* Free basic block info. */ + df_rd_local_compute, /* Local compute function. */ + df_rd_init_solution, /* Init the solution specific data. */ + df_worklist_dataflow, /* Worklist solver. */ + NULL, /* Confluence operator 0. */ + df_rd_confluence_n, /* Confluence operator n. */ + df_rd_transfer_function, /* Transfer function. */ + NULL, /* Finalize function. */ + df_rd_free, /* Free all of the problem information. */ + df_rd_free, /* Remove this problem from the stack of dataflow problems. */ + df_rd_start_dump, /* Debugging. */ + df_rd_top_dump, /* Debugging start block. */ + df_rd_bottom_dump, /* Debugging end block. */ + NULL, /* Incremental solution verify start. */ + NULL, /* Incremental solution verify end. */ + NULL, /* Dependent problem. */ + sizeof (struct df_rd_bb_info),/* Size of entry of block_info array. */ + TV_DF_RD, /* Timing variable. */ + true /* Reset blocks on dropping out of blocks_to_analyze. */ }; -/* Get basic block info. */ -struct df_rd_bb_info * -df_rd_get_bb_info (struct dataflow *dflow, unsigned int index) + +/* Create a new RD instance and add it to the existing instance + of DF. */ + +void +df_rd_add_problem (void) { - return (struct df_rd_bb_info *) dflow->block_info[index]; + df_add_problem (&problem_RD); } -/* Set basic block info. */ + +/*---------------------------------------------------------------------------- + LIVE REGISTERS -static void -df_rd_set_bb_info (struct dataflow *dflow, unsigned int index, - struct df_rd_bb_info *bb_info) -{ - dflow->block_info[index] = bb_info; -} + 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 regno is used to index into these sets. + See df.h for details. + ----------------------------------------------------------------------------*/ +/* Private data used to verify the solution for this problem. */ +struct df_lr_problem_data +{ + bitmap_head *in; + bitmap_head *out; + /* An obstack for the bitmaps we need for this problem. */ + bitmap_obstack lr_bitmaps; +}; /* Free basic block info. */ static void -df_rd_free_bb_info (struct dataflow *dflow, - basic_block bb ATTRIBUTE_UNUSED, +df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, void *vbb_info) { - struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info; + struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info; 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); - pool_free (dflow->block_pool, bb_info); + bitmap_clear (&bb_info->use); + bitmap_clear (&bb_info->def); + bitmap_clear (&bb_info->in); + bitmap_clear (&bb_info->out); } } -/* Allocate or reset bitmaps for DFLOW blocks. The solution bits are +/* Allocate or reset bitmaps for DF_LR blocks. The solution bits are not touched unless the block is new. */ -static void -df_rd_alloc (struct dataflow *dflow, bitmap blocks_to_rescan) +static void +df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED) { unsigned int bb_index; bitmap_iterator bi; - unsigned int reg_size = max_reg_num (); - - if (! dflow->block_pool) - dflow->block_pool = create_alloc_pool ("df_rd_block pool", - sizeof (struct df_rd_bb_info), 50); + struct df_lr_problem_data *problem_data; - if (dflow->problem_data) + df_grow_bb_info (df_lr); + if (df_lr->problem_data) + problem_data = (struct df_lr_problem_data *) df_lr->problem_data; + else { - unsigned int i; - struct df_rd_problem_data *problem_data = - (struct df_rd_problem_data *) dflow->problem_data; + problem_data = XNEW (struct df_lr_problem_data); + df_lr->problem_data = problem_data; - for (i = 0; i < problem_data->def_sites_size; i++) - { - bitmap bm = problem_data->def_sites[i]; - if (bm) - { - BITMAP_FREE (bm); - problem_data->def_sites[i] = NULL; - } - } - - if (problem_data->def_sites_size < reg_size) - { - problem_data->def_sites - = xrealloc (problem_data->def_sites, reg_size *sizeof (bitmap)); - memset (problem_data->def_sites + problem_data->def_sites_size, 0, - (reg_size - problem_data->def_sites_size) *sizeof (bitmap)); - problem_data->def_sites_size = reg_size; - } - - bitmap_clear (problem_data->sparse_invalidated_by_call); - bitmap_clear (problem_data->dense_invalidated_by_call); - } - else - { - struct df_rd_problem_data *problem_data = - xmalloc (sizeof (struct df_rd_problem_data)); - dflow->problem_data = problem_data; - - problem_data->def_sites = xcalloc (reg_size, sizeof (bitmap)); - problem_data->def_sites_size = reg_size; - problem_data->sparse_invalidated_by_call = BITMAP_ALLOC (NULL); - problem_data->dense_invalidated_by_call = BITMAP_ALLOC (NULL); + problem_data->out = NULL; + problem_data->in = NULL; + bitmap_obstack_initialize (&problem_data->lr_bitmaps); } - df_grow_bb_info (dflow); - - /* Because of the clustering of all def sites for the same pseudo, - we have to process all of the blocks before doing the - analysis. */ - - EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi) + EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi) { - struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb_index); - if (bb_info) - { - bitmap_clear (bb_info->kill); - bitmap_clear (bb_info->sparse_kill); - bitmap_clear (bb_info->gen); + struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index); + + /* When bitmaps are already initialized, just clear them. */ + if (bb_info->use.obstack) + { + bitmap_clear (&bb_info->def); + bitmap_clear (&bb_info->use); } else - { - bb_info = (struct df_rd_bb_info *) pool_alloc (dflow->block_pool); - df_rd_set_bb_info (dflow, bb_index, bb_info); - bb_info->kill = BITMAP_ALLOC (NULL); - bb_info->sparse_kill = BITMAP_ALLOC (NULL); - bb_info->gen = BITMAP_ALLOC (NULL); - bb_info->in = BITMAP_ALLOC (NULL); - bb_info->out = BITMAP_ALLOC (NULL); + { + bitmap_initialize (&bb_info->use, &problem_data->lr_bitmaps); + bitmap_initialize (&bb_info->def, &problem_data->lr_bitmaps); + bitmap_initialize (&bb_info->in, &problem_data->lr_bitmaps); + bitmap_initialize (&bb_info->out, &problem_data->lr_bitmaps); } } + + df_lr->optional_p = false; } -/* Process a list of DEFs for df_rd_bb_local_compute. */ +/* Reset the global solution for recalculation. */ static void -df_rd_bb_local_compute_process_def (struct dataflow *dflow, - struct df_rd_bb_info *bb_info, - struct df_ref *def) +df_lr_reset (bitmap all_blocks) { - struct df *df = dflow->df; - while (def) + unsigned int bb_index; + bitmap_iterator bi; + + EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) { - unsigned int regno = DF_REF_REGNO (def); - unsigned int begin = DF_REG_DEF_GET (df, regno)->begin; - unsigned int n_defs = DF_REG_DEF_GET (df, regno)->n_refs; - - /* Only the last def(s) for a regno in the block has any - effect. */ - if (!bitmap_bit_p (seen_in_block, regno)) - { - /* The first def for regno in insn gets to knock out the - defs from other instructions. */ - if (!bitmap_bit_p (seen_in_insn, regno)) - { - if (n_defs > DF_SPARSE_THRESHOLD) - { - bitmap_set_bit (bb_info->sparse_kill, regno); - bitmap_clear_range (bb_info->gen, begin, n_defs); - } - else - { - struct df_rd_problem_data *problem_data = - (struct df_rd_problem_data *) dflow->problem_data; - bitmap defs = - df_ref_bitmap (problem_data->def_sites, regno, - begin, n_defs); - bitmap_ior_into (bb_info->kill, defs); - bitmap_and_compl_into (bb_info->gen, defs); - } - } - - bitmap_set_bit (seen_in_insn, regno); - /* All defs for regno in the instruction may be put into - the gen set. */ - if (! (DF_REF_FLAGS (def) & DF_REF_CLOBBER)) - bitmap_set_bit (bb_info->gen, DF_REF_ID (def)); - } - def = def->next_ref; + struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index); + gcc_assert (bb_info); + bitmap_clear (&bb_info->in); + bitmap_clear (&bb_info->out); } } -/* Compute local reaching def info for basic block BB. */ + +/* Compute local live register info for basic block BB. */ static void -df_rd_bb_local_compute (struct dataflow *dflow, unsigned int bb_index) +df_lr_bb_local_compute (unsigned int bb_index) { - struct df *df = dflow->df; basic_block bb = BASIC_BLOCK (bb_index); - struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb_index); + struct df_lr_bb_info *bb_info = df_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); + bitmap_set_bit (&bb_info->def, dregno); + bitmap_clear_bit (&bb_info->use, dregno); + } + } - bitmap_clear (seen_in_block); - bitmap_clear (seen_in_insn); + /* 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) + bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use)); + } FOR_BB_INSNS_REVERSE (bb, insn) { unsigned int uid = INSN_UID (insn); - if (! INSN_P (insn)) + if (!NONDEBUG_INSN_P (insn)) continue; - df_rd_bb_local_compute_process_def (dflow, bb_info, - DF_INSN_UID_GET (df, uid)->defs); + 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_PARTIAL | DF_REF_CONDITIONAL))) + { + unsigned int dregno = DF_REF_REGNO (def); + bitmap_set_bit (&bb_info->def, dregno); + bitmap_clear_bit (&bb_info->use, dregno); + } + } + + for (use_rec = DF_INSN_UID_USES (uid); *use_rec; 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)); + } + } - /* This complex dance with the two bitmaps is required because - instructions can assign twice to the same pseudo. This - generally happens with calls that will have one def for the - result and another def for the clobber. If only one vector - is used and the clobber goes first, the result will be - lost. */ - bitmap_ior_into (seen_in_block, seen_in_insn); - bitmap_clear (seen_in_insn); + /* 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); + bitmap_set_bit (&bb_info->def, dregno); + bitmap_clear_bit (&bb_info->use, dregno); + } + } + +#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) + bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use)); } +#endif - /* Process the artificial defs last since we are going backwards - thur the block and these are logically at the start. */ - df_rd_bb_local_compute_process_def (dflow, bb_info, - df_get_artificial_defs (df, bb_index)); + /* If the df_live problem is not defined, such as at -O0 and -O1, we + still need to keep the luids up to date. This is normally done + in the df_live problem since this problem has a forwards + scan. */ + if (!df_live) + df_recompute_luids (bb); } -/* Compute local reaching def info for each basic block within BLOCKS. */ +/* Compute local live register info for each basic block within BLOCKS. */ static void -df_rd_local_compute (struct dataflow *dflow, - bitmap all_blocks, - bitmap rescan_blocks ATTRIBUTE_UNUSED) +df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED) { - struct df *df = dflow->df; unsigned int bb_index; bitmap_iterator bi; - unsigned int regno; - struct df_rd_problem_data *problem_data = - (struct df_rd_problem_data *) dflow->problem_data; - bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call; - bitmap dense_invalidated = problem_data->dense_invalidated_by_call; - df_set_seen (); + bitmap_clear (&df->hardware_regs_used); - if (!df->def_info.refs_organized) - df_reorganize_refs (&df->def_info); + /* The all-important stack pointer must always be live. */ + bitmap_set_bit (&df->hardware_regs_used, STACK_POINTER_REGNUM); - EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) + /* Before reload, there are a few registers that must be forced + live everywhere -- which might not already be the case for + blocks within infinite loops. */ + if (!reload_completed) { - df_rd_bb_local_compute (dflow, bb_index); + unsigned int pic_offset_table_regnum = PIC_OFFSET_TABLE_REGNUM; + /* Any reference to any pseudo before reload is a potential + reference of the frame pointer. */ + bitmap_set_bit (&df->hardware_regs_used, FRAME_POINTER_REGNUM); + +#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM + /* Pseudos with argument area equivalences may require + reloading via the argument pointer. */ + if (fixed_regs[ARG_POINTER_REGNUM]) + bitmap_set_bit (&df->hardware_regs_used, ARG_POINTER_REGNUM); +#endif + + /* Any constant, or pseudo with constant equivalences, may + require reloading from memory using the pic register. */ + if (pic_offset_table_regnum != INVALID_REGNUM + && fixed_regs[pic_offset_table_regnum]) + bitmap_set_bit (&df->hardware_regs_used, pic_offset_table_regnum); } - - /* 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 (df_lr->out_of_date_transfer_functions, 0, bb_index, bi) { - struct df_reg_info *reg_info = DF_REG_DEF_GET (df, regno); - if (reg_info->n_refs > DF_SPARSE_THRESHOLD) + if (bb_index == EXIT_BLOCK) { - bitmap_set_bit (sparse_invalidated, regno); + /* The exit block is special for this problem and its bits are + computed from thin air. */ + struct df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK); + bitmap_copy (&bb_info->use, df->exit_block_uses); } else - { - bitmap defs = df_ref_bitmap (problem_data->def_sites, regno, - reg_info->begin, reg_info->n_refs); - bitmap_ior_into (dense_invalidated, defs); - } + df_lr_bb_local_compute (bb_index); } - df_unset_seen (); + + bitmap_clear (df_lr->out_of_date_transfer_functions); } -/* Initialize the solution bit vectors for problem. */ +/* Initialize the solution vectors. */ -static void -df_rd_init_solution (struct dataflow *dflow, bitmap all_blocks) +static void +df_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_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb_index); - - bitmap_copy (bb_info->out, bb_info->gen); - bitmap_clear (bb_info->in); + struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index); + bitmap_copy (&bb_info->in, &bb_info->use); + bitmap_clear (&bb_info->out); } } -/* In of target gets or of out of source. */ +/* 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_rd_confluence_n (struct dataflow *dflow, edge e) +df_lr_confluence_0 (basic_block bb) { - bitmap op1 = df_rd_get_bb_info (dflow, e->dest->index)->in; - bitmap op2 = df_rd_get_bb_info (dflow, e->src->index)->out; + bitmap op1 = &df_lr_get_bb_info (bb->index)->out; + if (bb != EXIT_BLOCK_PTR) + bitmap_copy (op1, &df->hardware_regs_used); +} - if (e->flags & EDGE_EH) - { - struct df_rd_problem_data *problem_data = - (struct df_rd_problem_data *) dflow->problem_data; - bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call; - bitmap dense_invalidated = problem_data->dense_invalidated_by_call; - struct df *df = dflow->df; - bitmap_iterator bi; - unsigned int regno; - bitmap tmp = BITMAP_ALLOC (NULL); - bitmap_copy (tmp, op2); - bitmap_and_compl_into (tmp, dense_invalidated); +/* Confluence function that ignores fake edges. */ - EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi) - { - bitmap_clear_range (tmp, - DF_REG_DEF_GET (df, regno)->begin, - DF_REG_DEF_GET (df, regno)->n_refs); - } - bitmap_ior_into (op1, tmp); - BITMAP_FREE (tmp); - } +static bool +df_lr_confluence_n (edge e) +{ + bitmap op1 = &df_lr_get_bb_info (e->src->index)->out; + bitmap op2 = &df_lr_get_bb_info (e->dest->index)->in; + bool changed = false; + + /* 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) + changed = bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset); else - bitmap_ior_into (op1, op2); + changed = bitmap_ior_into (op1, op2); + + changed |= bitmap_ior_into (op1, &df->hardware_regs_used); + return changed; } /* Transfer function. */ static bool -df_rd_transfer_function (struct dataflow *dflow, int bb_index) +df_lr_transfer_function (int bb_index) { - struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb_index); - unsigned int regno; - bitmap_iterator bi; - bitmap in = bb_info->in; - bitmap out = bb_info->out; - bitmap gen = bb_info->gen; - bitmap kill = bb_info->kill; - bitmap sparse_kill = bb_info->sparse_kill; + struct df_lr_bb_info *bb_info = df_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; - if (bitmap_empty_p (sparse_kill)) - return bitmap_ior_and_compl (out, gen, in, kill); - else + return bitmap_ior_and_compl (in, use, out, def); +} + + +/* Run the fast dce as a side effect of building LR. */ + +static void +df_lr_finalize (bitmap all_blocks) +{ + df_lr->solutions_dirty = false; + if (df->changeable_flags & DF_LR_RUN_DCE) { - struct df *df = dflow->df; - bool changed = false; - bitmap tmp = BITMAP_ALLOC (NULL); - bitmap_copy (tmp, in); - EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi) + run_fast_df_dce (); + + /* 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) { - bitmap_clear_range (tmp, - DF_REG_DEF_GET (df, regno)->begin, - DF_REG_DEF_GET (df, regno)->n_refs); + 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); } - bitmap_and_compl_into (tmp, kill); - bitmap_ior_into (tmp, gen); - changed = !bitmap_equal_p (tmp, out); - if (changed) - { - BITMAP_FREE (out); - bb_info->out = tmp; - } - else - BITMAP_FREE (tmp); - return changed; } } @@ -1175,1956 +1045,3580 @@ df_rd_transfer_function (struct dataflow *dflow, int bb_index) /* Free all storage associated with the problem. */ static void -df_rd_free (struct dataflow *dflow) +df_lr_free (void) { - unsigned int i; - struct df_rd_problem_data *problem_data = - (struct df_rd_problem_data *) dflow->problem_data; + struct df_lr_problem_data *problem_data + = (struct df_lr_problem_data *) df_lr->problem_data; + if (df_lr->block_info) + { - if (problem_data) + df_lr->block_info_size = 0; + free (df_lr->block_info); + df_lr->block_info = NULL; + bitmap_obstack_release (&problem_data->lr_bitmaps); + free (df_lr->problem_data); + df_lr->problem_data = NULL; + } + + BITMAP_FREE (df_lr->out_of_date_transfer_functions); + free (df_lr); +} + + +/* Debugging info at top of bb. */ + +static void +df_lr_top_dump (basic_block bb, FILE *file) +{ + struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index); + struct df_lr_problem_data *problem_data; + if (!bb_info) + return; + + fprintf (file, ";; lr in \t"); + df_print_regset (file, &bb_info->in); + if (df_lr->problem_data) { - for (i = 0; i < dflow->block_info_size; i++) + problem_data = (struct df_lr_problem_data *)df_lr->problem_data; + if (problem_data->in) { - struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, 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); - } + fprintf (file, ";; old in \t"); + df_print_regset (file, &problem_data->in[bb->index]); } - - free_alloc_pool (dflow->block_pool); - - for (i = 0; i < problem_data->def_sites_size; i++) + } + fprintf (file, ";; lr use \t"); + df_print_regset (file, &bb_info->use); + fprintf (file, ";; lr def \t"); + df_print_regset (file, &bb_info->def); +} + + +/* Debugging info at bottom of bb. */ + +static void +df_lr_bottom_dump (basic_block bb, FILE *file) +{ + struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index); + struct df_lr_problem_data *problem_data; + if (!bb_info) + return; + + fprintf (file, ";; lr out \t"); + df_print_regset (file, &bb_info->out); + if (df_lr->problem_data) + { + problem_data = (struct df_lr_problem_data *)df_lr->problem_data; + if (problem_data->out) { - bitmap bm = problem_data->def_sites[i]; - if (bm) - BITMAP_FREE (bm); + fprintf (file, ";; old out \t"); + df_print_regset (file, &problem_data->out[bb->index]); } - - free (problem_data->def_sites); - BITMAP_FREE (problem_data->sparse_invalidated_by_call); - BITMAP_FREE (problem_data->dense_invalidated_by_call); - - dflow->block_info_size = 0; - free (dflow->block_info); - free (dflow->problem_data); } - free (dflow); } -/* Debugging info. */ +/* Build the datastructure to verify that the solution to the dataflow + equations is not dirty. */ static void -df_rd_dump (struct dataflow *dflow, FILE *file) +df_lr_verify_solution_start (void) { - struct df *df = dflow->df; basic_block bb; - struct df_rd_problem_data *problem_data = - (struct df_rd_problem_data *) dflow->problem_data; - unsigned int m = max_reg_num (); - unsigned int regno; - - fprintf (file, "Reaching defs:\n\n"); + struct df_lr_problem_data *problem_data; + if (df_lr->solutions_dirty) + return; - fprintf (file, " sparse invalidated \t"); - dump_bitmap (file, problem_data->sparse_invalidated_by_call); - fprintf (file, " dense invalidated \t"); - dump_bitmap (file, problem_data->dense_invalidated_by_call); + /* Set it true so that the solution is recomputed. */ + df_lr->solutions_dirty = true; - for (regno = 0; regno < m; regno++) - if (DF_REG_DEF_GET (df, regno)->n_refs) - fprintf (file, "%d[%d,%d] ", regno, - DF_REG_DEF_GET (df, regno)->begin, - DF_REG_DEF_GET (df, regno)->n_refs); - fprintf (file, "\n"); + problem_data = (struct df_lr_problem_data *)df_lr->problem_data; + problem_data->in = XNEWVEC (bitmap_head, last_basic_block); + problem_data->out = XNEWVEC (bitmap_head, last_basic_block); FOR_ALL_BB (bb) { - struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb->index); - df_print_bb_index (bb, file); - - if (! bb_info->in) - continue; - - fprintf (file, " in\t(%d)\n", (int) bitmap_count_bits (bb_info->in)); - dump_bitmap (file, bb_info->in); - fprintf (file, " gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen)); - dump_bitmap (file, bb_info->gen); - fprintf (file, " kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill)); - dump_bitmap (file, bb_info->kill); - fprintf (file, " out\t(%d)\n", (int) bitmap_count_bits (bb_info->out)); - dump_bitmap (file, bb_info->out); + bitmap_initialize (&problem_data->in[bb->index], &problem_data->lr_bitmaps); + bitmap_initialize (&problem_data->out[bb->index], &problem_data->lr_bitmaps); + bitmap_copy (&problem_data->in[bb->index], DF_LR_IN (bb)); + bitmap_copy (&problem_data->out[bb->index], DF_LR_OUT (bb)); + } +} + + +/* Compare the saved datastructure and the new solution to the dataflow + equations. */ + +static void +df_lr_verify_solution_end (void) +{ + struct df_lr_problem_data *problem_data; + basic_block bb; + + problem_data = (struct df_lr_problem_data *)df_lr->problem_data; + + if (!problem_data->out) + return; + + if (df_lr->solutions_dirty) + /* Do not check if the solution is still dirty. See the comment + in df_lr_finalize for details. */ + df_lr->solutions_dirty = false; + else + FOR_ALL_BB (bb) + { + if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LR_IN (bb))) + || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LR_OUT (bb)))) + { + /*df_dump (stderr);*/ + gcc_unreachable (); + } + } + + /* Cannot delete them immediately because you may want to dump them + if the comparison fails. */ + FOR_ALL_BB (bb) + { + bitmap_clear (&problem_data->in[bb->index]); + bitmap_clear (&problem_data->out[bb->index]); } + + free (problem_data->in); + free (problem_data->out); + problem_data->in = NULL; + problem_data->out = NULL; } + /* All of the information associated with every instance of the problem. */ -static struct df_problem problem_RD = +static struct df_problem problem_LR = { - DF_RD, /* Problem id. */ - DF_FORWARD, /* Direction. */ - df_rd_alloc, /* Allocate the problem specific data. */ - df_rd_free_bb_info, /* Free basic block info. */ - df_rd_local_compute, /* Local compute function. */ - df_rd_init_solution, /* Init the solution specific data. */ - df_iterative_dataflow, /* Iterative solver. */ - NULL, /* Confluence operator 0. */ - df_rd_confluence_n, /* Confluence operator n. */ - df_rd_transfer_function, /* Transfer function. */ - NULL, /* Finalize function. */ - df_rd_free, /* Free all of the problem information. */ - df_rd_dump, /* Debugging. */ - NULL /* Dependent problem. */ + DF_LR, /* Problem id. */ + DF_BACKWARD, /* Direction. */ + df_lr_alloc, /* Allocate the problem specific data. */ + df_lr_reset, /* Reset global information. */ + df_lr_free_bb_info, /* Free basic block info. */ + df_lr_local_compute, /* Local compute function. */ + df_lr_init, /* Init the solution specific data. */ + df_worklist_dataflow, /* Worklist solver. */ + df_lr_confluence_0, /* Confluence operator 0. */ + df_lr_confluence_n, /* Confluence operator n. */ + df_lr_transfer_function, /* Transfer 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. */ + df_lr_top_dump, /* Debugging start block. */ + df_lr_bottom_dump, /* Debugging end block. */ + df_lr_verify_solution_start,/* Incremental solution verify start. */ + df_lr_verify_solution_end, /* Incremental solution verify end. */ + NULL, /* Dependent problem. */ + sizeof (struct df_lr_bb_info),/* Size of entry of block_info array. */ + TV_DF_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. */ -struct dataflow * -df_rd_add_problem (struct df *df) +void +df_lr_add_problem (void) { - return df_add_problem (df, &problem_RD); + df_add_problem (&problem_LR); + /* These will be initialized when df_scan_blocks processes each + block. */ + df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL); } - -/*---------------------------------------------------------------------------- - LIVE REGISTERS +/* Verify that all of the lr related info is consistent and + correct. */ - Find the locations in the function where any use of a pseudo can reach - in the backwards direction. -----------------------------------------------------------------------------*/ +void +df_lr_verify_transfer_functions (void) +{ + basic_block bb; + bitmap_head saved_def; + bitmap_head saved_use; + bitmap_head all_blocks; -/* Get basic block info. */ + if (!df) + return; -struct df_lr_bb_info * -df_lr_get_bb_info (struct dataflow *dflow, unsigned int index) -{ - return (struct df_lr_bb_info *) dflow->block_info[index]; + bitmap_initialize (&saved_def, &bitmap_default_obstack); + bitmap_initialize (&saved_use, &bitmap_default_obstack); + bitmap_initialize (&all_blocks, &bitmap_default_obstack); + + FOR_ALL_BB (bb) + { + struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index); + bitmap_set_bit (&all_blocks, bb->index); + + if (bb_info) + { + /* Make a copy of the transfer functions and then compute + new ones to see if the transfer functions have + changed. */ + if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions, + bb->index)) + { + bitmap_copy (&saved_def, &bb_info->def); + bitmap_copy (&saved_use, &bb_info->use); + bitmap_clear (&bb_info->def); + bitmap_clear (&bb_info->use); + + df_lr_bb_local_compute (bb->index); + gcc_assert (bitmap_equal_p (&saved_def, &bb_info->def)); + gcc_assert (bitmap_equal_p (&saved_use, &bb_info->use)); + } + } + else + { + /* If we do not have basic block info, the block must be in + the list of dirty blocks or else some one has added a + block behind our backs. */ + gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions, + bb->index)); + } + /* Make sure no one created a block without following + procedures. */ + gcc_assert (df_scan_get_bb_info (bb->index)); + } + + /* Make sure there are no dirty bits in blocks that have been deleted. */ + gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions, + &all_blocks)); + + bitmap_clear (&saved_def); + bitmap_clear (&saved_use); + bitmap_clear (&all_blocks); } -/* Set basic block info. */ + +/*---------------------------------------------------------------------------- + LIVE AND MUST-INITIALIZED REGISTERS. + + This problem first computes the IN and OUT bitvectors for the + must-initialized registers problems, which is a forward problem. + It gives the set of registers for which we MUST have an available + definition on any path from the entry block to the entry/exit of + a basic block. Sets generate a definition, while clobbers kill + a definition. + + In and out bitvectors are built for each basic block and are indexed by + regnum (see df.h for details). In and out bitvectors in struct + df_live_bb_info actually refers to the must-initialized problem; + + Then, the in and out sets for the LIVE problem itself are computed. + These are the logical AND of the IN and OUT sets from the LR problem + and the must-initialized problem. +----------------------------------------------------------------------------*/ -static void -df_lr_set_bb_info (struct dataflow *dflow, unsigned int index, - struct df_lr_bb_info *bb_info) +/* Private data used to verify the solution for this problem. */ +struct df_live_problem_data { - dflow->block_info[index] = bb_info; -} + bitmap_head *in; + bitmap_head *out; + /* An obstack for the bitmaps we need for this problem. */ + bitmap_obstack live_bitmaps; +}; + +/* Scratch var used by transfer functions. This is used to implement + an optimization to reduce the amount of space used to compute the + combined lr and live analysis. */ +static bitmap_head df_live_scratch; + - /* Free basic block info. */ static void -df_lr_free_bb_info (struct dataflow *dflow, - basic_block bb ATTRIBUTE_UNUSED, +df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, void *vbb_info) { - struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info; + struct df_live_bb_info *bb_info = (struct df_live_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 (dflow->block_pool, bb_info); + bitmap_clear (&bb_info->gen); + bitmap_clear (&bb_info->kill); + bitmap_clear (&bb_info->in); + bitmap_clear (&bb_info->out); } } -/* Allocate or reset bitmaps for DFLOW blocks. The solution bits are +/* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are not touched unless the block is new. */ -static void -df_lr_alloc (struct dataflow *dflow, bitmap blocks_to_rescan) +static void +df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED) { unsigned int bb_index; bitmap_iterator bi; + struct df_live_problem_data *problem_data; - if (! dflow->block_pool) - dflow->block_pool = create_alloc_pool ("df_lr_block pool", - sizeof (struct df_lr_bb_info), 50); + if (df_live->problem_data) + problem_data = (struct df_live_problem_data *) df_live->problem_data; + else + { + problem_data = XNEW (struct df_live_problem_data); + df_live->problem_data = problem_data; - df_grow_bb_info (dflow); + problem_data->out = NULL; + problem_data->in = NULL; + bitmap_obstack_initialize (&problem_data->live_bitmaps); + bitmap_initialize (&df_live_scratch, &problem_data->live_bitmaps); + } - /* Because of the clustering of all def sites for the same pseudo, - we have to process all of the blocks before doing the - analysis. */ + df_grow_bb_info (df_live); - EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi) + EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi) { - struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb_index); - if (bb_info) - { - bitmap_clear (bb_info->def); - bitmap_clear (bb_info->use); + struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index); + + /* When bitmaps are already initialized, just clear them. */ + if (bb_info->kill.obstack) + { + bitmap_clear (&bb_info->kill); + bitmap_clear (&bb_info->gen); } else - { - bb_info = (struct df_lr_bb_info *) pool_alloc (dflow->block_pool); - df_lr_set_bb_info (dflow, bb_index, bb_info); - bb_info->use = BITMAP_ALLOC (NULL); - bb_info->def = BITMAP_ALLOC (NULL); - bb_info->in = BITMAP_ALLOC (NULL); - bb_info->out = BITMAP_ALLOC (NULL); + { + bitmap_initialize (&bb_info->kill, &problem_data->live_bitmaps); + bitmap_initialize (&bb_info->gen, &problem_data->live_bitmaps); + bitmap_initialize (&bb_info->in, &problem_data->live_bitmaps); + bitmap_initialize (&bb_info->out, &problem_data->live_bitmaps); } } + df_live->optional_p = (optimize <= 1); } -/* Compute local live register info for basic block BB. */ +/* Reset the global solution for recalculation. */ + +static void +df_live_reset (bitmap all_blocks) +{ + unsigned int bb_index; + bitmap_iterator bi; + + EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) + { + struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index); + gcc_assert (bb_info); + bitmap_clear (&bb_info->in); + bitmap_clear (&bb_info->out); + } +} + + +/* Compute local uninitialized register info for basic block BB. */ static void -df_lr_bb_local_compute (struct dataflow *dflow, - struct df *df, unsigned int bb_index) +df_live_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 (dflow, bb_index); + struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index); rtx insn; - struct df_ref *def; - struct df_ref *use; - - /* Process the hardware registers that are always live. */ - for (use = df_get_artificial_uses (df, bb_index); use; use = use->next_ref) - /* 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)); + df_ref *def_rec; + int luid = 0; - FOR_BB_INSNS_REVERSE (bb, insn) + FOR_BB_INSNS (bb, insn) { unsigned int uid = INSN_UID (insn); + struct df_insn_info *insn_info = DF_INSN_UID_GET (uid); - if (! INSN_P (insn)) - continue; - - if (CALL_P (insn)) + /* Inserting labels does not always trigger the incremental + rescanning. */ + if (!insn_info) { - for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref) - { - unsigned int dregno = DF_REF_REGNO (def); - - if (dregno >= FIRST_PSEUDO_REGISTER - || !(SIBLING_CALL_P (insn) - && bitmap_bit_p (df->exit_block_uses, dregno) - && !refers_to_regno_p (dregno, dregno+1, - current_function_return_rtx, - (rtx *)0))) - { - /* Add def to set of defs in this BB. */ - bitmap_set_bit (bb_info->def, dregno); - bitmap_clear_bit (bb_info->use, dregno); - } - } + gcc_assert (!INSN_P (insn)); + insn_info = df_insn_create_insn_record (insn); } - else + + DF_INSN_INFO_LUID (insn_info) = luid; + if (!INSN_P (insn)) + continue; + + luid++; + for (def_rec = DF_INSN_INFO_DEFS (insn_info); *def_rec; def_rec++) { - for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref) - { - unsigned int dregno = DF_REF_REGNO (def); - - if (DF_INSN_CONTAINS_ASM (df, insn) - && dregno < FIRST_PSEUDO_REGISTER) - { - unsigned int i; - unsigned int end = - dregno + hard_regno_nregs[dregno][GET_MODE (DF_REF_REG (def))] - 1; - for (i = dregno; i <= end; ++i) - regs_asm_clobbered[i] = 1; - } - /* Add def to set of defs in this BB. */ - bitmap_set_bit (bb_info->def, dregno); - bitmap_clear_bit (bb_info->use, dregno); - } - } + df_ref def = *def_rec; + unsigned int regno = DF_REF_REGNO (def); - for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref) - /* Add use to set of uses in this BB. */ - bitmap_set_bit (bb_info->use, DF_REF_REGNO (use)); + if (DF_REF_FLAGS_IS_SET (def, + DF_REF_PARTIAL | DF_REF_CONDITIONAL)) + /* All partial or conditional def + seen are included in the gen set. */ + bitmap_set_bit (&bb_info->gen, regno); + else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER)) + /* Only must clobbers for the entire reg destroy the + value. */ + bitmap_set_bit (&bb_info->kill, regno); + else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER)) + bitmap_set_bit (&bb_info->gen, regno); + } } - /* Process the registers set in an exception handler. */ - for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref) + for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++) { - unsigned int dregno = DF_REF_REGNO (def); - bitmap_set_bit (bb_info->def, dregno); - bitmap_clear_bit (bb_info->use, dregno); + df_ref def = *def_rec; + bitmap_set_bit (&bb_info->gen, DF_REF_REGNO (def)); } - -#ifdef EH_USES - /* Process the uses that are live into an exception handler. */ - for (use = df_get_artificial_uses (df, bb_index); use; use = use->next_ref) - /* 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)); -#endif } -/* Compute local live register info for each basic block within BLOCKS. */ + +/* Compute local uninitialized register info. */ static void -df_lr_local_compute (struct dataflow *dflow, - bitmap all_blocks, - bitmap rescan_blocks) +df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED) { - struct df *df = dflow->df; unsigned int bb_index; bitmap_iterator bi; - - /* Assume that the stack pointer is unchanging if alloca hasn't - been used. */ - if (bitmap_equal_p (all_blocks, rescan_blocks)) - memset (regs_asm_clobbered, 0, sizeof (regs_asm_clobbered)); - - bitmap_clear (df->hardware_regs_used); - - /* The all-important stack pointer must always be live. */ - bitmap_set_bit (df->hardware_regs_used, STACK_POINTER_REGNUM); - - /* Before reload, there are a few registers that must be forced - live everywhere -- which might not already be the case for - blocks within infinite loops. */ - if (! reload_completed) - { - /* Any reference to any pseudo before reload is a potential - reference of the frame pointer. */ - bitmap_set_bit (df->hardware_regs_used, FRAME_POINTER_REGNUM); - -#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM - /* Pseudos with argument area equivalences may require - reloading via the argument pointer. */ - if (fixed_regs[ARG_POINTER_REGNUM]) - bitmap_set_bit (df->hardware_regs_used, ARG_POINTER_REGNUM); -#endif - - /* Any constant, or pseudo with constant equivalences, may - require reloading from memory using the pic register. */ - if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM - && fixed_regs[PIC_OFFSET_TABLE_REGNUM]) - bitmap_set_bit (df->hardware_regs_used, PIC_OFFSET_TABLE_REGNUM); - } - - if (bitmap_bit_p (rescan_blocks, EXIT_BLOCK)) - { - /* The exit block is special for this problem and its bits are - computed from thin air. */ - struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, EXIT_BLOCK); - bitmap_copy (bb_info->use, df->exit_block_uses); - } - - EXECUTE_IF_SET_IN_BITMAP (rescan_blocks, 0, bb_index, bi) + + df_grow_insn_info (); + + EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, + 0, bb_index, bi) { - if (bb_index == EXIT_BLOCK) - continue; - df_lr_bb_local_compute (dflow, df, bb_index); + df_live_bb_local_compute (bb_index); } + + bitmap_clear (df_live->out_of_date_transfer_functions); } /* Initialize the solution vectors. */ -static void -df_lr_init (struct dataflow *dflow, bitmap all_blocks) +static void +df_live_init (bitmap all_blocks) { unsigned int bb_index; bitmap_iterator bi; EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) { - struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb_index); - bitmap_copy (bb_info->in, bb_info->use); - bitmap_clear (bb_info->out); + struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index); + struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index); + + /* No register may reach a location where it is not used. Thus + we trim the rr result to the places where it is used. */ + bitmap_and (&bb_info->out, &bb_info->gen, &bb_lr_info->out); + bitmap_clear (&bb_info->in); } } +/* Forward confluence function that ignores fake edges. */ -/* 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_lr_confluence_0 (struct dataflow *dflow, basic_block bb) +static bool +df_live_confluence_n (edge e) { - struct df *df = dflow->df; - - bitmap op1 = df_lr_get_bb_info (dflow, bb->index)->out; - if (bb != EXIT_BLOCK_PTR) - bitmap_copy (op1, df->hardware_regs_used); -} + bitmap op1 = &df_live_get_bb_info (e->dest->index)->in; + bitmap op2 = &df_live_get_bb_info (e->src->index)->out; + if (e->flags & EDGE_FAKE) + return false; -/* Confluence function that ignores fake edges. */ -static void -df_lr_confluence_n (struct dataflow *dflow, edge e) -{ - bitmap op1 = df_lr_get_bb_info (dflow, e->src->index)->out; - bitmap op2 = df_lr_get_bb_info (dflow, 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, df_invalidated_by_call); - else - bitmap_ior_into (op1, op2); + return bitmap_ior_into (op1, op2); +} - bitmap_ior_into (op1, dflow->df->hardware_regs_used); -} +/* Transfer function for the forwards must-initialized problem. */ -/* Transfer function. */ static bool -df_lr_transfer_function (struct dataflow *dflow, int bb_index) +df_live_transfer_function (int bb_index) { - struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, 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); + struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index); + struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index); + bitmap in = &bb_info->in; + bitmap out = &bb_info->out; + bitmap gen = &bb_info->gen; + bitmap kill = &bb_info->kill; + + /* We need to use a scratch set here so that the value returned from this + function invocation properly reflects whether the sets changed in a + significant way; i.e. not just because the lr set was anded in. */ + bitmap_and (&df_live_scratch, gen, &bb_lr_info->out); + /* No register may reach a location where it is not used. Thus + we trim the rr result to the places where it is used. */ + bitmap_and_into (in, &bb_lr_info->in); + + return bitmap_ior_and_compl (out, &df_live_scratch, in, kill); } -/* Free all storage associated with the problem. */ +/* And the LR info with the must-initialized registers, to produce the LIVE info. */ static void -df_lr_free (struct dataflow *dflow) +df_live_finalize (bitmap all_blocks) { - if (dflow->block_info) + + if (df_live->solutions_dirty) { - unsigned int i; - for (i = 0; i < dflow->block_info_size; i++) + bitmap_iterator bi; + unsigned int bb_index; + + EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) { - struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, i); - if (bb_info) - { - BITMAP_FREE (bb_info->use); - BITMAP_FREE (bb_info->def); - BITMAP_FREE (bb_info->in); - BITMAP_FREE (bb_info->out); - } + struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index); + struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index); + + /* No register may reach a location where it is not used. Thus + we trim the rr result to the places where it is used. */ + bitmap_and_into (&bb_live_info->in, &bb_lr_info->in); + bitmap_and_into (&bb_live_info->out, &bb_lr_info->out); } - free_alloc_pool (dflow->block_pool); - - dflow->block_info_size = 0; - free (dflow->block_info); + + df_live->solutions_dirty = false; } - free (dflow); } -/* Debugging info. */ +/* Free all storage associated with the problem. */ static void -df_lr_dump (struct dataflow *dflow, FILE *file) +df_live_free (void) { - basic_block bb; - - fprintf (file, "Live Registers:\n"); - FOR_ALL_BB (bb) + struct df_live_problem_data *problem_data + = (struct df_live_problem_data *) df_live->problem_data; + if (df_live->block_info) { - struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb->index); - df_print_bb_index (bb, file); - - if (!bb_info->in) - continue; - - fprintf (file, " in \t"); - dump_bitmap (file, bb_info->in); - fprintf (file, " use \t"); - dump_bitmap (file, bb_info->use); - fprintf (file, " def \t"); - dump_bitmap (file, bb_info->def); - fprintf (file, " out \t"); - dump_bitmap (file, bb_info->out); + df_live->block_info_size = 0; + free (df_live->block_info); + df_live->block_info = NULL; + bitmap_clear (&df_live_scratch); + bitmap_obstack_release (&problem_data->live_bitmaps); + free (problem_data); + df_live->problem_data = NULL; } + BITMAP_FREE (df_live->out_of_date_transfer_functions); + free (df_live); } -/* All of the information associated with every instance of the problem. */ - -static struct df_problem problem_LR = -{ - DF_LR, /* Problem id. */ - DF_BACKWARD, /* Direction. */ - df_lr_alloc, /* Allocate the problem specific data. */ - df_lr_free_bb_info, /* Free basic block info. */ - df_lr_local_compute, /* Local compute function. */ - df_lr_init, /* Init the solution specific data. */ - df_iterative_dataflow, /* Iterative solver. */ - df_lr_confluence_0, /* Confluence operator 0. */ - df_lr_confluence_n, /* Confluence operator n. */ - df_lr_transfer_function, /* Transfer function. */ - NULL, /* Finalize function. */ - df_lr_free, /* Free all of the problem information. */ - df_lr_dump, /* Debugging. */ - NULL /* Dependent problem. */ -}; - -/* 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. */ +/* Debugging info at top of bb. */ -struct dataflow * -df_lr_add_problem (struct df *df) +static void +df_live_top_dump (basic_block bb, FILE *file) { - return df_add_problem (df, &problem_LR); -} - - - -/*---------------------------------------------------------------------------- - UNINITIALIZED REGISTERS - - Find the set of uses for registers that are reachable from the entry - block without passing thru a definition. -----------------------------------------------------------------------------*/ + struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index); + struct df_live_problem_data *problem_data; -/* Get basic block info. */ + if (!bb_info) + return; -struct df_ur_bb_info * -df_ur_get_bb_info (struct dataflow *dflow, unsigned int index) -{ - return (struct df_ur_bb_info *) dflow->block_info[index]; + fprintf (file, ";; live in \t"); + df_print_regset (file, &bb_info->in); + if (df_live->problem_data) + { + problem_data = (struct df_live_problem_data *)df_live->problem_data; + if (problem_data->in) + { + fprintf (file, ";; old in \t"); + df_print_regset (file, &problem_data->in[bb->index]); + } + } + fprintf (file, ";; live gen \t"); + df_print_regset (file, &bb_info->gen); + fprintf (file, ";; live kill\t"); + df_print_regset (file, &bb_info->kill); } -/* Set basic block info. */ +/* Debugging info at bottom of bb. */ static void -df_ur_set_bb_info (struct dataflow *dflow, unsigned int index, - struct df_ur_bb_info *bb_info) +df_live_bottom_dump (basic_block bb, FILE *file) { - dflow->block_info[index] = bb_info; -} - + struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index); + struct df_live_problem_data *problem_data; -/* Free basic block info. */ + if (!bb_info) + return; -static void -df_ur_free_bb_info (struct dataflow *dflow, - basic_block bb ATTRIBUTE_UNUSED, - void *vbb_info) -{ - struct df_ur_bb_info *bb_info = (struct df_ur_bb_info *) vbb_info; - if (bb_info) + fprintf (file, ";; live out \t"); + df_print_regset (file, &bb_info->out); + if (df_live->problem_data) { - BITMAP_FREE (bb_info->gen); - BITMAP_FREE (bb_info->kill); - BITMAP_FREE (bb_info->in); - BITMAP_FREE (bb_info->out); - pool_free (dflow->block_pool, bb_info); + problem_data = (struct df_live_problem_data *)df_live->problem_data; + if (problem_data->out) + { + fprintf (file, ";; old out \t"); + df_print_regset (file, &problem_data->out[bb->index]); + } } } -/* Allocate or reset bitmaps for DFLOW blocks. The solution bits are - not touched unless the block is new. */ +/* Build the datastructure to verify that the solution to the dataflow + equations is not dirty. */ -static void -df_ur_alloc (struct dataflow *dflow, bitmap blocks_to_rescan) +static void +df_live_verify_solution_start (void) { - unsigned int bb_index; - bitmap_iterator bi; - - if (! dflow->block_pool) - dflow->block_pool = create_alloc_pool ("df_ur_block pool", - sizeof (struct df_ur_bb_info), 100); + basic_block bb; + struct df_live_problem_data *problem_data; + if (df_live->solutions_dirty) + return; - df_grow_bb_info (dflow); + /* Set it true so that the solution is recomputed. */ + df_live->solutions_dirty = true; - /* Because of the clustering of all def sites for the same pseudo, - we have to process all of the blocks before doing the - analysis. */ + problem_data = (struct df_live_problem_data *)df_live->problem_data; + problem_data->in = XNEWVEC (bitmap_head, last_basic_block); + problem_data->out = XNEWVEC (bitmap_head, last_basic_block); - EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi) + FOR_ALL_BB (bb) { - struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index); - if (bb_info) - { - bitmap_clear (bb_info->kill); - bitmap_clear (bb_info->gen); - } - else - { - bb_info = (struct df_ur_bb_info *) pool_alloc (dflow->block_pool); - df_ur_set_bb_info (dflow, bb_index, bb_info); - bb_info->kill = BITMAP_ALLOC (NULL); - bb_info->gen = BITMAP_ALLOC (NULL); - bb_info->in = BITMAP_ALLOC (NULL); - bb_info->out = BITMAP_ALLOC (NULL); - } + bitmap_initialize (&problem_data->in[bb->index], &problem_data->live_bitmaps); + bitmap_initialize (&problem_data->out[bb->index], &problem_data->live_bitmaps); + bitmap_copy (&problem_data->in[bb->index], DF_LIVE_IN (bb)); + bitmap_copy (&problem_data->out[bb->index], DF_LIVE_OUT (bb)); } } -/* Compute local uninitialized register info for basic block BB. */ +/* Compare the saved datastructure and the new solution to the dataflow + equations. */ static void -df_ur_bb_local_compute (struct dataflow *dflow, unsigned int bb_index) +df_live_verify_solution_end (void) { - struct df *df = dflow->df; - basic_block bb = BASIC_BLOCK (bb_index); - struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index); - rtx insn; - struct df_ref *def; - - bitmap_clear (seen_in_block); - bitmap_clear (seen_in_insn); - - FOR_BB_INSNS_REVERSE (bb, insn) - { - unsigned int uid = INSN_UID (insn); - if (!INSN_P (insn)) - continue; + struct df_live_problem_data *problem_data; + basic_block bb; - for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref) - { - unsigned int regno = DF_REF_REGNO (def); - /* Only the last def counts. */ - if (!bitmap_bit_p (seen_in_block, regno)) - { - bitmap_set_bit (seen_in_insn, regno); - - if (DF_REF_FLAGS (def) & DF_REF_CLOBBER) - bitmap_set_bit (bb_info->kill, regno); - else - bitmap_set_bit (bb_info->gen, regno); - } - } - bitmap_ior_into (seen_in_block, seen_in_insn); - bitmap_clear (seen_in_insn); - } + problem_data = (struct df_live_problem_data *)df_live->problem_data; + if (!problem_data->out) + return; - for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref) + FOR_ALL_BB (bb) { - unsigned int regno = DF_REF_REGNO (def); - if (!bitmap_bit_p (seen_in_block, regno)) + if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LIVE_IN (bb))) + || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LIVE_OUT (bb)))) { - bitmap_set_bit (seen_in_block, regno); - bitmap_set_bit (bb_info->gen, regno); + /*df_dump (stderr);*/ + gcc_unreachable (); } } -} - -/* Compute local uninitialized register info. */ - -static void -df_ur_local_compute (struct dataflow *dflow, - bitmap all_blocks ATTRIBUTE_UNUSED, - bitmap rescan_blocks) -{ - unsigned int bb_index; - bitmap_iterator bi; - - df_set_seen (); - - EXECUTE_IF_SET_IN_BITMAP (rescan_blocks, 0, bb_index, bi) + /* Cannot delete them immediately because you may want to dump them + if the comparison fails. */ + FOR_ALL_BB (bb) { - df_ur_bb_local_compute (dflow, bb_index); + bitmap_clear (&problem_data->in[bb->index]); + bitmap_clear (&problem_data->out[bb->index]); } - df_unset_seen (); + free (problem_data->in); + free (problem_data->out); + free (problem_data); + df_live->problem_data = NULL; } -/* Initialize the solution vectors. */ +/* All of the information associated with every instance of the problem. */ -static void -df_ur_init (struct dataflow *dflow, bitmap all_blocks) +static struct df_problem problem_LIVE = { - unsigned int bb_index; - bitmap_iterator bi; - - EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) - { - struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index); - - bitmap_copy (bb_info->out, bb_info->gen); - bitmap_clear (bb_info->in); - } -} + DF_LIVE, /* Problem id. */ + DF_FORWARD, /* Direction. */ + df_live_alloc, /* Allocate the problem specific data. */ + df_live_reset, /* Reset global information. */ + df_live_free_bb_info, /* Free basic block info. */ + df_live_local_compute, /* Local compute function. */ + df_live_init, /* Init the solution specific data. */ + df_worklist_dataflow, /* Worklist solver. */ + NULL, /* Confluence operator 0. */ + df_live_confluence_n, /* Confluence operator n. */ + df_live_transfer_function, /* Transfer 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. */ + df_live_top_dump, /* Debugging start block. */ + df_live_bottom_dump, /* Debugging end block. */ + df_live_verify_solution_start,/* Incremental solution verify start. */ + df_live_verify_solution_end, /* Incremental solution verify end. */ + &problem_LR, /* Dependent problem. */ + sizeof (struct df_live_bb_info),/* Size of entry of block_info array. */ + TV_DF_LIVE, /* Timing variable. */ + false /* Reset blocks on dropping out of blocks_to_analyze. */ +}; -/* Or in the stack regs, hard regs and early clobber regs into the the - ur_in sets of all of the blocks. */ +/* 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. */ -static void -df_ur_local_finalize (struct dataflow *dflow, bitmap all_blocks) +void +df_live_add_problem (void) { - struct df *df = dflow->df; - struct dataflow *lr_dflow = df->problems_by_index[DF_LR]; - bitmap tmp = BITMAP_ALLOC (NULL); - bitmap_iterator bi; - unsigned int bb_index; - - EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) - { - struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index); - struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (lr_dflow, bb_index); - - bitmap_ior_into (bb_info->in, df_all_hard_regs); - bitmap_ior_into (bb_info->out, df_all_hard_regs); - - /* No register may reach a location where it is not used. Thus - we trim the rr result to the places where it is used. */ - bitmap_and_into (bb_info->in, bb_lr_info->in); - bitmap_and_into (bb_info->out, bb_lr_info->out); - -#if 1 - /* Hard registers may still stick in the ur_out set, but not - be in the ur_in set, if their only mention was in a call - in this block. This is because a call kills in the lr - problem but does not kill in the ur problem. To clean - this up, we execute the transfer function on the lr_in - set and then use that to knock bits out of ur_out. */ - bitmap_ior_and_compl (tmp, bb_info->gen, bb_lr_info->in, - bb_info->kill); - bitmap_and_into (bb_info->out, tmp); -#endif - } - - BITMAP_FREE (tmp); + df_add_problem (&problem_LIVE); + /* These will be initialized when df_scan_blocks processes each + block. */ + df_live->out_of_date_transfer_functions = BITMAP_ALLOC (NULL); } -/* Confluence function that ignores fake edges. */ +/* Set all of the blocks as dirty. This needs to be done if this + problem is added after all of the insns have been scanned. */ -static void -df_ur_confluence_n (struct dataflow *dflow, edge e) +void +df_live_set_all_dirty (void) { - bitmap op1 = df_ur_get_bb_info (dflow, e->dest->index)->in; - bitmap op2 = df_ur_get_bb_info (dflow, e->src->index)->out; - - if (e->flags & EDGE_FAKE) - return; - - bitmap_ior_into (op1, op2); -} + basic_block bb; + FOR_ALL_BB (bb) + bitmap_set_bit (df_live->out_of_date_transfer_functions, + bb->index); +} -/* Transfer function. */ +/* Verify that all of the lr related info is consistent and + correct. */ -static bool -df_ur_transfer_function (struct dataflow *dflow, int bb_index) +void +df_live_verify_transfer_functions (void) { - struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index); - bitmap in = bb_info->in; - bitmap out = bb_info->out; - bitmap gen = bb_info->gen; - bitmap kill = bb_info->kill; + basic_block bb; + bitmap_head saved_gen; + bitmap_head saved_kill; + bitmap_head all_blocks; - return bitmap_ior_and_compl (out, gen, in, kill); -} + if (!df) + return; + bitmap_initialize (&saved_gen, &bitmap_default_obstack); + bitmap_initialize (&saved_kill, &bitmap_default_obstack); + bitmap_initialize (&all_blocks, &bitmap_default_obstack); -/* Free all storage associated with the problem. */ + df_grow_insn_info (); -static void -df_ur_free (struct dataflow *dflow) -{ - if (dflow->block_info) + FOR_ALL_BB (bb) { - unsigned int i; - - for (i = 0; i < dflow->block_info_size; i++) + struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index); + bitmap_set_bit (&all_blocks, bb->index); + + if (bb_info) { - struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, i); - if (bb_info) + /* Make a copy of the transfer functions and then compute + new ones to see if the transfer functions have + changed. */ + if (!bitmap_bit_p (df_live->out_of_date_transfer_functions, + bb->index)) { - BITMAP_FREE (bb_info->gen); - BITMAP_FREE (bb_info->kill); - BITMAP_FREE (bb_info->in); - BITMAP_FREE (bb_info->out); + bitmap_copy (&saved_gen, &bb_info->gen); + bitmap_copy (&saved_kill, &bb_info->kill); + bitmap_clear (&bb_info->gen); + bitmap_clear (&bb_info->kill); + + df_live_bb_local_compute (bb->index); + gcc_assert (bitmap_equal_p (&saved_gen, &bb_info->gen)); + gcc_assert (bitmap_equal_p (&saved_kill, &bb_info->kill)); } } - - free_alloc_pool (dflow->block_pool); - dflow->block_info_size = 0; - free (dflow->block_info); + else + { + /* If we do not have basic block info, the block must be in + the list of dirty blocks or else some one has added a + block behind our backs. */ + gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions, + bb->index)); + } + /* Make sure no one created a block without following + procedures. */ + gcc_assert (df_scan_get_bb_info (bb->index)); } - free (dflow); -} - -/* Debugging info. */ + /* Make sure there are no dirty bits in blocks that have been deleted. */ + gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions, + &all_blocks)); + bitmap_clear (&saved_gen); + bitmap_clear (&saved_kill); + bitmap_clear (&all_blocks); +} + +/*---------------------------------------------------------------------------- + CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS + + Link either the defs to the uses and / or the uses to the defs. + + These problems are set up like the other dataflow problems so that + they nicely fit into the framework. They are much simpler and only + involve a single traversal of instructions and an examination of + the reaching defs information (the dependent problem). +----------------------------------------------------------------------------*/ + +#define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG)) + +/* Create a du or ud chain from SRC to DST and link it into SRC. */ +struct df_link * +df_chain_create (df_ref src, df_ref dst) +{ + struct df_link *head = DF_REF_CHAIN (src); + struct df_link *link = (struct df_link *) pool_alloc (df_chain->block_pool); + + DF_REF_CHAIN (src) = link; + link->next = head; + link->ref = dst; + return link; +} + + +/* Delete any du or ud chains that start at REF and point to + TARGET. */ static void -df_ur_dump (struct dataflow *dflow, FILE *file) +df_chain_unlink_1 (df_ref ref, df_ref target) { - basic_block bb; - - fprintf (file, "Undefined regs:\n"); - - FOR_ALL_BB (bb) + struct df_link *chain = DF_REF_CHAIN (ref); + struct df_link *prev = NULL; + + while (chain) { - struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb->index); - df_print_bb_index (bb, file); - - if (! bb_info->in) - continue; - - fprintf (file, " in \t"); - dump_bitmap (file, bb_info->in); - fprintf (file, " gen \t"); - dump_bitmap (file, bb_info->gen); - fprintf (file, " kill\t"); - dump_bitmap (file, bb_info->kill); - fprintf (file, " out \t"); - dump_bitmap (file, bb_info->out); + if (chain->ref == target) + { + if (prev) + prev->next = chain->next; + else + DF_REF_CHAIN (ref) = chain->next; + pool_free (df_chain->block_pool, chain); + return; + } + prev = chain; + chain = chain->next; } } -/* All of the information associated with every instance of the problem. */ -static struct df_problem problem_UR = +/* Delete a du or ud chain that leave or point to REF. */ + +void +df_chain_unlink (df_ref ref) { - DF_UR, /* Problem id. */ - DF_FORWARD, /* Direction. */ - df_ur_alloc, /* Allocate the problem specific data. */ - df_ur_free_bb_info, /* Free basic block info. */ - df_ur_local_compute, /* Local compute function. */ - df_ur_init, /* Init the solution specific data. */ - df_iterative_dataflow, /* Iterative solver. */ - NULL, /* Confluence operator 0. */ - df_ur_confluence_n, /* Confluence operator n. */ - df_ur_transfer_function, /* Transfer function. */ - df_ur_local_finalize, /* Finalize function. */ - df_ur_free, /* Free all of the problem information. */ - df_ur_dump, /* Debugging. */ - &problem_LR /* Dependent problem. */ -}; + struct df_link *chain = DF_REF_CHAIN (ref); + while (chain) + { + struct df_link *next = chain->next; + /* Delete the other side if it exists. */ + df_chain_unlink_1 (chain->ref, ref); + pool_free (df_chain->block_pool, chain); + chain = next; + } + DF_REF_CHAIN (ref) = NULL; +} -/* 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. */ +/* Copy the du or ud chain starting at FROM_REF and attach it to + TO_REF. */ -struct dataflow * -df_ur_add_problem (struct df *df) +void +df_chain_copy (df_ref to_ref, + struct df_link *from_ref) { - return df_add_problem (df, &problem_UR); + while (from_ref) + { + df_chain_create (to_ref, from_ref->ref); + from_ref = from_ref->next; + } } - -/*---------------------------------------------------------------------------- - UNINITIALIZED REGISTERS WITH EARLYCLOBBER +/* Remove this problem from the stack of dataflow problems. */ - Find the set of uses for registers that are reachable from the entry - block without passing thru a definition. +static void +df_chain_remove_problem (void) +{ + bitmap_iterator bi; + unsigned int bb_index; - This is a variant of the UR problem above that has a lot of special - features just for the register allocation phase. -----------------------------------------------------------------------------*/ + /* Wholesale destruction of the old chains. */ + if (df_chain->block_pool) + free_alloc_pool (df_chain->block_pool); -struct df_urec_problem_data -{ - bool earlyclobbers_found; /* True if any instruction contains an - earlyclobber. */ -#ifdef STACK_REGS - bitmap stack_regs; /* Registers that may be allocated to a STACK_REGS. */ -#endif -}; + EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi) + { + rtx insn; + df_ref *def_rec; + df_ref *use_rec; + basic_block bb = BASIC_BLOCK (bb_index); + + if (df_chain_problem_p (DF_DU_CHAIN)) + for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++) + DF_REF_CHAIN (*def_rec) = NULL; + if (df_chain_problem_p (DF_UD_CHAIN)) + for (use_rec = df_get_artificial_uses (bb->index); *use_rec; use_rec++) + DF_REF_CHAIN (*use_rec) = NULL; + + FOR_BB_INSNS (bb, insn) + { + unsigned int uid = INSN_UID (insn); + + if (INSN_P (insn)) + { + if (df_chain_problem_p (DF_DU_CHAIN)) + for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) + DF_REF_CHAIN (*def_rec) = NULL; + if (df_chain_problem_p (DF_UD_CHAIN)) + { + for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++) + DF_REF_CHAIN (*use_rec) = NULL; + for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++) + DF_REF_CHAIN (*use_rec) = NULL; + } + } + } + } + + bitmap_clear (df_chain->out_of_date_transfer_functions); + df_chain->block_pool = NULL; +} -/* Get basic block info. */ +/* Remove the chain problem completely. */ -struct df_urec_bb_info * -df_urec_get_bb_info (struct dataflow *dflow, unsigned int index) +static void +df_chain_fully_remove_problem (void) { - return (struct df_urec_bb_info *) dflow->block_info[index]; + df_chain_remove_problem (); + BITMAP_FREE (df_chain->out_of_date_transfer_functions); + free (df_chain); } -/* Set basic block info. */ +/* Create def-use or use-def chains. */ static void -df_urec_set_bb_info (struct dataflow *dflow, unsigned int index, - struct df_urec_bb_info *bb_info) +df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED) { - dflow->block_info[index] = bb_info; + df_chain_remove_problem (); + df_chain->block_pool = create_alloc_pool ("df_chain_block pool", + sizeof (struct df_link), 50); + df_chain->optional_p = true; } -/* Free basic block info. */ +/* Reset all of the chains when the set of basic blocks changes. */ static void -df_urec_free_bb_info (struct dataflow *dflow, - basic_block bb ATTRIBUTE_UNUSED, - void *vbb_info) +df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED) { - struct df_urec_bb_info *bb_info = (struct df_urec_bb_info *) vbb_info; - if (bb_info) - { - BITMAP_FREE (bb_info->gen); - BITMAP_FREE (bb_info->kill); - BITMAP_FREE (bb_info->in); - BITMAP_FREE (bb_info->out); - BITMAP_FREE (bb_info->earlyclobber); - pool_free (dflow->block_pool, bb_info); - } + df_chain_remove_problem (); } -/* Allocate or reset bitmaps for DFLOW blocks. The solution bits are - not touched unless the block is new. */ +/* Create the chains for a list of USEs. */ -static void -df_urec_alloc (struct dataflow *dflow, bitmap blocks_to_rescan) +static void +df_chain_create_bb_process_use (bitmap local_rd, + df_ref *use_rec, + int top_flag) { - unsigned int bb_index; bitmap_iterator bi; - struct df_urec_problem_data *problem_data = - (struct df_urec_problem_data *) dflow->problem_data; - - if (! dflow->block_pool) - dflow->block_pool = create_alloc_pool ("df_urec_block pool", - sizeof (struct df_urec_bb_info), 50); + unsigned int def_index; - if (!dflow->problem_data) + while (*use_rec) { - problem_data = xmalloc (sizeof (struct df_urec_problem_data)); - dflow->problem_data = problem_data; - } - problem_data->earlyclobbers_found = false; - - df_grow_bb_info (dflow); - - /* Because of the clustering of all def sites for the same pseudo, - we have to process all of the blocks before doing the - analysis. */ + df_ref use = *use_rec; + unsigned int uregno = DF_REF_REGNO (use); + if ((!(df->changeable_flags & DF_NO_HARD_REGS)) + || (uregno >= FIRST_PSEUDO_REGISTER)) + { + /* Do not want to go through this for an uninitialized var. */ + int count = DF_DEFS_COUNT (uregno); + if (count) + { + if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP)) + { + unsigned int first_index = DF_DEFS_BEGIN (uregno); + unsigned int last_index = first_index + count - 1; - EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi) - { - struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index); - if (bb_info) - { - bitmap_clear (bb_info->kill); - bitmap_clear (bb_info->gen); - bitmap_clear (bb_info->earlyclobber); - } - else - { - bb_info = (struct df_urec_bb_info *) pool_alloc (dflow->block_pool); - df_urec_set_bb_info (dflow, bb_index, bb_info); - bb_info->kill = BITMAP_ALLOC (NULL); - bb_info->gen = BITMAP_ALLOC (NULL); - bb_info->in = BITMAP_ALLOC (NULL); - bb_info->out = BITMAP_ALLOC (NULL); - bb_info->earlyclobber = BITMAP_ALLOC (NULL); + EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi) + { + df_ref def; + if (def_index > last_index) + break; + + def = DF_DEFS_GET (def_index); + if (df_chain_problem_p (DF_DU_CHAIN)) + df_chain_create (def, use); + if (df_chain_problem_p (DF_UD_CHAIN)) + df_chain_create (use, def); + } + } + } } + + use_rec++; } } -/* The function modifies local info for register REG being changed in - SETTER. DATA is used to pass the current basic block info. */ +/* Create chains from reaching defs bitmaps for basic block BB. */ static void -df_urec_mark_reg_change (rtx reg, rtx setter, void *data) +df_chain_create_bb (unsigned int bb_index) { - int regno; - int endregno; - int i; - struct df_urec_bb_info *bb_info = (struct df_urec_bb_info*) data; + basic_block bb = BASIC_BLOCK (bb_index); + struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index); + rtx insn; + bitmap_head cpy; - if (GET_CODE (reg) == SUBREG) - reg = SUBREG_REG (reg); + bitmap_initialize (&cpy, &bitmap_default_obstack); + bitmap_copy (&cpy, &bb_info->in); + bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index); - if (!REG_P (reg)) - return; - - - endregno = regno = REGNO (reg); - if (regno < FIRST_PSEUDO_REGISTER) - { - endregno +=hard_regno_nregs[regno][GET_MODE (reg)]; - - for (i = regno; i < endregno; i++) - { - bitmap_set_bit (bb_info->kill, i); - - if (GET_CODE (setter) != CLOBBER) - bitmap_set_bit (bb_info->gen, i); - else - bitmap_clear_bit (bb_info->gen, i); - } - } - else + /* Since we are going forwards, process the artificial uses first + then the artificial defs second. */ + +#ifdef EH_USES + /* Create the chains for the artificial uses from the EH_USES at the + beginning of the block. */ + + /* Artificials are only hard regs. */ + if (!(df->changeable_flags & DF_NO_HARD_REGS)) + df_chain_create_bb_process_use (&cpy, + df_get_artificial_uses (bb->index), + DF_REF_AT_TOP); +#endif + + df_rd_simulate_artificial_defs_at_top (bb, &cpy); + + /* Process the regular instructions next. */ + FOR_BB_INSNS (bb, insn) + 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. */ + 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. */ + if (!(df->changeable_flags & DF_NO_HARD_REGS)) + df_chain_create_bb_process_use (&cpy, + df_get_artificial_uses (bb->index), + 0); + + bitmap_clear (&cpy); +} + +/* Create def-use chains from reaching use bitmaps for basic blocks + in BLOCKS. */ + +static void +df_chain_finalize (bitmap all_blocks) +{ + unsigned int bb_index; + bitmap_iterator bi; + + EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) { - bitmap_set_bit (bb_info->kill, regno); - - if (GET_CODE (setter) != CLOBBER) - bitmap_set_bit (bb_info->gen, regno); - else - bitmap_clear_bit (bb_info->gen, regno); + df_chain_create_bb (bb_index); } } -/* Classes of registers which could be early clobbered in the current - insn. */ - -DEF_VEC_I(int); -DEF_VEC_ALLOC_I(int,heap); -static VEC(int,heap) *earlyclobber_regclass; -/* This function finds and stores register classes that could be early - clobbered in INSN. If any earlyclobber classes are found, the function - returns TRUE, in all other cases it returns FALSE. */ +/* Free all storage associated with the problem. */ -static bool -df_urec_check_earlyclobber (rtx insn) +static void +df_chain_free (void) { - int opno; - bool found = false; + free_alloc_pool (df_chain->block_pool); + BITMAP_FREE (df_chain->out_of_date_transfer_functions); + free (df_chain); +} - extract_insn (insn); - VEC_truncate (int, earlyclobber_regclass, 0); - for (opno = 0; opno < recog_data.n_operands; opno++) - { - char c; - bool amp_p; - int i; - enum reg_class class; - const char *p = recog_data.constraints[opno]; +/* Debugging info. */ - class = NO_REGS; - amp_p = false; - for (;;) +static void +df_chain_top_dump (basic_block bb, FILE *file) +{ + if (df_chain_problem_p (DF_DU_CHAIN)) + { + rtx insn; + df_ref *def_rec = df_get_artificial_defs (bb->index); + if (*def_rec) { - c = *p; - switch (c) + + fprintf (file, ";; DU chains for artificial defs\n"); + while (*def_rec) { - case '=': case '+': case '?': - case '#': case '!': - case '*': case '%': - case 'm': case '<': case '>': case 'V': case 'o': - case 'E': case 'F': case 'G': case 'H': - case 's': case 'i': case 'n': - case 'I': case 'J': case 'K': case 'L': - case 'M': case 'N': case 'O': case 'P': - case 'X': - case '0': case '1': case '2': case '3': case '4': - case '5': case '6': case '7': case '8': case '9': - /* These don't say anything we care about. */ - break; + df_ref def = *def_rec; + fprintf (file, ";; reg %d ", DF_REF_REGNO (def)); + df_chain_dump (DF_REF_CHAIN (def), file); + fprintf (file, "\n"); + def_rec++; + } + } - case '&': - amp_p = true; - break; - case '\0': - case ',': - if (amp_p && class != NO_REGS) + FOR_BB_INSNS (bb, insn) + { + if (INSN_P (insn)) + { + struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); + def_rec = DF_INSN_INFO_DEFS (insn_info); + if (*def_rec) { - int rc; + fprintf (file, ";; DU chains for insn luid %d uid %d\n", + DF_INSN_INFO_LUID (insn_info), INSN_UID (insn)); - found = true; - for (i = 0; - VEC_iterate (int, earlyclobber_regclass, i, rc); - i++) + while (*def_rec) { - if (rc == (int) class) - goto found_rc; + df_ref def = *def_rec; + fprintf (file, ";; reg %d ", DF_REF_REGNO (def)); + if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE) + fprintf (file, "read/write "); + df_chain_dump (DF_REF_CHAIN (def), file); + fprintf (file, "\n"); + def_rec++; } - - /* We use VEC_quick_push here because - earlyclobber_regclass holds no more than - N_REG_CLASSES elements. */ - VEC_quick_push (int, earlyclobber_regclass, (int) class); - found_rc: - ; } - - amp_p = false; - class = NO_REGS; - break; - - case 'r': - class = GENERAL_REGS; - break; - - default: - class = REG_CLASS_FROM_CONSTRAINT (c, p); - break; } - if (c == '\0') - break; - p += CONSTRAINT_LEN (c, p); } } - - return found; } -/* The function checks that pseudo-register *X has a class - intersecting with the class of pseudo-register could be early - clobbered in the same insn. - - This function is a no-op if earlyclobber_regclass is empty. - Reload can assign the same hard register to uninitialized - pseudo-register and early clobbered pseudo-register in an insn if - the pseudo-register is used first time in given BB and not lived at - the BB start. To prevent this we don't change life information for - such pseudo-registers. */ - -static int -df_urec_mark_reg_use_for_earlyclobber (rtx *x, void *data) +static void +df_chain_bottom_dump (basic_block bb, FILE *file) { - enum reg_class pref_class, alt_class; - int i, regno; - struct df_urec_bb_info *bb_info = (struct df_urec_bb_info*) data; - - if (REG_P (*x) && REGNO (*x) >= FIRST_PSEUDO_REGISTER) + if (df_chain_problem_p (DF_UD_CHAIN)) { - int rc; + rtx insn; + df_ref *use_rec = df_get_artificial_uses (bb->index); - regno = REGNO (*x); - if (bitmap_bit_p (bb_info->kill, regno) - || bitmap_bit_p (bb_info->gen, regno)) - return 0; - pref_class = reg_preferred_class (regno); - alt_class = reg_alternate_class (regno); - for (i = 0; VEC_iterate (int, earlyclobber_regclass, i, rc); i++) + if (*use_rec) { - if (reg_classes_intersect_p (rc, pref_class) - || (rc != NO_REGS - && reg_classes_intersect_p (rc, alt_class))) + fprintf (file, ";; UD chains for artificial uses\n"); + while (*use_rec) { - bitmap_set_bit (bb_info->earlyclobber, regno); - break; + df_ref use = *use_rec; + fprintf (file, ";; reg %d ", DF_REF_REGNO (use)); + df_chain_dump (DF_REF_CHAIN (use), file); + fprintf (file, "\n"); + use_rec++; + } + } + + FOR_BB_INSNS (bb, insn) + { + if (INSN_P (insn)) + { + 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_INFO_LUID (insn_info), INSN_UID (insn)); + + while (*use_rec) + { + df_ref use = *use_rec; + fprintf (file, ";; reg %d ", DF_REF_REGNO (use)); + if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE) + fprintf (file, "read/write "); + df_chain_dump (DF_REF_CHAIN (use), file); + fprintf (file, "\n"); + use_rec++; + } + while (*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"); + eq_use_rec++; + } + } } } } - return 0; } -/* The function processes all pseudo-registers in *X with the aid of - previous function. */ -static void -df_urec_mark_reg_use_for_earlyclobber_1 (rtx *x, void *data) +static struct df_problem problem_CHAIN = +{ + DF_CHAIN, /* Problem id. */ + DF_NONE, /* Direction. */ + df_chain_alloc, /* Allocate the problem specific data. */ + df_chain_reset, /* Reset global information. */ + NULL, /* Free basic block info. */ + NULL, /* Local compute function. */ + NULL, /* Init the solution specific data. */ + NULL, /* Iterative solver. */ + NULL, /* Confluence operator 0. */ + NULL, /* Confluence operator n. */ + NULL, /* Transfer function. */ + df_chain_finalize, /* Finalize function. */ + df_chain_free, /* Free all of the problem information. */ + df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems. */ + NULL, /* Debugging. */ + df_chain_top_dump, /* Debugging start block. */ + df_chain_bottom_dump, /* Debugging end block. */ + NULL, /* Incremental solution verify start. */ + NULL, /* Incremental solution verify end. */ + &problem_RD, /* Dependent problem. */ + sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */ + TV_DF_CHAIN, /* 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_chain_add_problem (unsigned int chain_flags) { - for_each_rtx (x, df_urec_mark_reg_use_for_earlyclobber, data); + df_add_problem (&problem_CHAIN); + df_chain->local_flags = chain_flags; + df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (NULL); } +#undef df_chain_problem_p -/* Compute local uninitialized register info for basic block BB. */ + +/*---------------------------------------------------------------------------- + WORD LEVEL LIVE REGISTERS -static void -df_urec_bb_local_compute (struct dataflow *dflow, unsigned int bb_index) + 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. We only track pseudo registers that have a + size of 2 * UNITS_PER_WORD; bitmaps are indexed by 2 * regno and + contain two bits corresponding to each of the subwords. + + ----------------------------------------------------------------------------*/ + +/* Private data used to verify the solution for this problem. */ +struct df_word_lr_problem_data { - struct df *df = dflow->df; - basic_block bb = BASIC_BLOCK (bb_index); - struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index); - rtx insn; - struct df_ref *def; + /* An obstack for the bitmaps we need for this problem. */ + bitmap_obstack word_lr_bitmaps; +}; - for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref) - { - unsigned int regno = DF_REF_REGNO (def); - bitmap_set_bit (bb_info->gen, regno); - } - FOR_BB_INSNS (bb, insn) +/* Free basic block info. */ + +static void +df_word_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, + void *vbb_info) +{ + struct df_word_lr_bb_info *bb_info = (struct df_word_lr_bb_info *) vbb_info; + if (bb_info) { - if (INSN_P (insn)) - { - note_stores (PATTERN (insn), df_urec_mark_reg_change, bb_info); - if (df_state & (DF_SCAN_GLOBAL | DF_SCAN_POST_ALLOC) - && df_urec_check_earlyclobber (insn)) - { - struct df_urec_problem_data *problem_data = - (struct df_urec_problem_data *) dflow->problem_data; - problem_data->earlyclobbers_found = true; - note_uses (&PATTERN (insn), - df_urec_mark_reg_use_for_earlyclobber_1, bb_info); - } - } + bitmap_clear (&bb_info->use); + bitmap_clear (&bb_info->def); + bitmap_clear (&bb_info->in); + bitmap_clear (&bb_info->out); } } -/* Compute local uninitialized register info. */ +/* Allocate or reset bitmaps for DF_WORD_LR blocks. The solution bits are + not touched unless the block is new. */ static void -df_urec_local_compute (struct dataflow *dflow, - bitmap all_blocks ATTRIBUTE_UNUSED, - bitmap rescan_blocks) +df_word_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED) { unsigned int bb_index; bitmap_iterator bi; -#ifdef STACK_REGS - int i; - HARD_REG_SET zero, stack_hard_regs, used; - struct df_urec_problem_data *problem_data = - (struct df_urec_problem_data *) dflow->problem_data; - - /* Any register that MAY be allocated to a register stack (like the - 387) is treated poorly. Each such register is marked as being - live everywhere. This keeps the register allocator and the - subsequent passes from doing anything useful with these values. - - FIXME: This seems like an incredibly poor idea. */ - - CLEAR_HARD_REG_SET (zero); - CLEAR_HARD_REG_SET (stack_hard_regs); - for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++) - SET_HARD_REG_BIT (stack_hard_regs, i); - problem_data->stack_regs = BITMAP_ALLOC (NULL); - for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) - { - COPY_HARD_REG_SET (used, reg_class_contents[reg_preferred_class (i)]); - IOR_HARD_REG_SET (used, reg_class_contents[reg_alternate_class (i)]); - AND_HARD_REG_SET (used, stack_hard_regs); - GO_IF_HARD_REG_EQUAL (used, zero, skip); - bitmap_set_bit (problem_data->stack_regs, i); - skip: - ; - } -#endif + basic_block bb; + struct df_word_lr_problem_data *problem_data + = XNEW (struct df_word_lr_problem_data); - /* We know that earlyclobber_regclass holds no more than - N_REG_CLASSES elements. See df_urec_check_earlyclobber. */ - earlyclobber_regclass = VEC_alloc (int, heap, N_REG_CLASSES); + df_word_lr->problem_data = problem_data; - EXECUTE_IF_SET_IN_BITMAP (rescan_blocks, 0, bb_index, bi) - { - df_urec_bb_local_compute (dflow, bb_index); - } + df_grow_bb_info (df_word_lr); - VEC_free (int, heap, earlyclobber_regclass); -} + /* 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->word_lr_bitmaps); -/* Initialize the solution vectors. */ + FOR_EACH_BB (bb) + bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, bb->index); -static void -df_urec_init (struct dataflow *dflow, bitmap all_blocks) -{ - unsigned int bb_index; - bitmap_iterator bi; + bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, ENTRY_BLOCK); + bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, EXIT_BLOCK); - EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) + EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi) { - struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index); - - /* FIXME: This is a hack, it has been copied over from - make_accurate_live_analysis by Vlad. Most likely it is necessary - because the generation of gen and kill information for hardware - registers in ur is a subset of what is really necessary and what - is done for the lr problem. */ + struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index); - /* Inside the register allocator, partial availability is only - allowed for the psuedo registers. To implement this, the rr is - initially iored with a mask ones for the hard registers and zeros - for the pseudos before being iterated. This means that each - hardware register will be live unless explicitly killed by some - statement. Eventually most of these bit will die because the - results of rr are anded with the results of lr before being used. - Outside of register allocation, a more conservative strategy of - completely ignoring the unintialized registers is imployed in the - finalizer function. */ - if (df_state & DF_SCAN_GLOBAL) - { - bitmap_ior (bb_info->out, bb_info->gen, df_all_hard_regs); - bitmap_copy (bb_info->in, df_all_hard_regs); + /* When bitmaps are already initialized, just clear them. */ + if (bb_info->use.obstack) + { + bitmap_clear (&bb_info->def); + bitmap_clear (&bb_info->use); } else { - bitmap_copy (bb_info->out, bb_info->gen); - bitmap_clear (bb_info->in); + bitmap_initialize (&bb_info->use, &problem_data->word_lr_bitmaps); + bitmap_initialize (&bb_info->def, &problem_data->word_lr_bitmaps); + bitmap_initialize (&bb_info->in, &problem_data->word_lr_bitmaps); + bitmap_initialize (&bb_info->out, &problem_data->word_lr_bitmaps); } } + + df_word_lr->optional_p = true; } -/* Or in the stack regs, hard regs and early clobber regs into the the - ur_in sets of all of the blocks. */ +/* Reset the global solution for recalculation. */ static void -df_urec_local_finalize (struct dataflow *dflow, bitmap all_blocks) +df_word_lr_reset (bitmap all_blocks) { - struct df *df = dflow->df; - struct dataflow *lr_dflow = df->problems_by_index[DF_LR]; - bitmap tmp = BITMAP_ALLOC (NULL); - bitmap_iterator bi; unsigned int bb_index; - struct df_urec_problem_data *problem_data = - (struct df_urec_problem_data *) dflow->problem_data; + bitmap_iterator bi; EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) { - struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index); - struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (lr_dflow, bb_index); + struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index); + gcc_assert (bb_info); + bitmap_clear (&bb_info->in); + bitmap_clear (&bb_info->out); + } +} + +/* Examine REF, and if it is for a reg we're interested in, set or + clear the bits corresponding to its subwords from the bitmap + according to IS_SET. LIVE is the bitmap we should update. We do + not track hard regs or pseudos of any size other than 2 * + UNITS_PER_WORD. + We return true if we changed the bitmap, or if we encountered a register + we're not tracking. */ + +bool +df_word_lr_mark_ref (df_ref ref, bool is_set, regset live) +{ + rtx orig_reg = DF_REF_REG (ref); + rtx reg = orig_reg; + enum machine_mode reg_mode; + unsigned regno; + /* Left at -1 for whole accesses. */ + int which_subword = -1; + bool changed = false; + + if (GET_CODE (reg) == SUBREG) + reg = SUBREG_REG (orig_reg); + regno = REGNO (reg); + reg_mode = GET_MODE (reg); + if (regno < FIRST_PSEUDO_REGISTER + || GET_MODE_SIZE (reg_mode) != 2 * UNITS_PER_WORD) + return true; + + if (GET_CODE (orig_reg) == SUBREG + && df_read_modify_subreg_p (orig_reg)) + { + gcc_assert (DF_REF_FLAGS_IS_SET (ref, DF_REF_PARTIAL)); + if (subreg_lowpart_p (orig_reg)) + which_subword = 0; + else + which_subword = 1; + } + if (is_set) + { + if (which_subword != 1) + changed |= bitmap_set_bit (live, regno * 2); + if (which_subword != 0) + changed |= bitmap_set_bit (live, regno * 2 + 1); + } + else + { + if (which_subword != 1) + changed |= bitmap_clear_bit (live, regno * 2); + if (which_subword != 0) + changed |= bitmap_clear_bit (live, regno * 2 + 1); + } + return changed; +} + +/* Compute local live register info for basic block BB. */ + +static void +df_word_lr_bb_local_compute (unsigned int bb_index) +{ + basic_block bb = BASIC_BLOCK (bb_index); + struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index); + rtx insn; + df_ref *def_rec; + df_ref *use_rec; + + /* Ensure that artificial refs don't contain references to pseudos. */ + for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++) + { + df_ref def = *def_rec; + gcc_assert (DF_REF_REGNO (def) < FIRST_PSEUDO_REGISTER); + } + + for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++) + { + df_ref use = *use_rec; + gcc_assert (DF_REF_REGNO (use) < FIRST_PSEUDO_REGISTER); + } + + FOR_BB_INSNS_REVERSE (bb, insn) + { + unsigned int uid = INSN_UID (insn); - if (bb_index != ENTRY_BLOCK && bb_index != EXIT_BLOCK) + if (!NONDEBUG_INSN_P (insn)) + continue; + for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) { - if (problem_data->earlyclobbers_found) - bitmap_ior_into (bb_info->in, bb_info->earlyclobber); - -#ifdef STACK_REGS - /* We can not use the same stack register for uninitialized - pseudo-register and another living pseudo-register - because if the uninitialized pseudo-register dies, - subsequent pass reg-stack will be confused (it will - believe that the other register dies). */ - bitmap_ior_into (bb_info->in, problem_data->stack_regs); - bitmap_ior_into (bb_info->out, problem_data->stack_regs); -#endif + 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))) + { + df_word_lr_mark_ref (def, true, &bb_info->def); + df_word_lr_mark_ref (def, false, &bb_info->use); + } + } + for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++) + { + df_ref use = *use_rec; + df_word_lr_mark_ref (use, true, &bb_info->use); } + } +} + + +/* Compute local live register info for each basic block within BLOCKS. */ + +static void +df_word_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED) +{ + unsigned int bb_index; + bitmap_iterator bi; - if (!(df_state & DF_SCAN_GLOBAL)) + EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi) + { + if (bb_index == EXIT_BLOCK) { - bitmap_ior_into (bb_info->in, df_all_hard_regs); - bitmap_ior_into (bb_info->out, df_all_hard_regs); + unsigned regno; + bitmap_iterator bi; + EXECUTE_IF_SET_IN_BITMAP (df->exit_block_uses, FIRST_PSEUDO_REGISTER, + regno, bi) + gcc_unreachable (); } + else + df_word_lr_bb_local_compute (bb_index); + } - /* No register may reach a location where it is not used. Thus - we trim the rr result to the places where it is used. */ - bitmap_and_into (bb_info->in, bb_lr_info->in); - bitmap_and_into (bb_info->out, bb_lr_info->out); - -#if 1 - /* Hard registers may still stick in the ur_out set, but not - be in the ur_in set, if their only mention was in a call - in this block. This is because a call kills in the lr - problem but does not kill in the rr problem. To clean - this up, we execute the transfer function on the lr_in - set and then use that to knock bits out of ur_out. */ - bitmap_ior_and_compl (tmp, bb_info->gen, bb_lr_info->in, - bb_info->kill); - bitmap_and_into (bb_info->out, tmp); -#endif + bitmap_clear (df_word_lr->out_of_date_transfer_functions); +} + + +/* Initialize the solution vectors. */ + +static void +df_word_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_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index); + bitmap_copy (&bb_info->in, &bb_info->use); + bitmap_clear (&bb_info->out); } - -#ifdef STACK_REGS - BITMAP_FREE (problem_data->stack_regs); -#endif - BITMAP_FREE (tmp); } /* Confluence function that ignores fake edges. */ -static void -df_urec_confluence_n (struct dataflow *dflow, edge e) +static bool +df_word_lr_confluence_n (edge e) { - bitmap op1 = df_urec_get_bb_info (dflow, e->dest->index)->in; - bitmap op2 = df_urec_get_bb_info (dflow, e->src->index)->out; - - if (e->flags & EDGE_FAKE) - return; + bitmap op1 = &df_word_lr_get_bb_info (e->src->index)->out; + bitmap op2 = &df_word_lr_get_bb_info (e->dest->index)->in; - bitmap_ior_into (op1, op2); -} + return bitmap_ior_into (op1, op2); +} /* Transfer function. */ static bool -df_urec_transfer_function (struct dataflow *dflow, int bb_index) +df_word_lr_transfer_function (int bb_index) { - struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index); - bitmap in = bb_info->in; - bitmap out = bb_info->out; - bitmap gen = bb_info->gen; - bitmap kill = bb_info->kill; + struct df_word_lr_bb_info *bb_info = df_word_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 (out, gen, in, kill); + return bitmap_ior_and_compl (in, use, out, def); } /* Free all storage associated with the problem. */ static void -df_urec_free (struct dataflow *dflow) +df_word_lr_free (void) { - if (dflow->block_info) + struct df_word_lr_problem_data *problem_data + = (struct df_word_lr_problem_data *)df_word_lr->problem_data; + + if (df_word_lr->block_info) { - unsigned int i; - - for (i = 0; i < dflow->block_info_size; i++) + df_word_lr->block_info_size = 0; + free (df_word_lr->block_info); + df_word_lr->block_info = NULL; + } + + BITMAP_FREE (df_word_lr->out_of_date_transfer_functions); + bitmap_obstack_release (&problem_data->word_lr_bitmaps); + free (problem_data); + free (df_word_lr); +} + + +/* Debugging info at top of bb. */ + +static void +df_word_lr_top_dump (basic_block bb, FILE *file) +{ + struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb->index); + if (!bb_info) + return; + + fprintf (file, ";; blr in \t"); + df_print_word_regset (file, &bb_info->in); + fprintf (file, ";; blr use \t"); + df_print_word_regset (file, &bb_info->use); + fprintf (file, ";; blr def \t"); + df_print_word_regset (file, &bb_info->def); +} + + +/* Debugging info at bottom of bb. */ + +static void +df_word_lr_bottom_dump (basic_block bb, FILE *file) +{ + struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb->index); + if (!bb_info) + return; + + fprintf (file, ";; blr out \t"); + df_print_word_regset (file, &bb_info->out); +} + + +/* All of the information associated with every instance of the problem. */ + +static struct df_problem problem_WORD_LR = +{ + DF_WORD_LR, /* Problem id. */ + DF_BACKWARD, /* Direction. */ + df_word_lr_alloc, /* Allocate the problem specific data. */ + df_word_lr_reset, /* Reset global information. */ + df_word_lr_free_bb_info, /* Free basic block info. */ + df_word_lr_local_compute, /* Local compute function. */ + df_word_lr_init, /* Init the solution specific data. */ + df_worklist_dataflow, /* Worklist solver. */ + NULL, /* Confluence operator 0. */ + df_word_lr_confluence_n, /* Confluence operator n. */ + df_word_lr_transfer_function, /* Transfer function. */ + NULL, /* Finalize function. */ + df_word_lr_free, /* Free all of the problem information. */ + df_word_lr_free, /* Remove this problem from the stack of dataflow problems. */ + NULL, /* Debugging. */ + df_word_lr_top_dump, /* Debugging start block. */ + df_word_lr_bottom_dump, /* Debugging end block. */ + NULL, /* Incremental solution verify start. */ + NULL, /* Incremental solution verify end. */ + NULL, /* Dependent problem. */ + sizeof (struct df_word_lr_bb_info),/* Size of entry of block_info array. */ + TV_DF_WORD_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_word_lr_add_problem (void) +{ + df_add_problem (&problem_WORD_LR); + /* These will be initialized when df_scan_blocks processes each + block. */ + df_word_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL); +} + + +/* Simulate the effects of the defs of INSN on LIVE. Return true if we changed + any bits, which is used by the caller to determine whether a set is + necessary. We also return true if there are other reasons not to delete + an insn. */ + +bool +df_word_lr_simulate_defs (rtx insn, bitmap live) +{ + bool changed = false; + 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 (DF_REF_FLAGS (def) & DF_REF_CONDITIONAL) + changed = true; + else + changed |= df_word_lr_mark_ref (*def_rec, false, live); + } + return changed; +} + + +/* Simulate the effects of the uses of INSN on LIVE. */ + +void +df_word_lr_simulate_uses (rtx insn, bitmap live) +{ + df_ref *use_rec; + unsigned int uid = INSN_UID (insn); + + for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++) + df_word_lr_mark_ref (*use_rec, true, live); +} + +/*---------------------------------------------------------------------------- + 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. Remove also + REG_EQUAL/REG_EQUIV notes referring to dead pseudos using LIVE + as the bitmap of currently live registers. */ + +static void +df_kill_notes (rtx insn, bitmap live) +{ + rtx *pprev = ®_NOTES (insn); + rtx link = *pprev; + + while (link) + { + switch (REG_NOTE_KIND (link)) { - struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, i); - if (bb_info) + 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 + free_EXPR_LIST_node (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 { - BITMAP_FREE (bb_info->gen); - BITMAP_FREE (bb_info->kill); - BITMAP_FREE (bb_info->in); - BITMAP_FREE (bb_info->out); - BITMAP_FREE (bb_info->earlyclobber); + rtx next = XEXP (link, 1); +#ifdef REG_DEAD_DEBUGGING + df_print_note ("deleting: ", insn, link); +#endif + free_EXPR_LIST_node (link); + *pprev = link = next; } + break; + + case REG_EQUAL: + case REG_EQUIV: + { + /* Remove the notes that refer to dead registers. As we have at most + one REG_EQUAL/EQUIV note, all of EQ_USES will refer to this note + so we need to purge the complete EQ_USES vector when removing + the note using df_notes_rescan. */ + df_ref *use_rec; + bool deleted = false; + + for (use_rec = DF_INSN_EQ_USES (insn); *use_rec; use_rec++) + { + df_ref use = *use_rec; + if (DF_REF_REGNO (use) > FIRST_PSEUDO_REGISTER + && DF_REF_LOC (use) + && (DF_REF_FLAGS (use) & DF_REF_IN_NOTE) + && ! bitmap_bit_p (live, DF_REF_REGNO (use)) + && loc_mentioned_in_p (DF_REF_LOC (use), XEXP (link, 0))) + { + deleted = true; + break; + } + } + if (deleted) + { + rtx next; +#ifdef REG_DEAD_DEBUGGING + df_print_note ("deleting: ", insn, link); +#endif + next = XEXP (link, 1); + free_EXPR_LIST_node (link); + *pprev = link = next; + df_notes_rescan (insn); + } + else + { + pprev = &XEXP (link, 1); + link = *pprev; + } + break; + } + default: + pprev = &XEXP (link, 1); + link = *pprev; + break; } - - free_alloc_pool (dflow->block_pool); - - dflow->block_info_size = 0; - free (dflow->block_info); - free (dflow->problem_data); } - free (dflow); } -/* Debugging info. */ +/* Set a NOTE_TYPE note for REG in INSN. */ + +static inline void +df_set_note (enum reg_note note_type, rtx insn, rtx reg) +{ + gcc_checking_assert (!DEBUG_INSN_P (insn)); + add_reg_note (insn, note_type, reg); +} + +/* 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; +} + + +/* Node of a linked list of uses of dead REGs in debug insns. */ +struct dead_debug_use +{ + df_ref use; + struct dead_debug_use *next; +}; + +/* Linked list of the above, with a bitmap of the REGs in the + list. */ +struct dead_debug +{ + struct dead_debug_use *head; + bitmap used; + bitmap to_rescan; +}; + +static void dead_debug_reset (struct dead_debug *, unsigned int); + + +/* 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 void -df_urec_dump (struct dataflow *dflow, FILE *file) +df_set_unused_notes_for_mw (rtx insn, struct df_mw_hardreg *mws, + bitmap live, bitmap do_not_gen, + bitmap artificial_uses, + struct dead_debug *debug) { - basic_block bb; - - fprintf (file, "Undefined regs:\n"); - - FOR_ALL_BB (bb) + 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 + + if (df_whole_mw_reg_unused_p (mws, live, artificial_uses)) { - struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb->index); - df_print_bb_index (bb, file); - - if (! bb_info->in) - continue; - - fprintf (file, " in \t"); - dump_bitmap (file, bb_info->in); - fprintf (file, " gen \t"); - dump_bitmap (file, bb_info->gen); - fprintf (file, " kill\t"); - dump_bitmap (file, bb_info->kill); - fprintf (file, " ec\t"); - dump_bitmap (file, bb_info->earlyclobber); - fprintf (file, " out \t"); - dump_bitmap (file, bb_info->out); + unsigned int regno = mws->start_regno; + df_set_note (REG_UNUSED, insn, mws->mw_reg); + dead_debug_reset (debug, regno); + +#ifdef REG_DEAD_DEBUGGING + df_print_note ("adding 1: ", insn, REG_NOTES (insn)); +#endif + bitmap_set_bit (do_not_gen, regno); + /* Only do this if the value is totally dead. */ + } + else + for (r = mws->start_regno; r <= mws->end_regno; r++) + { + if (!bitmap_bit_p (live, r) + && !bitmap_bit_p (artificial_uses, r)) + { + df_set_note (REG_UNUSED, insn, regno_reg_rtx[r]); + dead_debug_reset (debug, r); +#ifdef REG_DEAD_DEBUGGING + df_print_note ("adding 2: ", insn, REG_NOTES (insn)); +#endif + } + bitmap_set_bit (do_not_gen, r); + } +} + + +/* A subroutine of df_set_dead_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 dead, and if mw_reg can therefore + be used in a REG_DEAD note. */ + +static bool +df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws, + bitmap live, bitmap artificial_uses, + bitmap do_not_gen) +{ + unsigned int r; + + /* If MWS describes a partial reference, create REG_DEAD notes for + individual hard registers. */ + if (mws->flags & DF_REF_PARTIAL) + return false; + + /* Likewise if some part of the register is not dead. */ + for (r = mws->start_regno; r <= mws->end_regno; r++) + if (bitmap_bit_p (live, r) + || bitmap_bit_p (artificial_uses, r) + || bitmap_bit_p (do_not_gen, r)) + return false; + + gcc_assert (REG_P (mws->mw_reg)); + return true; +} + +/* Set the REG_DEAD notes for the multiword hardreg use in INSN based + on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes + from being set if the instruction both reads and writes the + register. */ + +static void +df_set_dead_notes_for_mw (rtx insn, struct df_mw_hardreg *mws, + bitmap live, bitmap do_not_gen, + bitmap artificial_uses, bool *added_notes_p) +{ + unsigned int r; + bool is_debug = *added_notes_p; + + *added_notes_p = false; + +#ifdef REG_DEAD_DEBUGGING + if (dump_file) + { + fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n do_not_gen =", + mws->start_regno, mws->end_regno); + df_print_regset (dump_file, do_not_gen); + fprintf (dump_file, " live ="); + df_print_regset (dump_file, live); + fprintf (dump_file, " artificial uses ="); + df_print_regset (dump_file, artificial_uses); + } +#endif + + if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen)) + { + /* Add a dead note for the entire multi word register. */ + if (is_debug) + { + *added_notes_p = true; + return; + } + df_set_note (REG_DEAD, insn, mws->mw_reg); +#ifdef REG_DEAD_DEBUGGING + df_print_note ("adding 1: ", insn, REG_NOTES (insn)); +#endif + } + else + { + for (r = mws->start_regno; r <= mws->end_regno; r++) + if (!bitmap_bit_p (live, r) + && !bitmap_bit_p (artificial_uses, r) + && !bitmap_bit_p (do_not_gen, r)) + { + if (is_debug) + { + *added_notes_p = true; + return; + } + df_set_note (REG_DEAD, insn, regno_reg_rtx[r]); +#ifdef REG_DEAD_DEBUGGING + df_print_note ("adding 2: ", insn, REG_NOTES (insn)); +#endif + } + } + return; +} + + +/* Create a REG_UNUSED note if necessary for DEF in INSN updating + LIVE. Do not generate notes for registers in ARTIFICIAL_USES. */ + +static void +df_create_unused_note (rtx insn, df_ref def, + bitmap live, bitmap artificial_uses, + struct dead_debug *debug) +{ + unsigned int dregno = DF_REF_REGNO (def); + +#ifdef REG_DEAD_DEBUGGING + if (dump_file) + { + fprintf (dump_file, " regular looking at def "); + df_ref_debug (def, dump_file); + } +#endif + + if (!((DF_REF_FLAGS (def) & DF_REF_MW_HARDREG) + || bitmap_bit_p (live, dregno) + || bitmap_bit_p (artificial_uses, dregno) + || df_ignore_stack_reg (dregno))) + { + rtx reg = (DF_REF_LOC (def)) + ? *DF_REF_REAL_LOC (def): DF_REF_REG (def); + df_set_note (REG_UNUSED, insn, reg); + dead_debug_reset (debug, dregno); +#ifdef REG_DEAD_DEBUGGING + df_print_note ("adding 3: ", insn, REG_NOTES (insn)); +#endif + } + + return; +} + + +/* Initialize DEBUG to an empty list, and clear USED, if given. */ +static inline void +dead_debug_init (struct dead_debug *debug, bitmap used) +{ + debug->head = NULL; + debug->used = used; + debug->to_rescan = NULL; + if (used) + bitmap_clear (used); +} + +/* Reset all debug insns with pending uses. Release the bitmap in it, + unless it is USED. USED must be the same bitmap passed to + dead_debug_init. */ +static inline void +dead_debug_finish (struct dead_debug *debug, bitmap used) +{ + struct dead_debug_use *head; + rtx insn = NULL; + + if (debug->used != used) + BITMAP_FREE (debug->used); + + while ((head = debug->head)) + { + insn = DF_REF_INSN (head->use); + if (!head->next || DF_REF_INSN (head->next->use) != insn) + { + INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC (); + df_insn_rescan_debug_internal (insn); + if (debug->to_rescan) + bitmap_clear_bit (debug->to_rescan, INSN_UID (insn)); + } + debug->head = head->next; + XDELETE (head); + } + + if (debug->to_rescan) + { + bitmap_iterator bi; + unsigned int uid; + + EXECUTE_IF_SET_IN_BITMAP (debug->to_rescan, 0, uid, bi) + { + struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid); + if (insn_info) + df_insn_rescan (insn_info->insn); + } + BITMAP_FREE (debug->to_rescan); + } +} + +/* Reset DEBUG_INSNs with pending uses of DREGNO. */ +static void +dead_debug_reset (struct dead_debug *debug, unsigned int dregno) +{ + struct dead_debug_use **tailp = &debug->head; + struct dead_debug_use **insnp = &debug->head; + struct dead_debug_use *cur; + rtx insn; + + if (!debug->used || !bitmap_clear_bit (debug->used, dregno)) + return; + + while ((cur = *tailp)) + { + if (DF_REF_REGNO (cur->use) == dregno) + { + *tailp = cur->next; + insn = DF_REF_INSN (cur->use); + INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC (); + if (debug->to_rescan == NULL) + debug->to_rescan = BITMAP_ALLOC (NULL); + bitmap_set_bit (debug->to_rescan, INSN_UID (insn)); + XDELETE (cur); + /* If the current use isn't the first one attached to INSN, go back + to this first use. We assume that the uses attached to an insn + are adjacent. */ + if (tailp != insnp && DF_REF_INSN ((*insnp)->use) == insn) + tailp = insnp; + /* Then remove all the other uses attached to INSN. */ + while ((cur = *tailp) && DF_REF_INSN (cur->use) == insn) + { + *tailp = cur->next; + XDELETE (cur); + } + insnp = tailp; + } + else + { + if (DF_REF_INSN ((*insnp)->use) != DF_REF_INSN (cur->use)) + insnp = tailp; + tailp = &(*tailp)->next; + } + } +} + +/* Add USE to DEBUG. It must be a dead reference to UREGNO in a debug + insn. Create a bitmap for DEBUG as needed. */ +static inline void +dead_debug_add (struct dead_debug *debug, df_ref use, unsigned int uregno) +{ + struct dead_debug_use *newddu = XNEW (struct dead_debug_use); + + newddu->use = use; + newddu->next = debug->head; + debug->head = newddu; + + if (!debug->used) + debug->used = BITMAP_ALLOC (NULL); + + bitmap_set_bit (debug->used, uregno); +} + +/* If UREGNO is referenced by any entry in DEBUG, emit a debug insn + before INSN that binds the REG to a debug temp, and replace all + uses of UREGNO in DEBUG with uses of the debug temp. INSN must be + the insn where UREGNO dies. */ +static inline void +dead_debug_insert_before (struct dead_debug *debug, unsigned int uregno, + rtx insn) +{ + struct dead_debug_use **tailp = &debug->head; + struct dead_debug_use *cur; + struct dead_debug_use *uses = NULL; + struct dead_debug_use **usesp = &uses; + rtx reg = NULL; + rtx dval; + rtx bind; + + if (!debug->used || !bitmap_clear_bit (debug->used, uregno)) + return; + + /* Move all uses of uregno from debug->head to uses, setting mode to + the widest referenced mode. */ + while ((cur = *tailp)) + { + if (DF_REF_REGNO (cur->use) == uregno) + { + *usesp = cur; + usesp = &cur->next; + *tailp = cur->next; + cur->next = NULL; + if (!reg + || (GET_MODE_BITSIZE (GET_MODE (reg)) + < GET_MODE_BITSIZE (GET_MODE (*DF_REF_REAL_LOC (cur->use))))) + reg = *DF_REF_REAL_LOC (cur->use); + } + else + tailp = &(*tailp)->next; + } + + /* We may have dangling bits in debug->used for registers that were part + of a multi-register use, one component of which has been reset. */ + if (reg == NULL) + return; + + /* Create DEBUG_EXPR (and DEBUG_EXPR_DECL). */ + dval = make_debug_expr_from_rtl (reg); + + /* Emit a debug bind insn before the insn in which reg dies. */ + bind = gen_rtx_VAR_LOCATION (GET_MODE (reg), + DEBUG_EXPR_TREE_DECL (dval), reg, + VAR_INIT_STATUS_INITIALIZED); + + bind = emit_debug_insn_before (bind, insn); + df_insn_rescan (bind); + + /* Adjust all uses. */ + while ((cur = uses)) + { + if (GET_MODE (*DF_REF_REAL_LOC (cur->use)) == GET_MODE (reg)) + *DF_REF_REAL_LOC (cur->use) = dval; + else + *DF_REF_REAL_LOC (cur->use) + = gen_lowpart_SUBREG (GET_MODE (*DF_REF_REAL_LOC (cur->use)), dval); + /* ??? Should we simplify subreg of subreg? */ + if (debug->to_rescan == NULL) + debug->to_rescan = BITMAP_ALLOC (NULL); + bitmap_set_bit (debug->to_rescan, INSN_UID (DF_REF_INSN (cur->use))); + uses = cur->next; + XDELETE (cur); + } +} + +/* Recompute the REG_DEAD and REG_UNUSED notes and compute register + info: lifetime, bb, and number of defs and uses for basic block + BB. The three bitvectors are scratch regs used here. */ + +static void +df_note_bb_compute (unsigned int bb_index, + bitmap live, bitmap do_not_gen, bitmap artificial_uses) +{ + basic_block bb = BASIC_BLOCK (bb_index); + rtx insn; + df_ref *def_rec; + df_ref *use_rec; + struct dead_debug debug; + + dead_debug_init (&debug, NULL); + + bitmap_copy (live, df_get_live_out (bb)); + bitmap_clear (artificial_uses); + +#ifdef REG_DEAD_DEBUGGING + if (dump_file) + { + fprintf (dump_file, "live at bottom "); + df_print_regset (dump_file, live); + } +#endif + + /* Process the artificial defs and uses at the bottom of the block + to begin processing. */ + for (def_rec = df_get_artificial_defs (bb_index); *def_rec; 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)); +#endif + + if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0) + bitmap_clear_bit (live, DF_REF_REGNO (def)); + } + + 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 regno = DF_REF_REGNO (use); + bitmap_set_bit (live, regno); + + /* Notes are not generated for any of the artificial registers + at the bottom of the block. */ + bitmap_set_bit (artificial_uses, regno); + } + } + +#ifdef REG_DEAD_DEBUGGING + if (dump_file) + { + fprintf (dump_file, "live before artificials out "); + df_print_regset (dump_file, live); + } +#endif + + FOR_BB_INSNS_REVERSE (bb, insn) + { + unsigned int uid = INSN_UID (insn); + struct df_mw_hardreg **mws_rec; + int debug_insn; + + if (!INSN_P (insn)) + continue; + + debug_insn = DEBUG_INSN_P (insn); + + bitmap_clear (do_not_gen); + df_kill_notes (insn, live); + + /* Process the defs. */ + if (CALL_P (insn)) + { +#ifdef REG_DEAD_DEBUGGING + if (dump_file) + { + fprintf (dump_file, "processing call %d\n live =", INSN_UID (insn)); + df_print_regset (dump_file, live); + } +#endif + /* We only care about real sets for calls. Clobbers cannot + be depended on to really die. */ + mws_rec = DF_INSN_UID_MWS (uid); + while (*mws_rec) + { + struct df_mw_hardreg *mws = *mws_rec; + if ((DF_MWS_REG_DEF_P (mws)) + && !df_ignore_stack_reg (mws->start_regno)) + df_set_unused_notes_for_mw (insn, + mws, live, do_not_gen, + artificial_uses, &debug); + mws_rec++; + } + + /* All of the defs except the return value are some sort of + clobber. This code is for the return. */ + 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_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)) + { + df_create_unused_note (insn, + def, live, artificial_uses, &debug); + bitmap_set_bit (do_not_gen, dregno); + } + + if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL)) + bitmap_clear_bit (live, dregno); + } + } + else + { + /* Regular insn. */ + mws_rec = DF_INSN_UID_MWS (uid); + while (*mws_rec) + { + struct df_mw_hardreg *mws = *mws_rec; + if (DF_MWS_REG_DEF_P (mws)) + df_set_unused_notes_for_mw (insn, + mws, live, do_not_gen, + artificial_uses, &debug); + mws_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); + df_create_unused_note (insn, + def, live, artificial_uses, &debug); + + if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)) + bitmap_set_bit (do_not_gen, dregno); + + if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL)) + bitmap_clear_bit (live, dregno); + } + } + + /* Process the uses. */ + mws_rec = DF_INSN_UID_MWS (uid); + while (*mws_rec) + { + struct df_mw_hardreg *mws = *mws_rec; + if (DF_MWS_REG_USE_P (mws) + && !df_ignore_stack_reg (mws->start_regno)) + { + bool really_add_notes = debug_insn != 0; + + df_set_dead_notes_for_mw (insn, + mws, live, do_not_gen, + artificial_uses, + &really_add_notes); + + if (really_add_notes) + debug_insn = -1; + } + mws_rec++; + } + + for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++) + { + df_ref use = *use_rec; + unsigned int uregno = DF_REF_REGNO (use); + +#ifdef REG_DEAD_DEBUGGING + if (dump_file && !debug_insn) + { + fprintf (dump_file, " regular looking at use "); + df_ref_debug (use, dump_file); + } +#endif + if (!bitmap_bit_p (live, uregno)) + { + if (debug_insn) + { + if (debug_insn > 0) + { + dead_debug_add (&debug, use, uregno); + continue; + } + break; + } + else + dead_debug_insert_before (&debug, uregno, insn); + + if ( (!(DF_REF_FLAGS (use) + & (DF_REF_MW_HARDREG | DF_REF_READ_WRITE))) + && (!bitmap_bit_p (do_not_gen, uregno)) + && (!bitmap_bit_p (artificial_uses, uregno)) + && (!df_ignore_stack_reg (uregno))) + { + rtx reg = (DF_REF_LOC (use)) + ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use); + df_set_note (REG_DEAD, insn, reg); + +#ifdef REG_DEAD_DEBUGGING + df_print_note ("adding 4: ", insn, REG_NOTES (insn)); +#endif + } + /* This register is now live. */ + bitmap_set_bit (live, uregno); + } + } + + if (debug_insn == -1) + { + /* ??? We could probably do better here, replacing dead + registers with their definitions. */ + INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC (); + df_insn_rescan_debug_internal (insn); + } + } + + dead_debug_finish (&debug, NULL); +} + + +/* Compute register info: lifetime, bb, and number of defs and uses. */ +static void +df_note_compute (bitmap all_blocks) +{ + unsigned int bb_index; + bitmap_iterator bi; + bitmap_head live, do_not_gen, artificial_uses; + + bitmap_initialize (&live, &df_bitmap_obstack); + bitmap_initialize (&do_not_gen, &df_bitmap_obstack); + bitmap_initialize (&artificial_uses, &df_bitmap_obstack); + +#ifdef REG_DEAD_DEBUGGING + if (dump_file) + print_rtl_with_bb (dump_file, get_insns()); +#endif + + EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) + { + df_note_bb_compute (bb_index, &live, &do_not_gen, &artificial_uses); + } + + bitmap_clear (&live); + bitmap_clear (&do_not_gen); + bitmap_clear (&artificial_uses); +} + + +/* Free all storage associated with the problem. */ + +static void +df_note_free (void) +{ + free (df_note); +} + + +/* All of the information associated every instance of the problem. */ + +static struct df_problem problem_NOTE = +{ + DF_NOTE, /* Problem id. */ + DF_NONE, /* Direction. */ + df_note_alloc, /* Allocate the problem specific data. */ + NULL, /* Reset global information. */ + NULL, /* Free basic block info. */ + df_note_compute, /* Local compute function. */ + NULL, /* Init the solution specific data. */ + NULL, /* Iterative solver. */ + NULL, /* Confluence operator 0. */ + NULL, /* Confluence operator n. */ + NULL, /* Transfer function. */ + NULL, /* Finalize function. */ + df_note_free, /* Free all of the problem information. */ + df_note_free, /* Remove this problem from the stack of dataflow problems. */ + NULL, /* Debugging. */ + NULL, /* Debugging start block. */ + NULL, /* Debugging end block. */ + NULL, /* Incremental solution verify start. */ + NULL, /* Incremental solution verify end. */ + &problem_LR, /* Dependent problem. */ + sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */ + TV_DF_NOTE, /* 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_note_add_problem (void) +{ + df_add_problem (&problem_NOTE); +} + + + + +/*---------------------------------------------------------------------------- + Functions for simulating the effects of single insns. + + You can either simulate in the forwards direction, starting from + the top of a block or the backwards direction from the end of the + block. If you go backwards, defs are examined first to clear bits, + then uses are examined to set bits. If you go forwards, defs are + examined first to set bits, then REG_DEAD and REG_UNUSED notes + are examined to clear bits. In either case, the result of examining + a def can be undone (respectively by a use or a REG_UNUSED note). + + If you start at the top of the block, use one of DF_LIVE_IN or + 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. +----------------------------------------------------------------------------*/ + + +/* Find the set of DEFs for INSN. */ + +void +df_simulate_find_defs (rtx insn, bitmap defs) +{ + 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; + bitmap_set_bit (defs, DF_REF_REGNO (def)); + } +} + +/* Find the set of uses for INSN. This includes partial defs. */ + +static void +df_simulate_find_uses (rtx insn, bitmap uses) +{ + df_ref *rec; + unsigned int uid = INSN_UID (insn); + + for (rec = DF_INSN_UID_DEFS (uid); *rec; rec++) + { + df_ref def = *rec; + if (DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)) + bitmap_set_bit (uses, DF_REF_REGNO (def)); + } + for (rec = DF_INSN_UID_USES (uid); *rec; rec++) + { + df_ref use = *rec; + bitmap_set_bit (uses, DF_REF_REGNO (use)); + } +} + +/* Find the set of real DEFs, which are not clobbers, for INSN. */ + +void +df_simulate_find_noclobber_defs (rtx insn, bitmap defs) +{ + 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 (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))) + bitmap_set_bit (defs, DF_REF_REGNO (def)); + } +} + + +/* Simulate the effects of the defs of INSN on LIVE. */ + +void +df_simulate_defs (rtx insn, bitmap live) +{ + 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; + unsigned int dregno = DF_REF_REGNO (def); + + /* 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))) + bitmap_clear_bit (live, dregno); + } +} + + +/* Simulate the effects of the uses of INSN on LIVE. */ + +void +df_simulate_uses (rtx insn, bitmap live) +{ + df_ref *use_rec; + unsigned int uid = INSN_UID (insn); + + if (DEBUG_INSN_P (insn)) + return; + + for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++) + { + df_ref use = *use_rec; + /* Add use to set of uses in this BB. */ + bitmap_set_bit (live, DF_REF_REGNO (use)); + } +} + + +/* Add back the always live regs in BB to LIVE. */ + +static inline void +df_simulate_fixup_sets (basic_block bb, bitmap live) +{ + /* These regs are considered always live so if they end up dying + because of some def, we need to bring the back again. */ + if (bb_has_eh_pred (bb)) + bitmap_ior_into (live, &df->eh_block_artificial_uses); + else + bitmap_ior_into (live, &df->regular_block_artificial_uses); +} + + +/*---------------------------------------------------------------------------- + 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 one. 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_initialize_backwards (basic_block bb, bitmap live) +{ + 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) + bitmap_clear_bit (live, DF_REF_REGNO (def)); + } + + 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) + bitmap_set_bit (live, DF_REF_REGNO (use)); + } +} + + +/* Simulate the backwards effects of INSN on the bitmap LIVE. */ + +void +df_simulate_one_insn_backwards (basic_block bb, rtx insn, bitmap live) +{ + if (!NONDEBUG_INSN_P (insn)) + return; + + df_simulate_defs (insn, live); + df_simulate_uses (insn, live); + df_simulate_fixup_sets (bb, live); +} + + +/* Apply the artificial uses and defs at the top of BB in a backwards + direction. */ + +void +df_simulate_finalize_backwards (basic_block bb, bitmap live) +{ + 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++) + { + 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++) + { + 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 first one. + ----------------------------------------------------------------------------*/ + +/* Initialize the LIVE bitmap, which should be copied from DF_LIVE_IN or + DF_LR_IN for basic block BB, for forward scanning by marking artificial + defs live. */ + +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_set_bit (live, DF_REF_REGNO (def)); + } +} + +/* Simulate the forwards effects of INSN on the bitmap LIVE. */ + +void +df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live) +{ + rtx link; + if (! INSN_P (insn)) + return; + + /* Make sure that DF_NOTE really is an active df problem. */ + gcc_assert (df_note); + + /* Note that this is the opposite as how the problem is defined, because + in the LR problem defs _kill_ liveness. However, they do so backwards, + while here the scan is performed forwards! So, first assume that the + def is live, and if this is not true REG_UNUSED notes will rectify the + situation. */ + df_simulate_find_noclobber_defs (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 (HARD_REGISTER_NUM_P (regno)) + bitmap_clear_range (live, regno, + hard_regno_nregs[regno][GET_MODE (reg)]); + else + bitmap_clear_bit (live, regno); + } + break; + default: + break; + } } + df_simulate_fixup_sets (bb, live); } + +/* Used by the next two functions to encode information about the + memory references we found. */ +#define MEMREF_NORMAL 1 +#define MEMREF_VOLATILE 2 -/* All of the information associated with every instance of the problem. */ +/* A subroutine of can_move_insns_across_p called through for_each_rtx. + Return either MEMREF_NORMAL or MEMREF_VOLATILE if a memory is found. */ -static struct df_problem problem_UREC = +static int +find_memory (rtx *px, void *data ATTRIBUTE_UNUSED) { - DF_UREC, /* Problem id. */ - DF_FORWARD, /* Direction. */ - df_urec_alloc, /* Allocate the problem specific data. */ - df_urec_free_bb_info, /* Free basic block info. */ - df_urec_local_compute, /* Local compute function. */ - df_urec_init, /* Init the solution specific data. */ - df_iterative_dataflow, /* Iterative solver. */ - NULL, /* Confluence operator 0. */ - df_urec_confluence_n, /* Confluence operator n. */ - df_urec_transfer_function, /* Transfer function. */ - df_urec_local_finalize, /* Finalize function. */ - df_urec_free, /* Free all of the problem information. */ - df_urec_dump, /* Debugging. */ - &problem_LR /* Dependent problem. */ -}; + rtx x = *px; + if (GET_CODE (x) == ASM_OPERANDS && MEM_VOLATILE_P (x)) + return MEMREF_VOLATILE; -/* 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. */ + if (!MEM_P (x)) + return 0; + if (MEM_VOLATILE_P (x)) + return MEMREF_VOLATILE; + if (MEM_READONLY_P (x)) + return 0; -struct dataflow * -df_urec_add_problem (struct df *df) -{ - return df_add_problem (df, &problem_UREC); + return MEMREF_NORMAL; } +/* A subroutine of can_move_insns_across_p called through note_stores. + DATA points to an integer in which we set either the bit for + MEMREF_NORMAL or the bit for MEMREF_VOLATILE if we find a MEM + of either kind. */ - -/*---------------------------------------------------------------------------- - CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS - - Link either the defs to the uses and / or the uses to the defs. +static void +find_memory_stores (rtx x, const_rtx pat ATTRIBUTE_UNUSED, + void *data ATTRIBUTE_UNUSED) +{ + int *pflags = (int *)data; + if (GET_CODE (x) == SUBREG) + x = XEXP (x, 0); + /* Treat stores to SP as stores to memory, this will prevent problems + when there are references to the stack frame. */ + if (x == stack_pointer_rtx) + *pflags |= MEMREF_VOLATILE; + if (!MEM_P (x)) + return; + *pflags |= MEM_VOLATILE_P (x) ? MEMREF_VOLATILE : MEMREF_NORMAL; +} - These problems are set up like the other dataflow problems so that - they nicely fit into the framework. They are much simpler and only - involve a single traversal of instructions and an examination of - the reaching defs information (the dependent problem). -----------------------------------------------------------------------------*/ +/* Scan BB backwards, using df_simulate functions to keep track of + lifetimes, up to insn POINT. The result is stored in LIVE. */ -struct df_chain_problem_data +void +simulate_backwards_to_point (basic_block bb, regset live, rtx point) { - int flags; -}; - + rtx insn; + bitmap_copy (live, df_get_live_out (bb)); + df_simulate_initialize_backwards (bb, live); -/* Create def-use or use-def chains. */ + /* Scan and update life information until we reach the point we're + interested in. */ + for (insn = BB_END (bb); insn != point; insn = PREV_INSN (insn)) + df_simulate_one_insn_backwards (bb, insn, live); +} -static void -df_chain_alloc (struct dataflow *dflow, - bitmap blocks_to_rescan ATTRIBUTE_UNUSED) +/* Return true if it is safe to move a group of insns, described by + the range FROM to TO, backwards across another group of insns, + described by ACROSS_FROM to ACROSS_TO. It is assumed that there + are no insns between ACROSS_TO and FROM, but they may be in + different basic blocks; MERGE_BB is the block from which the + insns will be moved. The caller must pass in a regset MERGE_LIVE + which specifies the registers live after TO. + + This function may be called in one of two cases: either we try to + move identical instructions from all successor blocks into their + predecessor, or we try to move from only one successor block. If + OTHER_BRANCH_LIVE is nonnull, it indicates that we're dealing with + the second case. It should contain a set of registers live at the + end of ACROSS_TO which must not be clobbered by moving the insns. + In that case, we're also more careful about moving memory references + and trapping insns. + + We return false if it is not safe to move the entire group, but it + may still be possible to move a subgroup. PMOVE_UPTO, if nonnull, + is set to point at the last moveable insn in such a case. */ + +bool +can_move_insns_across (rtx from, rtx to, rtx across_from, rtx across_to, + basic_block merge_bb, regset merge_live, + regset other_branch_live, rtx *pmove_upto) { - struct df *df = dflow->df; - unsigned int i; - struct df_chain_problem_data *problem_data = - (struct df_chain_problem_data *) dflow->problem_data; + rtx insn, next, max_to; + bitmap merge_set, merge_use, local_merge_live; + bitmap test_set, test_use; + unsigned i, fail = 0; + bitmap_iterator bi; + int memrefs_in_across = 0; + int mem_sets_in_across = 0; + bool trapping_insns_in_across = false; - /* Wholesale destruction of the old chains. */ - if (dflow->block_pool) - free_alloc_pool (dflow->block_pool); + if (pmove_upto != NULL) + *pmove_upto = NULL_RTX; - dflow->block_pool = create_alloc_pool ("df_chain_chain_block pool", - sizeof (struct df_link), 100); + /* Find real bounds, ignoring debug insns. */ + while (!NONDEBUG_INSN_P (from) && from != to) + from = NEXT_INSN (from); + while (!NONDEBUG_INSN_P (to) && from != to) + to = PREV_INSN (to); - if (problem_data->flags & DF_DU_CHAIN) + for (insn = across_to; ; insn = next) { - if (!df->def_info.refs_organized) - df_reorganize_refs (&df->def_info); - - /* Clear out the pointers from the refs. */ - for (i = 0; i < DF_DEFS_SIZE (df); i++) + if (CALL_P (insn)) { - struct df_ref *ref = df->def_info.refs[i]; - DF_REF_CHAIN (ref) = NULL; + if (RTL_CONST_OR_PURE_CALL_P (insn)) + /* Pure functions can read from memory. Const functions can + read from arguments that the ABI has forced onto the stack. + Neither sort of read can be volatile. */ + memrefs_in_across |= MEMREF_NORMAL; + else + { + memrefs_in_across |= MEMREF_VOLATILE; + mem_sets_in_across |= MEMREF_VOLATILE; + } + } + if (NONDEBUG_INSN_P (insn)) + { + memrefs_in_across |= for_each_rtx (&PATTERN (insn), find_memory, + NULL); + note_stores (PATTERN (insn), find_memory_stores, + &mem_sets_in_across); + /* This is used just to find sets of the stack pointer. */ + memrefs_in_across |= mem_sets_in_across; + trapping_insns_in_across |= may_trap_p (PATTERN (insn)); } + next = PREV_INSN (insn); + if (insn == across_from) + break; } - - if (problem_data->flags & DF_UD_CHAIN) + + /* Collect: + MERGE_SET = set of registers set in MERGE_BB + MERGE_USE = set of registers used in MERGE_BB and live at its top + MERGE_LIVE = set of registers live at the point inside the MERGE + range that we've reached during scanning + TEST_SET = set of registers set between ACROSS_FROM and ACROSS_END. + TEST_USE = set of registers used between ACROSS_FROM and ACROSS_END, + and live before ACROSS_FROM. */ + + merge_set = BITMAP_ALLOC (®_obstack); + merge_use = BITMAP_ALLOC (®_obstack); + local_merge_live = BITMAP_ALLOC (®_obstack); + test_set = BITMAP_ALLOC (®_obstack); + test_use = BITMAP_ALLOC (®_obstack); + + /* Compute the set of registers set and used in the ACROSS range. */ + if (other_branch_live != NULL) + bitmap_copy (test_use, other_branch_live); + df_simulate_initialize_backwards (merge_bb, test_use); + for (insn = across_to; ; insn = next) { - if (!df->use_info.refs_organized) - df_reorganize_refs (&df->use_info); - for (i = 0; i < DF_USES_SIZE (df); i++) + if (NONDEBUG_INSN_P (insn)) { - struct df_ref *ref = df->use_info.refs[i]; - DF_REF_CHAIN (ref) = NULL; + df_simulate_find_defs (insn, test_set); + df_simulate_defs (insn, test_use); + df_simulate_uses (insn, test_use); } + next = PREV_INSN (insn); + if (insn == across_from) + break; } -} - -/* Create the chains for a list of USEs. */ + /* Compute an upper bound for the amount of insns moved, by finding + the first insn in MERGE that sets a register in TEST_USE, or uses + a register in TEST_SET. We also check for calls, trapping operations, + and memory references. */ + max_to = NULL_RTX; + for (insn = from; ; insn = next) + { + if (CALL_P (insn)) + break; + if (NOTE_P (insn) && NOTE_KIND (insn) == NOTE_INSN_EPILOGUE_BEG) + break; + if (NONDEBUG_INSN_P (insn)) + { + if (may_trap_or_fault_p (PATTERN (insn)) + && (trapping_insns_in_across || other_branch_live != NULL)) + break; -static void -df_chain_create_bb_process_use (struct dataflow *dflow, - struct df_chain_problem_data *problem_data, - bitmap local_rd, - struct df_ref *use, - enum df_ref_flags top_flag) -{ - struct df *df = dflow->df; - bitmap_iterator bi; - unsigned int def_index; - - while (use) + /* We cannot move memory stores past each other, or move memory + reads past stores, at least not without tracking them and + calling true_dependence on every pair. + + If there is no other branch and no memory references or + sets in the ACROSS range, we can move memory references + freely, even volatile ones. + + Otherwise, the rules are as follows: volatile memory + references and stores can't be moved at all, and any type + of memory reference can't be moved if there are volatile + accesses or stores in the ACROSS range. That leaves + normal reads, which can be moved, as the trapping case is + dealt with elsewhere. */ + if (other_branch_live != NULL || memrefs_in_across != 0) + { + int mem_ref_flags = 0; + int mem_set_flags = 0; + note_stores (PATTERN (insn), find_memory_stores, &mem_set_flags); + mem_ref_flags = for_each_rtx (&PATTERN (insn), find_memory, + NULL); + /* Catch sets of the stack pointer. */ + mem_ref_flags |= mem_set_flags; + + if ((mem_ref_flags | mem_set_flags) & MEMREF_VOLATILE) + break; + if ((memrefs_in_across & MEMREF_VOLATILE) && mem_ref_flags != 0) + break; + if (mem_set_flags != 0 + || (mem_sets_in_across != 0 && mem_ref_flags != 0)) + break; + } + df_simulate_find_uses (insn, merge_use); + /* We're only interested in uses which use a value live at + the top, not one previously set in this block. */ + bitmap_and_compl_into (merge_use, merge_set); + df_simulate_find_defs (insn, merge_set); + if (bitmap_intersect_p (merge_set, test_use) + || bitmap_intersect_p (merge_use, test_set)) + break; +#ifdef HAVE_cc0 + if (!sets_cc0_p (insn)) +#endif + max_to = insn; + } + next = NEXT_INSN (insn); + if (insn == to) + break; + } + if (max_to != to) + fail = 1; + + if (max_to == NULL_RTX || (fail && pmove_upto == NULL)) + goto out; + + /* Now, lower this upper bound by also taking into account that + a range of insns moved across ACROSS must not leave a register + live at the end that will be clobbered in ACROSS. We need to + find a point where TEST_SET & LIVE == 0. + + Insns in the MERGE range that set registers which are also set + in the ACROSS range may still be moved as long as we also move + later insns which use the results of the set, and make the + register dead again. This is verified by the condition stated + above. We only need to test it for registers that are set in + the moved region. + + MERGE_LIVE is provided by the caller and holds live registers after + TO. */ + bitmap_copy (local_merge_live, merge_live); + for (insn = to; insn != max_to; insn = PREV_INSN (insn)) + df_simulate_one_insn_backwards (merge_bb, insn, local_merge_live); + + /* We're not interested in registers that aren't set in the moved + region at all. */ + bitmap_and_into (local_merge_live, merge_set); + for (;;) { - /* Do not want to go thur this for an uninitialized var. */ - unsigned int uregno = DF_REF_REGNO (use); - int count = DF_REG_DEF_GET (df, uregno)->n_refs; - if (count) + if (NONDEBUG_INSN_P (insn)) { - if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP)) + if (!bitmap_intersect_p (test_set, local_merge_live) +#ifdef HAVE_cc0 + && !sets_cc0_p (insn) +#endif + ) { - unsigned int first_index = DF_REG_DEF_GET (df, uregno)->begin; - unsigned int last_index = first_index + count - 1; - - EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi) - { - struct df_ref *def; - if (def_index > last_index) - break; - - def = DF_DEFS_GET (df, def_index); - if (problem_data->flags & DF_DU_CHAIN) - df_chain_create (dflow, def, use); - if (problem_data->flags & DF_UD_CHAIN) - df_chain_create (dflow, use, def); - } + max_to = insn; + break; } + + df_simulate_one_insn_backwards (merge_bb, insn, + local_merge_live); + } + if (insn == from) + { + fail = 1; + goto out; } - use = use->next_ref; + insn = PREV_INSN (insn); } -} -/* Reset the storage pool that the def-use or use-def chains have been - allocated in. We do not need to re adjust the pointers in the refs, - these have already been clean out.*/ + if (max_to != to) + fail = 1; -/* Create chains from reaching defs bitmaps for basic block BB. */ -static void -df_chain_create_bb (struct dataflow *dflow, - struct dataflow *rd_dflow, - unsigned int bb_index) -{ - basic_block bb = BASIC_BLOCK (bb_index); - struct df_rd_bb_info *bb_info = df_rd_get_bb_info (rd_dflow, bb_index); - rtx insn; - bitmap cpy = BITMAP_ALLOC (NULL); - struct df *df = dflow->df; - struct df_chain_problem_data *problem_data = - (struct df_chain_problem_data *) dflow->problem_data; - struct df_ref *def; + if (pmove_upto) + *pmove_upto = max_to; - bitmap_copy (cpy, bb_info->in); + /* For small register class machines, don't lengthen lifetimes of + hard registers before reload. */ + if (! reload_completed + && targetm.small_register_classes_for_mode_p (VOIDmode)) + { + EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi) + { + if (i < FIRST_PSEUDO_REGISTER + && ! fixed_regs[i] + && ! global_regs[i]) + fail = 1; + } + } - /* Since we are going forwards, process the artificial uses first - then the artificial defs second. */ + out: + BITMAP_FREE (merge_set); + BITMAP_FREE (merge_use); + BITMAP_FREE (local_merge_live); + BITMAP_FREE (test_set); + BITMAP_FREE (test_use); -#ifdef EH_USES - /* Create the chains for the artificial uses from the EH_USES at the - beginning of the block. */ - df_chain_create_bb_process_use (dflow, problem_data, cpy, - df_get_artificial_uses (df, bb->index), - DF_REF_AT_TOP); -#endif + return !fail; +} - for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref) - { - unsigned int dregno = DF_REF_REGNO (def); - bitmap_clear_range (cpy, - DF_REG_DEF_GET (df, dregno)->begin, - DF_REG_DEF_GET (df, dregno)->n_refs); - if (! (DF_REF_FLAGS (def) & DF_REF_CLOBBER)) - bitmap_set_bit (cpy, DF_REF_ID (def)); - } - - /* Process the regular instructions next. */ - FOR_BB_INSNS (bb, insn) - { - struct df_ref *def; - unsigned int uid = INSN_UID (insn); + +/*---------------------------------------------------------------------------- + MULTIPLE DEFINITIONS + + Find the locations in the function reached by multiple definition sites + for a live pseudo. In and out bitvectors are built for each basic + block. They are restricted for efficiency to live registers. + + The gen and kill sets for the problem are obvious. Together they + include all defined registers in a basic block; the gen set includes + registers where a partial or conditional or may-clobber definition is + last in the BB, while the kill set includes registers with a complete + definition coming last. However, the computation of the dataflow + itself is interesting. + + The idea behind it comes from SSA form's iterated dominance frontier + criterion for inserting PHI functions. Just like in that case, we can use + the dominance frontier to find places where multiple definitions meet; + a register X defined in a basic block BB1 has multiple definitions in + basic blocks in BB1's dominance frontier. + + So, the in-set of a basic block BB2 is not just the union of the + out-sets of BB2's predecessors, but includes some more bits that come + from the basic blocks of whose dominance frontier BB2 is part (BB1 in + the previous paragraph). I called this set the init-set of BB2. + + (Note: I actually use the kill-set only to build the init-set. + gen bits are anyway propagated from BB1 to BB2 by dataflow). + + For example, if you have + + BB1 : r10 = 0 + r11 = 0 + if <...> goto BB2 else goto BB3; + + BB2 : r10 = 1 + r12 = 1 + goto BB3; + + BB3 : + + you have BB3 in BB2's dominance frontier but not in BB1's, so that the + init-set of BB3 includes r10 and r12, but not r11. Note that we do + not need to iterate the dominance frontier, because we do not insert + anything like PHI functions there! Instead, dataflow will take care of + propagating the information to BB3's successors. + ---------------------------------------------------------------------------*/ + +/* Private data used to verify the solution for this problem. */ +struct df_md_problem_data +{ + /* An obstack for the bitmaps we need for this problem. */ + bitmap_obstack md_bitmaps; +}; - if (! INSN_P (insn)) - continue; +/* Scratch var used by transfer functions. This is used to do md analysis + only for live registers. */ +static bitmap_head df_md_scratch; - /* Now scan the uses and link them up with the defs that remain - in the cpy vector. */ - - df_chain_create_bb_process_use (dflow, problem_data, cpy, - DF_INSN_UID_GET (df, uid)->uses, 0); - /* Since we are going forwards, process the defs second. This - pass only changes the bits in cpy. */ - for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref) - { - unsigned int dregno = DF_REF_REGNO (def); - bitmap_clear_range (cpy, - DF_REG_DEF_GET (df, dregno)->begin, - DF_REG_DEF_GET (df, dregno)->n_refs); - if (! (DF_REF_FLAGS (def) & DF_REF_CLOBBER)) - bitmap_set_bit (cpy, DF_REF_ID (def)); - } +static void +df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, + void *vbb_info) +{ + struct df_md_bb_info *bb_info = (struct df_md_bb_info *) vbb_info; + if (bb_info) + { + bitmap_clear (&bb_info->kill); + bitmap_clear (&bb_info->gen); + bitmap_clear (&bb_info->init); + bitmap_clear (&bb_info->in); + bitmap_clear (&bb_info->out); } - - /* Create the chains for the artificial uses of the hard registers - at the end of the block. */ - df_chain_create_bb_process_use (dflow, problem_data, cpy, - df_get_artificial_uses (df, bb->index), 0); } -/* Create def-use chains from reaching use bitmaps for basic blocks - in BLOCKS. */ + +/* Allocate or reset bitmaps for DF_MD. The solution bits are + not touched unless the block is new. */ static void -df_chain_finalize (struct dataflow *dflow, bitmap all_blocks) +df_md_alloc (bitmap all_blocks) { unsigned int bb_index; bitmap_iterator bi; - struct df *df = dflow->df; - struct dataflow *rd_dflow = df->problems_by_index [DF_RD]; - + struct df_md_problem_data *problem_data; + + df_grow_bb_info (df_md); + if (df_md->problem_data) + problem_data = (struct df_md_problem_data *) df_md->problem_data; + else + { + problem_data = XNEW (struct df_md_problem_data); + df_md->problem_data = problem_data; + bitmap_obstack_initialize (&problem_data->md_bitmaps); + } + bitmap_initialize (&df_md_scratch, &problem_data->md_bitmaps); + EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) { - df_chain_create_bb (dflow, rd_dflow, bb_index); + struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index); + /* When bitmaps are already initialized, just clear them. */ + if (bb_info->init.obstack) + { + bitmap_clear (&bb_info->init); + bitmap_clear (&bb_info->gen); + bitmap_clear (&bb_info->kill); + bitmap_clear (&bb_info->in); + bitmap_clear (&bb_info->out); + } + else + { + bitmap_initialize (&bb_info->init, &problem_data->md_bitmaps); + bitmap_initialize (&bb_info->gen, &problem_data->md_bitmaps); + bitmap_initialize (&bb_info->kill, &problem_data->md_bitmaps); + bitmap_initialize (&bb_info->in, &problem_data->md_bitmaps); + bitmap_initialize (&bb_info->out, &problem_data->md_bitmaps); + } } -} + df_md->optional_p = true; +} -/* Free all storage associated with the problem. */ +/* Add the effect of the top artificial defs of BB to the multiple definitions + bitmap LOCAL_MD. */ -static void -df_chain_free (struct dataflow *dflow) +void +df_md_simulate_artificial_defs_at_top (basic_block bb, bitmap local_md) { - free_alloc_pool (dflow->block_pool); - free (dflow->problem_data); - free (dflow); + 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 | DF_REF_MAY_CLOBBER)) + bitmap_set_bit (local_md, dregno); + else + bitmap_clear_bit (local_md, dregno); + } + } } -/* Debugging info. */ +/* Add the effect of the defs of INSN to the reaching definitions bitmap + LOCAL_MD. */ -static void -df_chains_dump (struct dataflow *dflow, FILE *file) +void +df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx insn, + bitmap local_md) { - struct df *df = dflow->df; - unsigned int j; - struct df_chain_problem_data *problem_data = - (struct df_chain_problem_data *) dflow->problem_data; + unsigned uid = INSN_UID (insn); + df_ref *def_rec; - if (problem_data->flags & DF_DU_CHAIN) + for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) { - fprintf (file, "Def-use chains:\n"); - for (j = 0; j < df->def_info.bitmap_size; j++) - { - struct df_ref *def = DF_DEFS_GET (df, j); - if (def) - { - fprintf (file, "d%d bb %d luid %d insn %d reg %d ", - j, DF_REF_BBNO (def), - DF_INSN_LUID (df, DF_REF_INSN (def)), - DF_REF_INSN (def) ? DF_REF_INSN_UID (def) : -1, - DF_REF_REGNO (def)); - if (def->flags & DF_REF_READ_WRITE) - fprintf (file, "read/write "); - df_chain_dump (df, DF_REF_CHAIN (def), file); - fprintf (file, "\n"); - } - } + 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 | DF_REF_MAY_CLOBBER)) + bitmap_set_bit (local_md, DF_REF_ID (def)); + else + bitmap_clear_bit (local_md, DF_REF_ID (def)); + } } +} + +static void +df_md_bb_local_compute_process_def (struct df_md_bb_info *bb_info, + df_ref *def_rec, + int top_flag) +{ + df_ref def; + bitmap_clear (&seen_in_insn); - if (problem_data->flags & DF_UD_CHAIN) + while ((def = *def_rec++) != NULL) { - fprintf (file, "Use-def chains:\n"); - for (j = 0; j < df->use_info.bitmap_size; j++) + unsigned int dregno = DF_REF_REGNO (def); + if (((!(df->changeable_flags & DF_NO_HARD_REGS)) + || (dregno >= FIRST_PSEUDO_REGISTER)) + && top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP)) { - struct df_ref *use = DF_USES_GET (df, j); - if (use) + if (!bitmap_bit_p (&seen_in_insn, dregno)) { - fprintf (file, "u%d bb %d luid %d insn %d reg %d ", - j, DF_REF_BBNO (use), - DF_REF_INSN (use) ? - DF_INSN_LUID (df, DF_REF_INSN (use)) - : -1, - DF_REF_INSN (DF_USES_GET (df, j)) ? - DF_REF_INSN_UID (DF_USES_GET (df,j)) - : -1, - DF_REF_REGNO (use)); - if (use->flags & DF_REF_READ_WRITE) - fprintf (file, "read/write "); - if (use->flags & DF_REF_STRIPPED) - fprintf (file, "stripped "); - if (use->flags & DF_REF_IN_NOTE) - fprintf (file, "note "); - df_chain_dump (df, DF_REF_CHAIN (use), file); - fprintf (file, "\n"); + if (DF_REF_FLAGS (def) + & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER)) + { + bitmap_set_bit (&bb_info->gen, dregno); + bitmap_clear_bit (&bb_info->kill, dregno); + } + else + { + /* When we find a clobber and a regular def, + make sure the regular def wins. */ + bitmap_set_bit (&seen_in_insn, dregno); + bitmap_set_bit (&bb_info->kill, dregno); + bitmap_clear_bit (&bb_info->gen, dregno); + } } } } } -static struct df_problem problem_CHAIN = +/* Compute local multiple def info for basic block BB. */ + +static void +df_md_bb_local_compute (unsigned int bb_index) { - DF_CHAIN, /* Problem id. */ - DF_NONE, /* Direction. */ - df_chain_alloc, /* Allocate the problem specific data. */ - NULL, /* Free basic block info. */ - NULL, /* Local compute function. */ - NULL, /* Init the solution specific data. */ - NULL, /* Iterative solver. */ - NULL, /* Confluence operator 0. */ - NULL, /* Confluence operator n. */ - NULL, /* Transfer function. */ - df_chain_finalize, /* Finalize function. */ - df_chain_free, /* Free all of the problem information. */ - df_chains_dump, /* Debugging. */ - &problem_RD /* Dependent problem. */ -}; + basic_block bb = BASIC_BLOCK (bb_index); + struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index); + rtx insn; + /* Artificials are only hard regs. */ + if (!(df->changeable_flags & DF_NO_HARD_REGS)) + df_md_bb_local_compute_process_def (bb_info, + df_get_artificial_defs (bb_index), + DF_REF_AT_TOP); -/* 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. */ + FOR_BB_INSNS (bb, insn) + { + unsigned int uid = INSN_UID (insn); + if (!INSN_P (insn)) + continue; -struct dataflow * -df_chain_add_problem (struct df *df, int flags) -{ - struct df_chain_problem_data *problem_data = - xmalloc (sizeof (struct df_chain_problem_data)); - struct dataflow *dflow = df_add_problem (df, &problem_CHAIN); + df_md_bb_local_compute_process_def (bb_info, DF_INSN_UID_DEFS (uid), 0); + } - dflow->problem_data = problem_data; - problem_data->flags = flags; - - return dflow; + if (!(df->changeable_flags & DF_NO_HARD_REGS)) + df_md_bb_local_compute_process_def (bb_info, + df_get_artificial_defs (bb_index), + 0); } +/* Compute local reaching def info for each basic block within BLOCKS. */ -/*---------------------------------------------------------------------------- - REGISTER INFORMATION - - Currently this consists of only lifetime information. But the plan is - to enhance it so that it produces all of the register information needed - by the register allocators. -----------------------------------------------------------------------------*/ +static void +df_md_local_compute (bitmap all_blocks) +{ + unsigned int bb_index, df_bb_index; + bitmap_iterator bi1, bi2; + basic_block bb; + bitmap_head *frontiers; + bitmap_initialize (&seen_in_insn, &bitmap_default_obstack); -struct df_ri_problem_data -{ - int *lifetime; -}; + EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1) + { + df_md_bb_local_compute (bb_index); + } + bitmap_clear (&seen_in_insn); -/* Allocate the lifetime information. */ + frontiers = XNEWVEC (bitmap_head, last_basic_block); + FOR_ALL_BB (bb) + bitmap_initialize (&frontiers[bb->index], &bitmap_default_obstack); -static void -df_ri_alloc (struct dataflow *dflow, bitmap blocks_to_rescan ATTRIBUTE_UNUSED) -{ - struct df_ri_problem_data *problem_data = - (struct df_ri_problem_data *) dflow->problem_data; + compute_dominance_frontiers (frontiers); - if (!dflow->problem_data) + /* Add each basic block's kills to the nodes in the frontier of the BB. */ + EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1) { - struct df_ri_problem_data *problem_data = - xmalloc (sizeof (struct df_ri_problem_data)); - dflow->problem_data = problem_data; + bitmap kill = &df_md_get_bb_info (bb_index)->kill; + EXECUTE_IF_SET_IN_BITMAP (&frontiers[bb_index], 0, df_bb_index, bi2) + { + basic_block bb = BASIC_BLOCK (df_bb_index); + if (bitmap_bit_p (all_blocks, df_bb_index)) + bitmap_ior_and_into (&df_md_get_bb_info (df_bb_index)->init, kill, + df_get_live_in (bb)); + } } - problem_data->lifetime = xrealloc (problem_data->lifetime, - max_reg_num () *sizeof (int)); - memset (problem_data->lifetime, 0, max_reg_num () *sizeof (int)); + FOR_ALL_BB (bb) + bitmap_clear (&frontiers[bb->index]); + free (frontiers); } -/* Compute register info: lifetime, bb, and number of defs and uses - for basic block BB. */ + +/* Reset the global solution for recalculation. */ static void -df_ri_bb_compute (struct dataflow *dflow, unsigned int bb_index, bitmap live) +df_md_reset (bitmap all_blocks) { - struct df *df = dflow->df; - struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index); - struct df_ri_problem_data *problem_data = - (struct df_ri_problem_data *) dflow->problem_data; - basic_block bb = BASIC_BLOCK (bb_index); - rtx insn; - - bitmap_copy (live, bb_info->out); + unsigned int bb_index; + bitmap_iterator bi; - FOR_BB_INSNS_REVERSE (bb, insn) + EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) { - unsigned int uid = INSN_UID (insn); - unsigned int regno; - bitmap_iterator bi; - struct df_ref *def; - struct df_ref *use; - - if (! INSN_P (insn)) - continue; + struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index); + gcc_assert (bb_info); + bitmap_clear (&bb_info->in); + bitmap_clear (&bb_info->out); + } +} - for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref) - { - unsigned int dregno = DF_REF_REGNO (def); +static bool +df_md_transfer_function (int bb_index) +{ + basic_block bb = BASIC_BLOCK (bb_index); + struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index); + bitmap in = &bb_info->in; + bitmap out = &bb_info->out; + bitmap gen = &bb_info->gen; + bitmap kill = &bb_info->kill; + + /* We need to use a scratch set here so that the value returned from this + function invocation properly reflects whether the sets changed in a + significant way; i.e. not just because the live set was anded in. */ + bitmap_and (&df_md_scratch, gen, df_get_live_out (bb)); + + /* Multiple definitions of a register are not relevant if it is not + live. Thus we trim the result to the places where it is live. */ + bitmap_and_into (in, df_get_live_in (bb)); + + return bitmap_ior_and_compl (out, &df_md_scratch, in, kill); +} - /* Kill this register. */ - bitmap_clear_bit (live, dregno); - } +/* Initialize the solution bit vectors for problem. */ - for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref) - { - unsigned int uregno = DF_REF_REGNO (use); +static void +df_md_init (bitmap all_blocks) +{ + unsigned int bb_index; + bitmap_iterator bi; - /* This register is now live. */ - bitmap_set_bit (live, uregno); - } + EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) + { + struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index); - /* Increment lifetimes of all live registers. */ - EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi) - { - problem_data->lifetime[regno]++; - } + bitmap_copy (&bb_info->in, &bb_info->init); + df_md_transfer_function (bb_index); } } - -/* Compute register info: lifetime, bb, and number of defs and uses. */ static void -df_ri_compute (struct dataflow *dflow, bitmap all_blocks ATTRIBUTE_UNUSED, - bitmap blocks_to_scan) +df_md_confluence_0 (basic_block bb) { - unsigned int bb_index; - bitmap_iterator bi; - bitmap live; + struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index); + bitmap_copy (&bb_info->in, &bb_info->init); +} - live = BITMAP_ALLOC (NULL); +/* In of target gets or of out of source. */ - EXECUTE_IF_SET_IN_BITMAP (blocks_to_scan, 0, bb_index, bi) - { - df_ri_bb_compute (dflow, bb_index, live); - } +static bool +df_md_confluence_n (edge e) +{ + bitmap op1 = &df_md_get_bb_info (e->dest->index)->in; + bitmap op2 = &df_md_get_bb_info (e->src->index)->out; - BITMAP_FREE (live); -} + if (e->flags & EDGE_FAKE) + return false; + if (e->flags & EDGE_EH) + return bitmap_ior_and_compl_into (op1, op2, + regs_invalidated_by_call_regset); + else + return bitmap_ior_into (op1, op2); +} /* Free all storage associated with the problem. */ static void -df_ri_free (struct dataflow *dflow) +df_md_free (void) { - struct df_ri_problem_data *problem_data = - (struct df_ri_problem_data *) dflow->problem_data; + struct df_md_problem_data *problem_data + = (struct df_md_problem_data *) df_md->problem_data; - free (problem_data->lifetime); - free (dflow->problem_data); - free (dflow); + bitmap_obstack_release (&problem_data->md_bitmaps); + free (problem_data); + df_md->problem_data = NULL; + + df_md->block_info_size = 0; + free (df_md->block_info); + df_md->block_info = NULL; + free (df_md); } -/* Debugging info. */ +/* Debugging info at top of bb. */ static void -df_ri_dump (struct dataflow *dflow, FILE *file) +df_md_top_dump (basic_block bb, FILE *file) { - struct df_ri_problem_data *problem_data = - (struct df_ri_problem_data *) dflow->problem_data; - int j; + struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index); + if (!bb_info) + return; - fprintf (file, "Register info:\n"); - for (j = 0; j < max_reg_num (); j++) - { - fprintf (file, "reg %d life %d\n", j, problem_data->lifetime[j]); - } + fprintf (file, ";; md in \t"); + df_print_regset (file, &bb_info->in); + fprintf (file, ";; md init \t"); + df_print_regset (file, &bb_info->init); + fprintf (file, ";; md gen \t"); + df_print_regset (file, &bb_info->gen); + fprintf (file, ";; md kill \t"); + df_print_regset (file, &bb_info->kill); } -/* All of the information associated every instance of the problem. */ +/* Debugging info at bottom of bb. */ -static struct df_problem problem_RI = +static void +df_md_bottom_dump (basic_block bb, FILE *file) { - DF_RI, /* Problem id. */ - DF_NONE, /* Direction. */ - df_ri_alloc, /* Allocate the problem specific data. */ - NULL, /* Free basic block info. */ - df_ri_compute, /* Local compute function. */ - NULL, /* Init the solution specific data. */ - NULL, /* Iterative solver. */ - NULL, /* Confluence operator 0. */ - NULL, /* Confluence operator n. */ - NULL, /* Transfer function. */ - NULL, /* Finalize function. */ - df_ri_free, /* Free all of the problem information. */ - df_ri_dump, /* Debugging. */ - &problem_UR /* Dependent problem. */ -}; - + struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index); + if (!bb_info) + return; -/* 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. */ + fprintf (file, ";; md out \t"); + df_print_regset (file, &bb_info->out); +} -struct dataflow * -df_ri_add_problem (struct df *df) +static struct df_problem problem_MD = { - return df_add_problem (df, &problem_RI); -} + DF_MD, /* Problem id. */ + DF_FORWARD, /* Direction. */ + df_md_alloc, /* Allocate the problem specific data. */ + df_md_reset, /* Reset global information. */ + df_md_free_bb_info, /* Free basic block info. */ + df_md_local_compute, /* Local compute function. */ + df_md_init, /* Init the solution specific data. */ + df_worklist_dataflow, /* Worklist solver. */ + df_md_confluence_0, /* Confluence operator 0. */ + df_md_confluence_n, /* Confluence operator n. */ + df_md_transfer_function, /* Transfer function. */ + NULL, /* Finalize function. */ + df_md_free, /* Free all of the problem information. */ + df_md_free, /* Remove this problem from the stack of dataflow problems. */ + NULL, /* Debugging. */ + df_md_top_dump, /* Debugging start block. */ + df_md_bottom_dump, /* Debugging end block. */ + NULL, /* Incremental solution verify start. */ + NULL, /* Incremental solution verify end. */ + NULL, /* Dependent problem. */ + sizeof (struct df_md_bb_info),/* Size of entry of block_info array. */ + TV_DF_MD, /* Timing variable. */ + false /* Reset blocks on dropping out of blocks_to_analyze. */ +}; +/* Create a new MD instance and add it to the existing instance + of DF. */ -/* Return total lifetime (in insns) of REG. */ -int -df_reg_lifetime (struct df *df, rtx reg) +void +df_md_add_problem (void) { - struct dataflow *dflow = df->problems_by_index[DF_RI]; - struct df_ri_problem_data *problem_data = - (struct df_ri_problem_data *) dflow->problem_data; - return problem_data->lifetime[REGNO (reg)]; + df_add_problem (&problem_MD); } +