| /* 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 |
| (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com) |
| Major rewrite contributed by Danny Berlin (dberlin@dberlin.org) |
| and Kenneth Zadeck (zadeck@naturalbridge.com). |
| |
| 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 |
| version. |
| |
| GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
| WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| 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. */ |
| |
| #include "config.h" |
| #include "system.h" |
| #include "coretypes.h" |
| #include "tm.h" |
| #include "rtl.h" |
| #include "tm_p.h" |
| #include "insn-config.h" |
| #include "recog.h" |
| #include "function.h" |
| #include "regs.h" |
| #include "output.h" |
| #include "alloc-pool.h" |
| #include "flags.h" |
| #include "hard-reg-set.h" |
| #include "basic-block.h" |
| #include "sbitmap.h" |
| #include "bitmap.h" |
| #include "timevar.h" |
| #include "df.h" |
| #include "vecprim.h" |
| #include "except.h" |
| |
| #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 void df_ri_dump (struct dataflow *, FILE *); |
| |
| |
| /*---------------------------------------------------------------------------- |
| Public functions access functions for the dataflow problems. |
| ----------------------------------------------------------------------------*/ |
| |
| /* 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. */ |
| |
| bitmap |
| df_get_live_in (struct df *df, basic_block bb) |
| { |
| gcc_assert (df->problems_by_index[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); |
| } |
| |
| |
| /* Get the live out set for BB no matter what problem happens to be |
| defined. */ |
| |
| bitmap |
| df_get_live_out (struct df *df, basic_block bb) |
| { |
| gcc_assert (df->problems_by_index[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); |
| } |
| |
| |
| /*---------------------------------------------------------------------------- |
| Utility functions. |
| ----------------------------------------------------------------------------*/ |
| |
| /* Generic versions to get the void* version of the block info. Only |
| used inside the problem instance 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; |
| } |
| } |
| |
| /* Dump a def-use or use-def chain for REF to FILE. */ |
| |
| void |
| 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_ID (link->ref), |
| DF_REF_BBNO (link->ref), |
| DF_REF_INSN (link->ref) ? DF_REF_INSN_UID (link->ref) : -1); |
| } |
| fprintf (file, "}"); |
| } |
| |
| |
| /* Print some basic block info as part of df_dump. */ |
| |
| void |
| df_print_bb_index (basic_block bb, FILE *file) |
| { |
| edge e; |
| edge_iterator ei; |
| |
| fprintf (file, "( "); |
| FOR_EACH_EDGE (e, ei, bb->preds) |
| { |
| basic_block pred = e->src; |
| fprintf (file, "%d ", pred->index); |
| } |
| 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 a bitmap for REGNO from the cache MAPS. The bitmap is to |
| contain COUNT bits starting at START. These bitmaps are not to be |
| changed since there is a cache of them. */ |
| |
| 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); |
| } |
| 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); |
| } |
| |
| |
| |
| /*---------------------------------------------------------------------------- |
| REACHING USES |
| |
| Find the locations in the function where each use site for a pseudo |
| can reach backwards. 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. |
| |
| 1) The order of the bits in the bitvectors. After the scanning |
| phase, all of the uses are sorted. All of the uses for the reg 0 |
| are first, followed by all uses for reg 1 and so on. |
| |
| 2) There are two kill sets, one if the number of uses is less or |
| equal to DF_SPARSE_THRESHOLD and another if it is greater. |
| |
| <= : There is a bitmap for each register, uses_sites[N], that is |
| built on demand. This bitvector contains a 1 for each use or reg |
| N. |
| |
| > : 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. |
| |
| The kill and sparse_kill and the dense_invalidated_by_call and |
| sparse_invalidated_by call both play this game. */ |
| |
| /* Private data used to compute the solution for this problem. These |
| data structures are not accessible outside of this module. */ |
| 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 invalidated by call for ru. */ |
| bitmap dense_invalidated_by_call; |
| }; |
| |
| /* Get basic block info. */ |
| |
| 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]; |
| } |
| |
| |
| /* Set basic block info. */ |
| |
| static void |
| df_ru_set_bb_info (struct dataflow *dflow, unsigned int index, |
| struct df_ru_bb_info *bb_info) |
| { |
| dflow->block_info[index] = bb_info; |
| } |
| |
| |
| /* Free basic block info. */ |
| |
| static void |
| df_ru_free_bb_info (struct dataflow *dflow, |
| basic_block bb ATTRIBUTE_UNUSED, |
| void *vbb_info) |
| { |
| struct df_ru_bb_info *bb_info = (struct df_ru_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); |
| } |
| } |
| |
| |
| /* Allocate or reset bitmaps for DFLOW blocks. The solution bits are |
| not touched unless the block is new. */ |
| |
| static void |
| df_ru_alloc (struct dataflow *dflow, |
| bitmap blocks_to_rescan ATTRIBUTE_UNUSED, |
| 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); |
| |
| if (dflow->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); |
| } |
| else |
| { |
| struct df_ru_problem_data *problem_data = XNEW (struct df_ru_problem_data); |
| dflow->problem_data = problem_data; |
| |
| problem_data->use_sites = XCNEWVEC (bitmap, reg_size); |
| 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); |
| } |
| |
| 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 (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); |
| } |
| 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); |
| } |
| } |
| } |
| |
| |
| /* Process a list of DEFs for df_ru_bb_local_compute. */ |
| |
| static void |
| df_ru_bb_local_compute_process_def (struct dataflow *dflow, |
| struct df_ru_bb_info *bb_info, |
| struct df_ref *def, |
| enum df_ref_flags top_flag) |
| { |
| struct df *df = dflow->df; |
| while (def) |
| { |
| if ((top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP)) |
| /* If the def is to only part of the reg, it is as if it did |
| not happen, since some of the bits may get thru. */ |
| && (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL))) |
| { |
| 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)) |
| { |
| /* The first def for regno in the insn, causes the kill |
| info to be generated. Do not modify the gen set |
| because the only values in it are the uses from here |
| to the top of the block and this def does not effect |
| them. */ |
| if (!bitmap_bit_p (seen_in_insn, regno)) |
| { |
| if (n_uses > DF_SPARSE_THRESHOLD) |
| bitmap_set_bit (bb_info->sparse_kill, regno); |
| 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_set_bit (seen_in_insn, regno); |
| } |
| } |
| def = def->next_ref; |
| } |
| } |
| |
| |
| /* Process a list of USEs for df_ru_bb_local_compute. */ |
| |
| 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) |
| { |
| while (use) |
| { |
| if (top_flag == (DF_REF_FLAGS (use) & 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)); |
| } |
| use = use->next_ref; |
| } |
| } |
| |
| /* Compute local reaching use (upward exposed use) info for basic |
| block BB. USE_INFO->REGS[R] caches the set of uses for register R. */ |
| static void |
| df_ru_bb_local_compute (struct dataflow *dflow, 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); |
| 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 |
| df_ru_bb_local_compute_process_def (dflow, bb_info, |
| df_get_artificial_defs (df, bb_index), |
| DF_REF_AT_TOP); |
| |
| FOR_BB_INSNS (bb, insn) |
| { |
| unsigned int uid = INSN_UID (insn); |
| if (!INSN_P (insn)) |
| continue; |
| |
| df_ru_bb_local_compute_process_use (bb_info, |
| DF_INSN_UID_USES (df, uid), 0); |
| |
| df_ru_bb_local_compute_process_def (dflow, bb_info, |
| DF_INSN_UID_DEFS (df, uid), 0); |
| |
| 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); |
| |
| df_ru_bb_local_compute_process_def (dflow, bb_info, |
| df_get_artificial_defs (df, bb_index), 0); |
| } |
| |
| |
| /* Compute local reaching use (upward exposed use) info for each basic |
| block within BLOCKS. */ |
| static void |
| df_ru_local_compute (struct dataflow *dflow, |
| bitmap all_blocks, |
| bitmap rescan_blocks ATTRIBUTE_UNUSED) |
| { |
| 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; |
| |
| df_set_seen (); |
| |
| if (!df->use_info.refs_organized) |
| df_reorganize_refs (&df->use_info); |
| |
| EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) |
| { |
| df_ru_bb_local_compute (dflow, 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) |
| { |
| struct df_reg_info *reg_info = DF_REG_USE_GET (df, regno); |
| if (reg_info->n_refs > 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); |
| } |
| } |
| |
| df_unset_seen (); |
| } |
| |
| |
| /* Initialize the solution bit vectors for problem. */ |
| |
| static void |
| df_ru_init_solution (struct dataflow *dflow, 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); |
| } |
| } |
| |
| |
| /* Out of target gets or of in of source. */ |
| |
| static void |
| df_ru_confluence_n (struct dataflow *dflow, 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; |
| |
| 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; |
| bitmap_iterator bi; |
| unsigned int regno; |
| bitmap tmp = BITMAP_ALLOC (NULL); |
| |
| 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_ior_into (op1, tmp); |
| BITMAP_FREE (tmp); |
| } |
| else |
| bitmap_ior_into (op1, op2); |
| } |
| |
| |
| /* Transfer function. */ |
| |
| static bool |
| df_ru_transfer_function (struct dataflow *dflow, int bb_index) |
| { |
| struct df_ru_bb_info *bb_info = df_ru_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; |
| |
| if (bitmap_empty_p (sparse_kill)) |
| return bitmap_ior_and_compl (in, gen, out, kill); |
| else |
| { |
| struct df *df = dflow->df; |
| bool changed = false; |
| bitmap tmp = BITMAP_ALLOC (NULL); |
| bitmap_copy (tmp, out); |
| 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_and_compl_into (tmp, kill); |
| bitmap_ior_into (tmp, gen); |
| changed = !bitmap_equal_p (tmp, in); |
| if (changed) |
| { |
| BITMAP_FREE (in); |
| bb_info->in = tmp; |
| } |
| else |
| BITMAP_FREE (tmp); |
| return changed; |
| } |
| } |
| |
| |
| /* Free all storage associated with the problem. */ |
| |
| static void |
| df_ru_free (struct dataflow *dflow) |
| { |
| unsigned int i; |
| struct df_ru_problem_data *problem_data |
| = (struct df_ru_problem_data *) dflow->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); |
| } |
| free (dflow); |
| } |
| |
| |
| /* Debugging info. */ |
| |
| static void |
| df_ru_dump (struct dataflow *dflow, 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 (); |
| unsigned int regno; |
| |
| if (!dflow->block_info) |
| return; |
| |
| fprintf (file, "Reaching uses:\n"); |
| |
| 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); |
| |
| 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); |
| 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(%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); |
| } |
| } |
| |
| /* All of the information associated with every instance of the problem. */ |
| |
| static struct df_problem problem_RU = |
| { |
| DF_RU, /* Problem id. */ |
| DF_BACKWARD, /* Direction. */ |
| df_ru_alloc, /* Allocate the problem specific data. */ |
| NULL, /* Reset global information. */ |
| 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. */ |
| 0 /* Changeable flags. */ |
| }; |
| |
| |
| |
| /* 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_ru_add_problem (struct df *df, int flags) |
| { |
| return df_add_problem (df, &problem_RU, flags); |
| } |
| |
| |
| /*---------------------------------------------------------------------------- |
| REACHING DEFINITIONS |
| |
| 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. |
| ----------------------------------------------------------------------------*/ |
| |
| /* See the comment at the top of the Reaching Uses problem for how the |
| uses are represented in the kill sets. The same games are played |
| here for the defs. */ |
| |
| /* 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 |
| { |
| /* If the number of defs for regnum N is less than |
| DF_SPARSE_THRESHOLD, uses_sites[N] contains a mask of the all of |
| the defs of reg N indexed by the id in the ref structure. If |
| there are more than DF_SPARSE_THRESHOLD defs for regnum N a |
| different mechanism is used to mask the def. */ |
| 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 rd. */ |
| bitmap dense_invalidated_by_call; |
| }; |
| |
| /* Get basic block info. */ |
| |
| struct df_rd_bb_info * |
| df_rd_get_bb_info (struct dataflow *dflow, unsigned int index) |
| { |
| return (struct df_rd_bb_info *) dflow->block_info[index]; |
| } |
| |
| |
| /* Set basic block info. */ |
| |
| 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; |
| } |
| |
| |
| /* Free basic block info. */ |
| |
| static void |
| df_rd_free_bb_info (struct dataflow *dflow, |
| basic_block bb ATTRIBUTE_UNUSED, |
| void *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); |
| } |
| } |
| |
| |
| /* Allocate or reset bitmaps for DFLOW blocks. The solution bits are |
| not touched unless the block is new. */ |
| |
| static void |
| df_rd_alloc (struct dataflow *dflow, |
| bitmap blocks_to_rescan ATTRIBUTE_UNUSED, |
| 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_rd_block pool", |
| sizeof (struct df_rd_bb_info), 50); |
| |
| if (dflow->problem_data) |
| { |
| unsigned int i; |
| struct df_rd_problem_data *problem_data |
| = (struct df_rd_problem_data *) dflow->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 = XNEW (struct df_rd_problem_data); |
| dflow->problem_data = problem_data; |
| |
| problem_data->def_sites = XCNEWVEC (bitmap, reg_size); |
| 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); |
| } |
| |
| df_grow_bb_info (dflow); |
| |
| /* 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 (all_blocks, 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); |
| } |
| 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); |
| } |
| } |
| } |
| |
| |
| /* Process a list of DEFs for df_rd_bb_local_compute. */ |
| |
| static void |
| df_rd_bb_local_compute_process_def (struct dataflow *dflow, |
| struct df_rd_bb_info *bb_info, |
| struct df_ref *def, |
| enum df_ref_flags top_flag) |
| { |
| struct df *df = dflow->df; |
| while (def) |
| { |
| if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP)) |
| { |
| 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 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_FLAGS (def) & 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 |
| { |
| 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_MUST_CLOBBER | DF_REF_MAY_CLOBBER))) |
| bitmap_set_bit (bb_info->gen, DF_REF_ID (def)); |
| } |
| } |
| def = def->next_ref; |
| } |
| } |
| |
| /* Compute local reaching def info for basic block BB. */ |
| |
| static void |
| df_rd_bb_local_compute (struct dataflow *dflow, 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); |
| rtx insn; |
| |
| bitmap_clear (seen_in_block); |
| bitmap_clear (seen_in_insn); |
| |
| df_rd_bb_local_compute_process_def (dflow, bb_info, |
| df_get_artificial_defs (df, bb_index), 0); |
| |
| FOR_BB_INSNS_REVERSE (bb, insn) |
| { |
| unsigned int uid = INSN_UID (insn); |
| |
| if (!INSN_P (insn)) |
| continue; |
| |
| df_rd_bb_local_compute_process_def (dflow, bb_info, |
| DF_INSN_UID_DEFS (df, uid), 0); |
| |
| /* 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 artificial defs at the top of the block last since we |
| are going backwards through 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), |
| DF_REF_AT_TOP); |
| } |
| |
| |
| /* Compute local reaching def info for each basic block within BLOCKS. */ |
| |
| static void |
| df_rd_local_compute (struct dataflow *dflow, |
| bitmap all_blocks, |
| bitmap rescan_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 (); |
| |
| if (!df->def_info.refs_organized) |
| df_reorganize_refs (&df->def_info); |
| |
| EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) |
| { |
| df_rd_bb_local_compute (dflow, 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) |
| { |
| struct df_reg_info *reg_info = DF_REG_DEF_GET (df, regno); |
| if (reg_info->n_refs > DF_SPARSE_THRESHOLD) |
| { |
| bitmap_set_bit (sparse_invalidated, regno); |
| } |
| 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_unset_seen (); |
| } |
| |
| |
| /* Initialize the solution bit vectors for problem. */ |
| |
| static void |
| df_rd_init_solution (struct dataflow *dflow, 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); |
| } |
| } |
| |
| /* In of target gets or of out of source. */ |
| |
| static void |
| df_rd_confluence_n (struct dataflow *dflow, edge e) |
| { |
| bitmap op1 = df_rd_get_bb_info (dflow, e->dest->index)->in; |
| bitmap op2 = df_rd_get_bb_info (dflow, e->src->index)->out; |
| |
| 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); |
| |
| 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); |
| } |
| else |
| bitmap_ior_into (op1, op2); |
| } |
| |
| |
| /* Transfer function. */ |
| |
| static bool |
| df_rd_transfer_function (struct dataflow *dflow, 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; |
| |
| if (bitmap_empty_p (sparse_kill)) |
| return bitmap_ior_and_compl (out, gen, in, kill); |
| else |
| { |
| 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) |
| { |
| bitmap_clear_range (tmp, |
| DF_REG_DEF_GET (df, regno)->begin, |
| DF_REG_DEF_GET (df, regno)->n_refs); |
| } |
| 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; |
| } |
| } |
| |
| |
| /* Free all storage associated with the problem. */ |
| |
| static void |
| df_rd_free (struct dataflow *dflow) |
| { |
| unsigned int i; |
| struct df_rd_problem_data *problem_data |
| = (struct df_rd_problem_data *) dflow->problem_data; |
| |
| if (problem_data) |
| { |
| for (i = 0; i < dflow->block_info_size; i++) |
| { |
| 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); |
| } |
| } |
| |
| free_alloc_pool (dflow->block_pool); |
| |
| for (i = 0; i < problem_data->def_sites_size; i++) |
| { |
| bitmap bm = problem_data->def_sites[i]; |
| if (bm) |
| BITMAP_FREE (bm); |
| } |
| |
| 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. */ |
| |
| static void |
| df_rd_dump (struct dataflow *dflow, FILE *file) |
| { |
| 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; |
| |
| if (!dflow->block_info) |
| return; |
| |
| fprintf (file, "Reaching defs:\n\n"); |
| |
| 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); |
| |
| 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"); |
| |
| 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); |
| } |
| } |
| |
| /* All of the information associated with every instance of the problem. */ |
| |
| static struct df_problem problem_RD = |
| { |
| 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_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. */ |
| 0 /* Changeable flags. */ |
| }; |
| |
| |
| |
| /* 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, int flags) |
| { |
| return df_add_problem (df, &problem_RD, flags); |
| } |
| |
| |
| |
| /*---------------------------------------------------------------------------- |
| LIVE REGISTERS |
| |
| Find the locations in the function where any use of a pseudo can |
| reach in the backwards direction. In and out bitvectors are built |
| for each basic block. The regnum is used to index into these sets. |
| See df.h for details. |
| ----------------------------------------------------------------------------*/ |
| |
| /* Get basic block info. */ |
| |
| 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]; |
| } |
| |
| |
| /* Set basic block info. */ |
| |
| static void |
| df_lr_set_bb_info (struct dataflow *dflow, unsigned int index, |
| struct df_lr_bb_info *bb_info) |
| { |
| dflow->block_info[index] = bb_info; |
| } |
| |
| |
| /* Free basic block info. */ |
| |
| static void |
| df_lr_free_bb_info (struct dataflow *dflow, |
| basic_block bb ATTRIBUTE_UNUSED, |
| void *vbb_info) |
| { |
| struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info; |
| if (bb_info) |
| { |
| BITMAP_FREE (bb_info->use); |
| BITMAP_FREE (bb_info->def); |
| BITMAP_FREE (bb_info->in); |
| BITMAP_FREE (bb_info->out); |
| pool_free (dflow->block_pool, bb_info); |
| } |
| } |
| |
| |
| /* Allocate or reset bitmaps for DFLOW blocks. The solution bits are |
| not touched unless the block is new. */ |
| |
| static void |
| df_lr_alloc (struct dataflow *dflow, bitmap blocks_to_rescan, |
| bitmap all_blocks ATTRIBUTE_UNUSED) |
| { |
| unsigned int bb_index; |
| bitmap_iterator bi; |
| |
| if (!dflow->block_pool) |
| dflow->block_pool = create_alloc_pool ("df_lr_block pool", |
| sizeof (struct df_lr_bb_info), 50); |
| |
| df_grow_bb_info (dflow); |
| |
| EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 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); |
| } |
| 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); |
| } |
| } |
| } |
| |
| |
| /* Compute local live register info for basic block BB. */ |
| |
| static void |
| df_lr_bb_local_compute (struct dataflow *dflow, |
| struct df *df, 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); |
| rtx insn; |
| struct df_ref *def; |
| struct df_ref *use; |
| |
| /* Process the registers set in an exception handler. */ |
| for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref) |
| if (((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0) |
| && (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL))) |
| { |
| unsigned int dregno = DF_REF_REGNO (def); |
| bitmap_set_bit (bb_info->def, dregno); |
| bitmap_clear_bit (bb_info->use, dregno); |
| } |
| |
| /* 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)); |
| |
| FOR_BB_INSNS_REVERSE (bb, insn) |
| { |
| unsigned int uid = INSN_UID (insn); |
| |
| if (!INSN_P (insn)) |
| continue; |
| |
| if (CALL_P (insn)) |
| { |
| for (def = DF_INSN_UID_DEFS (df, uid); 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))) |
| { |
| /* 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)) |
| { |
| bitmap_set_bit (bb_info->def, dregno); |
| bitmap_clear_bit (bb_info->use, dregno); |
| } |
| } |
| } |
| } |
| else |
| { |
| for (def = DF_INSN_UID_DEFS (df, uid); 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; |
| } |
| /* 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)) |
| { |
| bitmap_set_bit (bb_info->def, dregno); |
| bitmap_clear_bit (bb_info->use, dregno); |
| } |
| } |
| } |
| |
| for (use = DF_INSN_UID_USES (df, uid); use; use = use->next_ref) |
| /* Add use to set of uses in this BB. */ |
| bitmap_set_bit (bb_info->use, DF_REF_REGNO (use)); |
| } |
| |
| /* Process the registers set in an exception handler. */ |
| for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref) |
| if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) |
| && (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL))) |
| { |
| 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 = 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. */ |
| |
| static void |
| df_lr_local_compute (struct dataflow *dflow, |
| bitmap all_blocks, |
| bitmap rescan_blocks) |
| { |
| 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) |
| { |
| if (bb_index == EXIT_BLOCK) |
| continue; |
| df_lr_bb_local_compute (dflow, df, bb_index); |
| } |
| } |
| |
| |
| /* Initialize the solution vectors. */ |
| |
| static void |
| df_lr_init (struct dataflow *dflow, 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); |
| } |
| } |
| |
| |
| /* 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) |
| { |
| 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); |
| } |
| |
| |
| /* 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); |
| |
| bitmap_ior_into (op1, dflow->df->hardware_regs_used); |
| } |
| |
| |
| /* Transfer function. */ |
| |
| static bool |
| df_lr_transfer_function (struct dataflow *dflow, 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); |
| } |
| |
| |
| /* Free all storage associated with the problem. */ |
| |
| static void |
| df_lr_free (struct dataflow *dflow) |
| { |
| if (dflow->block_info) |
| { |
| unsigned int i; |
| for (i = 0; i < dflow->block_info_size; i++) |
| { |
| 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); |
| } |
| } |
| free_alloc_pool (dflow->block_pool); |
| |
| dflow->block_info_size = 0; |
| free (dflow->block_info); |
| } |
| |
| free (dflow->problem_data); |
| free (dflow); |
| } |
| |
| |
| /* Debugging info. */ |
| |
| static void |
| df_lr_dump (struct dataflow *dflow, FILE *file) |
| { |
| basic_block bb; |
| |
| if (!dflow->block_info) |
| return; |
| |
| fprintf (file, "Live Registers:\n"); |
| FOR_ALL_BB (bb) |
| { |
| 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); |
| } |
| } |
| |
| /* 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. */ |
| NULL, /* 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_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. */ |
| 0 |
| }; |
| |
| |
| /* 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_lr_add_problem (struct df *df, int flags) |
| { |
| return df_add_problem (df, &problem_LR, flags); |
| } |
| |
| |
| |
| /*---------------------------------------------------------------------------- |
| UNINITIALIZED REGISTERS |
| |
| Find the set of uses for registers that are reachable from the entry |
| block without passing thru a definition. In and out bitvectors are built |
| for each basic block. The regnum is used to index into these sets. |
| See df.h for details. |
| ----------------------------------------------------------------------------*/ |
| |
| /* Get basic block info. */ |
| |
| 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]; |
| } |
| |
| |
| /* Set basic block info. */ |
| |
| static void |
| df_ur_set_bb_info (struct dataflow *dflow, unsigned int index, |
| struct df_ur_bb_info *bb_info) |
| { |
| dflow->block_info[index] = bb_info; |
| } |
| |
| |
| /* Free basic block info. */ |
| |
| 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) |
| { |
| 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); |
| } |
| } |
| |
| |
| /* Allocate or reset bitmaps for DFLOW blocks. The solution bits are |
| not touched unless the block is new. */ |
| |
| static void |
| df_ur_alloc (struct dataflow *dflow, bitmap blocks_to_rescan, |
| bitmap all_blocks ATTRIBUTE_UNUSED) |
| { |
| 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); |
| |
| df_grow_bb_info (dflow); |
| |
| EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi) |
| { |
| 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); |
| } |
| } |
| } |
| |
| |
| /* Compute local uninitialized register info for basic block BB. */ |
| |
| static void |
| df_ur_bb_local_compute (struct dataflow *dflow, unsigned int bb_index) |
| { |
| 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 (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref) |
| if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0) |
| { |
| unsigned int regno = DF_REF_REGNO (def); |
| if (!bitmap_bit_p (seen_in_block, regno)) |
| { |
| bitmap_set_bit (seen_in_block, regno); |
| bitmap_set_bit (bb_info->gen, regno); |
| } |
| } |
| |
| FOR_BB_INSNS_REVERSE (bb, insn) |
| { |
| unsigned int uid = INSN_UID (insn); |
| if (!INSN_P (insn)) |
| continue; |
| |
| for (def = DF_INSN_UID_DEFS (df, uid); 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_MUST_CLOBBER | DF_REF_MAY_CLOBBER)) |
| { |
| /* Only must clobbers for the entire reg destroy the |
| value. */ |
| if ((DF_REF_FLAGS (def) & DF_REF_MUST_CLOBBER) |
| && (!DF_REF_FLAGS (def) & DF_REF_PARTIAL)) |
| 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); |
| } |
| |
| for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref) |
| if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) |
| { |
| unsigned int regno = DF_REF_REGNO (def); |
| if (!bitmap_bit_p (seen_in_block, regno)) |
| { |
| bitmap_set_bit (seen_in_block, regno); |
| bitmap_set_bit (bb_info->gen, regno); |
| } |
| } |
| } |
| |
| |
| /* 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) |
| { |
| df_ur_bb_local_compute (dflow, bb_index); |
| } |
| |
| df_unset_seen (); |
| } |
| |
| |
| /* Initialize the solution vectors. */ |
| |
| static void |
| df_ur_init (struct dataflow *dflow, bitmap all_blocks) |
| { |
| 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); |
| } |
| } |
| |
| |
| /* Or in the stack regs, hard regs and early clobber regs into the the |
| ur_in sets of all of the blocks. */ |
| |
| static void |
| df_ur_local_finalize (struct dataflow *dflow, 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; |
| |
| 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); |
| |
| /* 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); |
| } |
| |
| |
| /* Confluence function that ignores fake edges. */ |
| |
| static void |
| df_ur_confluence_n (struct dataflow *dflow, edge e) |
| { |
| 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); |
| } |
| |
| |
| /* Transfer function. */ |
| |
| static bool |
| df_ur_transfer_function (struct dataflow *dflow, int bb_index) |
| { |
| 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; |
| |
| return bitmap_ior_and_compl (out, gen, in, kill); |
| } |
| |
| |
| /* Free all storage associated with the problem. */ |
| |
| static void |
| df_ur_free (struct dataflow *dflow) |
| { |
| if (dflow->block_info) |
| { |
| unsigned int i; |
| |
| for (i = 0; i < dflow->block_info_size; i++) |
| { |
| struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, i); |
| if (bb_info) |
| { |
| BITMAP_FREE (bb_info->gen); |
| BITMAP_FREE (bb_info->kill); |
| BITMAP_FREE (bb_info->in); |
| BITMAP_FREE (bb_info->out); |
| } |
| } |
| |
| free_alloc_pool (dflow->block_pool); |
| dflow->block_info_size = 0; |
| free (dflow->block_info); |
| } |
| free (dflow); |
| } |
| |
| |
| /* Debugging info. */ |
| |
| static void |
| df_ur_dump (struct dataflow *dflow, FILE *file) |
| { |
| basic_block bb; |
| |
| if (!dflow->block_info) |
| return; |
| |
| fprintf (file, "Undefined regs:\n"); |
| |
| FOR_ALL_BB (bb) |
| { |
| 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); |
| } |
| } |
| |
| /* All of the information associated with every instance of the problem. */ |
| |
| static struct df_problem problem_UR = |
| { |
| DF_UR, /* Problem id. */ |
| DF_FORWARD, /* Direction. */ |
| df_ur_alloc, /* Allocate the problem specific data. */ |
| NULL, /* Reset global information. */ |
| 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. */ |
| df_lr_add_problem, /* Dependent problem. */ |
| 0 /* Changeable flags. */ |
| }; |
| |
| |
| /* 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_ur_add_problem (struct df *df, int flags) |
| { |
| return df_add_problem (df, &problem_UR, flags); |
| } |
| |
| |
| |
| /*---------------------------------------------------------------------------- |
| UNINITIALIZED REGISTERS WITH EARLYCLOBBER |
| |
| Find the set of uses for registers that are reachable from the entry |
| block without passing thru a definition. In and out bitvectors are built |
| for each basic block. The regnum is used to index into these sets. |
| See df.h for details. |
| |
| This is a variant of the UR problem above that has a lot of special |
| features just for the register allocation phase. This problem |
| should go a away if someone would fix the interference graph. |
| |
| ----------------------------------------------------------------------------*/ |
| |
| /* Private data used to compute the solution for this problem. These |
| data structures are not accessible outside of this module. */ |
| 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 |
| }; |
| |
| |
| /* Get basic block info. */ |
| |
| struct df_urec_bb_info * |
| df_urec_get_bb_info (struct dataflow *dflow, unsigned int index) |
| { |
| return (struct df_urec_bb_info *) dflow->block_info[index]; |
| } |
| |
| |
| /* Set basic block info. */ |
| |
| static void |
| df_urec_set_bb_info (struct dataflow *dflow, unsigned int index, |
| struct df_urec_bb_info *bb_info) |
| { |
| dflow->block_info[index] = bb_info; |
| } |
| |
| |
| /* Free basic block info. */ |
| |
| static void |
| df_urec_free_bb_info (struct dataflow *dflow, |
| basic_block bb ATTRIBUTE_UNUSED, |
| void *vbb_info) |
| { |
| 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); |
| } |
| } |
| |
| |
| /* Allocate or reset bitmaps for DFLOW blocks. The solution bits are |
| not touched unless the block is new. */ |
| |
| static void |
| df_urec_alloc (struct dataflow *dflow, bitmap blocks_to_rescan, |
| bitmap all_blocks ATTRIBUTE_UNUSED) |
| |
| { |
| 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); |
| |
| if (!dflow->problem_data) |
| { |
| problem_data = XNEW (struct df_urec_problem_data); |
| dflow->problem_data = problem_data; |
| } |
| problem_data->earlyclobbers_found = false; |
| |
| df_grow_bb_info (dflow); |
| |
| 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); |
| } |
| } |
| } |
| |
| |
| /* The function modifies local info for register REG being changed in |
| SETTER. DATA is used to pass the current basic block info. */ |
| |
| static void |
| df_urec_mark_reg_change (rtx reg, rtx setter, void *data) |
| { |
| int regno; |
| int endregno; |
| int i; |
| struct df_urec_bb_info *bb_info = (struct df_urec_bb_info*) data; |
| |
| if (GET_CODE (reg) == SUBREG) |
| reg = SUBREG_REG (reg); |
| |
| 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 |
| { |
| 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); |
| } |
| } |
| /* Classes of registers which could be early clobbered in the current |
| insn. */ |
| |
| 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. */ |
| |
| static bool |
| df_urec_check_earlyclobber (rtx insn) |
| { |
| int opno; |
| bool found = false; |
| |
| 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]; |
| |
| class = NO_REGS; |
| amp_p = false; |
| for (;;) |
| { |
| c = *p; |
| switch (c) |
| { |
| 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; |
| |
| case '&': |
| amp_p = true; |
| break; |
| case '\0': |
| case ',': |
| if (amp_p && class != NO_REGS) |
| { |
| int rc; |
| |
| found = true; |
| for (i = 0; |
| VEC_iterate (int, earlyclobber_regclass, i, rc); |
| i++) |
| { |
| if (rc == (int) class) |
| goto found_rc; |
| } |
| |
| /* 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) |
| { |
| 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) |
| { |
| int rc; |
| |
| 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 (reg_classes_intersect_p (rc, pref_class) |
| || (rc != NO_REGS |
| && reg_classes_intersect_p (rc, alt_class))) |
| { |
| bitmap_set_bit (bb_info->earlyclobber, regno); |
| break; |
| } |
| } |
| } |
| 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) |
| { |
| for_each_rtx (x, df_urec_mark_reg_use_for_earlyclobber, data); |
| } |
| |
| |
| /* Compute local uninitialized register info for basic block BB. */ |
| |
| static void |
| df_urec_bb_local_compute (struct dataflow *dflow, unsigned int bb_index) |
| { |
| 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; |
| |
| for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref) |
| if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) |
| { |
| unsigned int regno = DF_REF_REGNO (def); |
| bitmap_set_bit (bb_info->gen, regno); |
| } |
| |
| FOR_BB_INSNS (bb, insn) |
| { |
| if (INSN_P (insn)) |
| { |
| note_stores (PATTERN (insn), df_urec_mark_reg_change, bb_info); |
| if (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); |
| } |
| } |
| } |
| |
| for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref) |
| if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0) |
| { |
| unsigned int regno = DF_REF_REGNO (def); |
| bitmap_set_bit (bb_info->gen, regno); |
| } |
| |
| } |
| |
| |
| /* Compute local uninitialized register info. */ |
| |
| static void |
| df_urec_local_compute (struct dataflow *dflow, |
| bitmap all_blocks ATTRIBUTE_UNUSED, |
| bitmap rescan_blocks) |
| { |
| 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 |
| |
| /* 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); |
| |
| EXECUTE_IF_SET_IN_BITMAP (rescan_blocks, 0, bb_index, bi) |
| { |
| df_urec_bb_local_compute (dflow, bb_index); |
| } |
| |
| VEC_free (int, heap, earlyclobber_regclass); |
| } |
| |
| |
| /* Initialize the solution vectors. */ |
| |
| static void |
| df_urec_init (struct dataflow *dflow, bitmap all_blocks) |
| { |
| unsigned int bb_index; |
| 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); |
| |
| bitmap_copy (bb_info->out, bb_info->gen); |
| bitmap_clear (bb_info->in); |
| } |
| } |
| |
| |
| /* Or in the stack regs, hard regs and early clobber regs into the the |
| ur_in sets of all of the blocks. */ |
| |
| static void |
| df_urec_local_finalize (struct dataflow *dflow, 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; |
| |
| 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); |
| |
| if (bb_index != ENTRY_BLOCK && bb_index != EXIT_BLOCK) |
| { |
| 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 |
| } |
| |
| /* 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 |
| } |
| |
| #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) |
| { |
| 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_ior_into (op1, op2); |
| } |
| |
| |
| /* Transfer function. */ |
| |
| static bool |
| df_urec_transfer_function (struct dataflow *dflow, 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; |
| |
| return bitmap_ior_and_compl (out, gen, in, kill); |
| } |
| |
| |
| /* Free all storage associated with the problem. */ |
| |
| static void |
| df_urec_free (struct dataflow *dflow) |
| { |
| if (dflow->block_info) |
| { |
| unsigned int i; |
| |
| for (i = 0; i < dflow->block_info_size; i++) |
| { |
| struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, i); |
| 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); |
| } |
| } |
| |
| free_alloc_pool (dflow->block_pool); |
| |
| dflow->block_info_size = 0; |
| free (dflow->block_info); |
| free (dflow->problem_data); |
| } |
| free (dflow); |
| } |
| |
| |
| /* Debugging info. */ |
| |
| static void |
| df_urec_dump (struct dataflow *dflow, FILE *file) |
| { |
| basic_block bb; |
| |
| if (!dflow->block_info) |
| return; |
| |
| fprintf (file, "Undefined regs:\n"); |
| |
| FOR_ALL_BB (bb) |
| { |
| 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); |
| } |
| } |
| |
| /* All of the information associated with every instance of the problem. */ |
| |
| static struct df_problem problem_UREC = |
| { |
| DF_UREC, /* Problem id. */ |
| DF_FORWARD, /* Direction. */ |
| df_urec_alloc, /* Allocate the problem specific data. */ |
| NULL, /* Reset global information. */ |
| 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. */ |
| df_lr_add_problem, /* Dependent problem. */ |
| 0 /* Changeable flags. */ |
| }; |
| |
| |
| /* 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_urec_add_problem (struct df *df, int flags) |
| { |
| return df_add_problem (df, &problem_UREC, flags); |
| } |
| |
| |
| |
| /*---------------------------------------------------------------------------- |
| 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). |
| ----------------------------------------------------------------------------*/ |
| |
| /* Create def-use or use-def chains. */ |
| |
| static void |
| df_chain_alloc (struct dataflow *dflow, |
| bitmap blocks_to_rescan ATTRIBUTE_UNUSED, |
| bitmap all_blocks ATTRIBUTE_UNUSED) |
| |
| { |
| struct df *df = dflow->df; |
| unsigned int i; |
| |
| /* Wholesale destruction of the old chains. */ |
| if (dflow->block_pool) |
| free_alloc_pool (dflow->block_pool); |
| |
| dflow->block_pool = create_alloc_pool ("df_chain_chain_block pool", |
| sizeof (struct df_link), 100); |
| |
| if (dflow->flags & DF_DU_CHAIN) |
| { |
| 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++) |
| { |
| struct df_ref *ref = df->def_info.refs[i]; |
| DF_REF_CHAIN (ref) = NULL; |
| } |
| } |
| |
| if (dflow->flags & DF_UD_CHAIN) |
| { |
| if (!df->use_info.refs_organized) |
| df_reorganize_refs (&df->use_info); |
| for (i = 0; i < DF_USES_SIZE (df); i++) |
| { |
| struct df_ref *ref = df->use_info.refs[i]; |
| DF_REF_CHAIN (ref) = NULL; |
| } |
| } |
| } |
| |
| |
| /* Reset all def_use and use_def chains in INSN. */ |
| |
| static void |
| df_chain_insn_reset (struct dataflow *dflow, rtx insn) |
| { |
| struct df *df = dflow->df; |
| unsigned int uid = INSN_UID (insn); |
| struct df_insn_info *insn_info = NULL; |
| struct df_ref *ref; |
| |
| if (uid < df->insns_size) |
| insn_info = DF_INSN_UID_GET (df, uid); |
| |
| if (insn_info) |
| { |
| if (dflow->flags & DF_DU_CHAIN) |
| { |
| ref = insn_info->defs; |
| while (ref) |
| { |
| ref->chain = NULL; |
| ref = ref->next_ref; |
| } |
| } |
| |
| if (dflow->flags & DF_UD_CHAIN) |
| { |
| ref = insn_info->uses; |
| while (ref) |
| { |
| ref->chain = NULL; |
| ref = ref->next_ref; |
| } |
| } |
| } |
| } |
| |
| |
| /* Reset all def_use and use_def chains in basic block. */ |
| |
| static void |
| df_chain_bb_reset (struct dataflow *dflow, unsigned int bb_index) |
| { |
| struct df *df = dflow->df; |
| rtx insn; |
| basic_block bb = BASIC_BLOCK (bb_index); |
| |
| /* Some one deleted the basic block out from under us. */ |
| if (!bb) |
| return; |
| |
| FOR_BB_INSNS (bb, insn) |
| { |
| if (INSN_P (insn)) |
| { |
| /* Record defs within INSN. */ |
| df_chain_insn_reset (dflow, insn); |
| } |
| } |
| |
| /* Get rid of any chains in artificial uses or defs. */ |
| if (dflow->flags & DF_DU_CHAIN) |
| { |
| struct df_ref *def; |
| def = df_get_artificial_defs (df, bb_index); |
| while (def) |
| { |
| def->chain = NULL; |
| def = def->next_ref; |
| } |
| } |
| |
| if (dflow->flags & DF_UD_CHAIN) |
| { |
| struct df_ref *use; |
| use = df_get_artificial_uses (df, bb_index); |
| while (use) |
| { |
| use->chain = NULL; |
| use = use->next_ref; |
| } |
| } |
| } |
| |
| |
| /* Reset all of the chains when the set of basic blocks changes. */ |
| |
| |
| static void |
| df_chain_reset (struct dataflow *dflow, bitmap blocks_to_clear) |
| { |
| bitmap_iterator bi; |
| unsigned int bb_index; |
| |
| EXECUTE_IF_SET_IN_BITMAP (blocks_to_clear, 0, bb_index, bi) |
| { |
| df_chain_bb_reset (dflow, bb_index); |
| } |
| |
| free_alloc_pool (dflow->block_pool); |
| dflow->block_pool = NULL; |
| } |
| |
| |
| /* Create the chains for a list of USEs. */ |
| |
| static void |
| df_chain_create_bb_process_use (struct dataflow *dflow, |
| 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) |
| { |
| /* Do not want to go through 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 (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP)) |
| { |
| 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 (dflow->flags & DF_DU_CHAIN) |
| df_chain_create (dflow, def, use); |
| if (dflow->flags & DF_UD_CHAIN) |
| df_chain_create (dflow, use, def); |
| } |
| } |
| } |
| use = use->next_ref; |
| } |
| } |
| |
| /* 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.*/ |
| |
| /* 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_ref *def; |
| |
| bitmap_copy (cpy, bb_info->in); |
| |
| /* 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. */ |
| df_chain_create_bb_process_use (dflow, cpy, |
| df_get_artificial_uses (df, bb->index), |
| DF_REF_AT_TOP); |
| #endif |
| |
| for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref) |
| if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) |
| { |
| unsigned int dregno = DF_REF_REGNO (def); |
| if (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL)) |
| bitmap_clear_range (cpy, |
| DF_REG_DEF_GET (df, dregno)->begin, |
| DF_REG_DEF_GET (df, dregno)->n_refs); |
| 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); |
| |
| if (!INSN_P (insn)) |
| continue; |
| |
| /* Now scan the uses and link them up with the defs that remain |
| in the cpy vector. */ |
| |
| df_chain_create_bb_process_use (dflow, cpy, |
| DF_INSN_UID_USES (df, uid), 0); |
| |
| /* Since we are going forwards, process the defs second. This |
| pass only changes the bits in cpy. */ |
| for (def = DF_INSN_UID_DEFS (df, uid); def; def = def->next_ref) |
| { |
| unsigned int dregno = DF_REF_REGNO (def); |
| if (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL)) |
| 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_MUST_CLOBBER | DF_REF_MAY_CLOBBER))) |
| bitmap_set_bit (cpy, DF_REF_ID (def)); |
| } |
| } |
| |
| /* Create the chains for the artificial uses of the hard registers |
| at the end of the block. */ |
| df_chain_create_bb_process_use (dflow, cpy, |
| df_get_artificial_uses (df, bb->index), 0); |
| } |
| |
| /* Create def-use chains from reaching use bitmaps for basic blocks |
| in BLOCKS. */ |
| |
| static void |
| df_chain_finalize (struct dataflow *dflow, 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]; |
| |
| EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) |
| { |
| df_chain_create_bb (dflow, rd_dflow, bb_index); |
| } |
| } |
| |
| |
| /* Free all storage associated with the problem. */ |
| |
| static void |
| df_chain_free (struct dataflow *dflow) |
| { |
| free_alloc_pool (dflow->block_pool); |
| free (dflow); |
| } |
| |
| |
| /* Debugging info. */ |
| |
| static void |
| df_chains_dump (struct dataflow *dflow, FILE *file) |
| { |
| struct df *df = dflow->df; |
| unsigned int j; |
| |
| if (dflow->flags & DF_DU_CHAIN) |
| { |
| 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_REF_INSN (def) ? |
| DF_INSN_LUID (df, DF_REF_INSN (def)): |
| -1, |
| 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_REF_CHAIN (def), file); |
| fprintf (file, "\n"); |
| } |
| } |
| } |
| |
| if (dflow->flags & DF_UD_CHAIN) |
| { |
| fprintf (file, "Use-def chains:\n"); |
| for (j = 0; j < df->use_info.bitmap_size; j++) |
| { |
| struct df_ref *use = DF_USES_GET (df, j); |
| if (use) |
| { |
| 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_REF_CHAIN (use), file); |
| fprintf (file, "\n"); |
| } |
| } |
| } |
| } |
| |
| |
| 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_chains_dump, /* Debugging. */ |
| df_rd_add_problem, /* Dependent problem. */ |
| 0 /* Changeable flags. */ |
| }; |
| |
| |
| /* 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_chain_add_problem (struct df *df, int flags) |
| { |
| return df_add_problem (df, &problem_CHAIN, flags); |
| } |
| |
| |
| /*---------------------------------------------------------------------------- |
| REGISTER INFORMATION |
| |
| This pass properly computes REG_DEAD and REG_UNUSED notes. |
| |
| If the DF_RI_LIFE flag is set the following vectors containing |
| information about register usage are properly set: REG_N_REFS, |
| REG_N_DEATHS, REG_N_SETS, REG_LIVE_LENGTH, REG_N_CALLS_CROSSED, |
| REG_N_THROWING_CALLS_CROSSED and REG_BASIC_BLOCK. |
| |
| ----------------------------------------------------------------------------*/ |
| |
| #ifdef REG_DEAD_DEBUGGING |
| static void |
| print_note (char *prefix, rtx insn, rtx note) |
| { |
| fprintf (stderr, "%s %d ", prefix, INSN_UID (insn)); |
| print_rtl (stderr, note); |
| fprintf (stderr, "\n"); |
| } |
| #endif |
| |
| /* Allocate the lifetime information. */ |
| |
| static void |
| df_ri_alloc (struct dataflow *dflow, |
| bitmap blocks_to_rescan ATTRIBUTE_UNUSED, |
| bitmap all_blocks ATTRIBUTE_UNUSED) |
| { |
| int i; |
| struct df *df = dflow->df; |
| |
| if (dflow->flags & DF_RI_LIFE) |
| { |
| max_regno = max_reg_num (); |
| allocate_reg_info (max_regno, FALSE, FALSE); |
| |
| /* Reset all the data we'll collect. */ |
| for (i = 0; i < max_regno; i++) |
| { |
| REG_N_SETS (i) = DF_REG_DEF_COUNT (df, i); |
| REG_N_REFS (i) = DF_REG_USE_COUNT (df, i) + REG_N_SETS (i); |
| REG_N_DEATHS (i) = 0; |
| REG_N_CALLS_CROSSED (i) = 0; |
| REG_N_THROWING_CALLS_CROSSED (i) = 0; |
| REG_LIVE_LENGTH (i) = 0; |
| REG_FREQ (i) = 0; |
| REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN; |
| } |
| } |
| } |
| |
| |
| /* 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. */ |
| |
| static inline bool |
| df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED) |
| { |
| #ifdef STACK_REGS |
| return (regstack_completed |
| && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG)); |
| #else |
| return false; |
| #endif |
| } |
| |
| |
| /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN. */ |
| |
| static void |
| df_kill_notes (rtx insn, int flags) |
| { |
| rtx *pprev = ®_NOTES (insn); |
| rtx link = *pprev; |
| |
| while (link) |
| { |
| switch (REG_NOTE_KIND (link)) |
| { |
| case REG_DEAD: |
| if (flags & DF_RI_LIFE) |
| if (df_ignore_stack_reg (REGNO (XEXP (link, 0)))) |
| REG_N_DEATHS (REGNO (XEXP (link, 0)))++; |
| |
| /* Fallthru */ |
| case REG_UNUSED: |
| if (!df_ignore_stack_reg (REGNO (XEXP (link, 0)))) |
| { |
| rtx next = XEXP (link, 1); |
| #ifdef REG_DEAD_DEBUGGING |
| print_note ("deleting: ", insn, link); |
| #endif |
| free_EXPR_LIST_node (link); |
| *pprev = link = next; |
| } |
| break; |
| |
| default: |
| pprev = &XEXP (link, 1); |
| link = *pprev; |
| break; |
| } |
| } |
| } |
| |
| |
| /* 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_set_unused_notes_for_mw (rtx insn, struct df_mw_hardreg *mws, |
| bitmap live, bitmap do_not_gen, |
| bitmap artificial_uses, int flags) |
| { |
| bool all_dead = true; |
| struct df_link *regs = mws->regs; |
| unsigned int regno = DF_REF_REGNO (regs->ref); |
| |
| #ifdef REG_DEAD_DEBUGGING |
| fprintf (stderr, "mw unused looking at %d\n", DF_REF_REGNO (regs->ref)); |
| df_ref_debug (regs->ref, stderr); |
| #endif |
| while (regs) |
| { |
| unsigned int regno = DF_REF_REGNO (regs->ref); |
| if ((bitmap_bit_p (live, regno)) |
| || bitmap_bit_p (artificial_uses, regno)) |
| { |
| all_dead = false; |
| break; |
| } |
| regs = regs->next; |
| } |
| |
| if (all_dead) |
| { |
| struct df_link *regs = mws->regs; |
| rtx note = alloc_EXPR_LIST (REG_UNUSED, *DF_REF_LOC (regs->ref), |
| REG_NOTES (insn)); |
| REG_NOTES (insn) = note; |
| #ifdef REG_DEAD_DEBUGGING |
| print_note ("adding 1: ", insn, note); |
| #endif |
| bitmap_set_bit (do_not_gen, regno); |
| /* Only do this if the value is totally dead. */ |
| if (flags & DF_RI_LIFE) |
| { |
| REG_N_DEATHS (regno) ++; |
| REG_LIVE_LENGTH (regno)++; |
| } |
| } |
| else |
| { |
| struct df_link *regs = mws->regs; |
| while (regs) |
| { |
| struct df_ref *ref = regs->ref; |
| |
| regno = DF_REF_REGNO (ref); |
| if ((!bitmap_bit_p (live, regno)) |
| && (!bitmap_bit_p (artificial_uses, regno))) |
| { |
| rtx note = alloc_EXPR_LIST (REG_UNUSED, regno_reg_rtx[regno], |
| REG_NOTES (insn)); |
| REG_NOTES (insn) = note; |
| #ifdef REG_DEAD_DEBUGGING |
| print_note ("adding 2: ", insn, note); |
| #endif |
| } |
| bitmap_set_bit (do_not_gen, regno); |
| regs = regs->next; |
| } |
| } |
| } |
| |
| |
| /* 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, int flags) |
| { |
| bool all_dead = true; |
| struct df_link *regs = mws->regs; |
| unsigned int regno = DF_REF_REGNO (regs->ref); |
| |
| #ifdef REG_DEAD_DEBUGGING |
| fprintf (stderr, "mw looking at %d\n", DF_REF_REGNO (regs->ref)); |
| df_ref_debug (regs->ref, stderr); |
| #endif |
| while (regs) |
| { |
| unsigned int regno = DF_REF_REGNO (regs->ref); |
| if ((bitmap_bit_p (live, regno)) |
| || bitmap_bit_p (artificial_uses, regno)) |
| { |
| all_dead = false; |
| break; |
| } |
| regs = regs->next; |
| } |
| |
| if (all_dead) |
| { |
| if (!bitmap_bit_p (do_not_gen, regno)) |
| { |
| /* Add a dead note for the entire multi word register. */ |
| struct df_link *regs = mws->regs; |
| rtx note = alloc_EXPR_LIST (REG_DEAD, *DF_REF_LOC (regs->ref), |
| REG_NOTES (insn)); |
| REG_NOTES (insn) = note; |
| #ifdef REG_DEAD_DEBUGGING |
| print_note ("adding 1: ", insn, note); |
| #endif |
| |
| if (flags & DF_RI_LIFE) |
| { |
| struct df_link *regs = mws->regs; |
| while (regs) |
| { |
| struct df_ref *ref = regs->ref; |
| regno = DF_REF_REGNO (ref); |
| REG_N_DEATHS (regno)++; |
| regs = regs->next; |
| } |
| } |
| } |
| } |
| else |
| { |
| struct df_link *regs = mws->regs; |
| while (regs) |
| { |
| struct df_ref *ref = regs->ref; |
| |
| regno = DF_REF_REGNO (ref); |
| if ((!bitmap_bit_p (live, regno)) |
| && (!bitmap_bit_p (artificial_uses, regno)) |
| && (!bitmap_bit_p (do_not_gen, regno))) |
| { |
| rtx note = alloc_EXPR_LIST (REG_DEAD, regno_reg_rtx[regno], |
| REG_NOTES (insn)); |
| REG_NOTES (insn) = note; |
| if (flags & DF_RI_LIFE) |
| REG_N_DEATHS (regno)++; |
| #ifdef REG_DEAD_DEBUGGING |
| print_note ("adding 2: ", insn, note); |
| #endif |
| } |
| |
| regs = regs->next; |
| } |
| } |
| } |
| |
| |
| /* Create a REG_UNUSED note if necessary for DEF in INSN updating LIVE |
| and DO_NOT_GEN. Do not generate notes for registers in artificial |
| uses. */ |
| |
| static void |
| df_create_unused_note (basic_block bb, rtx insn, struct df_ref *def, |
| bitmap live, bitmap do_not_gen, bitmap artificial_uses, |
| bitmap local_live, bitmap local_processed, |
| int flags, int luid) |
| { |
| unsigned int dregno = DF_REF_REGNO (def); |
| |
| #ifdef REG_DEAD_DEBUGGING |
| fprintf (stderr, " regular looking at def "); |
| df_ref_debug (def, stderr); |
| #endif |
| |
| if (bitmap_bit_p (live, dregno)) |
| { |
| if (flags & DF_RI_LIFE) |
| { |
| /* If we have seen this regno, then it has already been |
| processed correctly with the per insn increment. If we |
| have not seen it we need to add the length from here to |
| the end of the block to the live length. */ |
| if (bitmap_bit_p (local_processed, dregno)) |
| { |
| if (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL)) |
| bitmap_clear_bit (local_live, dregno); |
| } |
| else |
| { |
| bitmap_set_bit (local_processed, dregno); |
| REG_LIVE_LENGTH (dregno) += luid; |
| } |
| } |
| } |
| else if ((!(DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)) |
| && (!bitmap_bit_p (artificial_uses, dregno)) |
| && (!df_ignore_stack_reg (dregno))) |
| { |
| rtx reg = GET_CODE (*DF_REF_LOC (def)) == SUBREG ? |
| SUBREG_REG (*DF_REF_LOC (def)) : *DF_REF_LOC (def); |
| rtx note = alloc_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn)); |
| REG_NOTES (insn) = note; |
| #ifdef REG_DEAD_DEBUGGING |
| print_note ("adding 3: ", insn, note); |
| #endif |
| if (flags & DF_RI_LIFE) |
| { |
| REG_N_DEATHS (dregno) ++; |
| REG_LIVE_LENGTH (dregno)++; |
| } |
| } |
| |
| if ((flags & DF_RI_LIFE) && (dregno >= FIRST_PSEUDO_REGISTER)) |
| { |
| REG_FREQ (dregno) += REG_FREQ_FROM_BB (bb); |
| if (REG_BASIC_BLOCK (dregno) == REG_BLOCK_UNKNOWN) |
| REG_BASIC_BLOCK (dregno) = bb->index; |
| else if (REG_BASIC_BLOCK (dregno) != bb->index) |
| REG_BASIC_BLOCK (dregno) = REG_BLOCK_GLOBAL; |
| } |
| |
| if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER + DF_REF_MAY_CLOBBER))) |
| bitmap_set_bit (do_not_gen, dregno); |
| |
| /* Kill this register if it is not a subreg store. */ |
| if (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL)) |
| bitmap_clear_bit (live, dregno); |
| } |
| |
| |
| /* 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_ri_bb_compute (struct dataflow *dflow, unsigned int bb_index, |
| bitmap live, bitmap do_not_gen, bitmap artificial_uses, |
| bitmap local_live, bitmap local_processed, bitmap setjumps_crossed) |
| { |
| struct df *df = dflow->df; |
| basic_block bb = BASIC_BLOCK (bb_index); |
| rtx insn; |
| struct df_ref *def; |
| struct df_ref *use; |
| int luid = 0; |
| |
| bitmap_copy (live, df_get_live_out (df, bb)); |
| bitmap_clear (artificial_uses); |
| |
| if (dflow->flags & DF_RI_LIFE) |
| { |
| /* Process the regs live at the end of the block. Mark them as |
| not local to any one basic block. */ |
| bitmap_iterator bi; |
| unsigned int regno; |
| EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi) |
| REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL; |
| } |
| |
| /* Process the artificial defs and uses at the bottom of the block |
| to begin processing. */ |
| for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref) |
| if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0) |
| bitmap_clear_bit (live, DF_REF_REGNO (def)); |
| |
| for (use = df_get_artificial_uses (df, bb_index); use; use = use->next_ref) |
| 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); |
| } |
| |
| FOR_BB_INSNS_REVERSE (bb, insn) |
| { |
| unsigned int uid = INSN_UID (insn); |
| unsigned int regno; |
| bitmap_iterator bi; |
| struct df_mw_hardreg *mws; |
| |
| if (!INSN_P (insn)) |
| continue; |
| |
| if (dflow->flags & DF_RI_LIFE) |
| { |
| /* Increment the live_length for all of the registers that |
| are are referenced in this block and live at this |
| particular point. */ |
| bitmap_iterator bi; |
| unsigned int regno; |
| EXECUTE_IF_SET_IN_BITMAP (local_live, 0, regno, bi) |
| { |
| REG_LIVE_LENGTH (regno)++; |
| } |
| luid++; |
| } |
| |
| bitmap_clear (do_not_gen); |
| df_kill_notes (insn, dflow->flags); |
| |
| /* Process the defs. */ |
| if (CALL_P (insn)) |
| { |
| if (dflow->flags & DF_RI_LIFE) |
| { |
| bool can_throw = can_throw_internal (insn); |
| bool set_jump = (find_reg_note (insn, REG_SETJMP, NULL) != NULL); |
| EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi) |
| { |
| REG_N_CALLS_CROSSED (regno)++; |
| if (can_throw) |
| REG_N_THROWING_CALLS_CROSSED (regno)++; |
| |
| /* We have a problem with any pseudoreg that lives |
| across the setjmp. ANSI says that if a user |
| variable does not change in value between the |
| setjmp and the longjmp, then the longjmp |
| preserves it. This includes longjmp from a place |
| where the pseudo appears dead. (In principle, |
| the value still exists if it is in scope.) If |
| the pseudo goes in a hard reg, some other value |
| may occupy that hard reg where this pseudo is |
| dead, thus clobbering the pseudo. Conclusion: |
| such a pseudo must not go in a hard reg. */ |
| if (set_jump && regno >= FIRST_PSEUDO_REGISTER) |
| bitmap_set_bit (setjumps_crossed, regno); |
| } |
| } |
| |
| /* We only care about real sets for calls. Clobbers only |
| may clobber and cannot be depended on. */ |
| for (mws = DF_INSN_UID_MWS (df, uid); mws; mws = mws->next) |
| { |
| if ((mws->type == DF_REF_REG_DEF) |
| && !df_ignore_stack_reg (REGNO (mws->mw_reg))) |
| df_set_unused_notes_for_mw (insn, mws, live, do_not_gen, |
| artificial_uses, dflow->flags); |
| } |
| |
| /* All of the defs except the return value are some sort of |
| clobber. This code is for the return. */ |
| for (def = DF_INSN_UID_DEFS (df, uid); def; def = def->next_ref) |
| if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))) |
| df_create_unused_note (bb, insn, def, live, do_not_gen, |
| artificial_uses, local_live, |
| local_processed, dflow->flags, luid); |
| |
| } |
| else |
| { |
| /* Regular insn. */ |
| for (mws = DF_INSN_UID_MWS (df, uid); mws; mws = mws->next) |
| { |
| if (mws->type == DF_REF_REG_DEF) |
| df_set_unused_notes_for_mw (insn, mws, live, do_not_gen, |
| artificial_uses, dflow->flags); |
| } |
| |
| for (def = DF_INSN_UID_DEFS (df, uid); def; def = def->next_ref) |
| df_create_unused_note (bb, insn, def, live, do_not_gen, |
| artificial_uses, local_live, |
| local_processed, dflow->flags, luid); |
| } |
| |
| /* Process the uses. */ |
| for (mws = DF_INSN_UID_MWS (df, uid); mws; mws = mws->next) |
| { |
| if ((mws->type != DF_REF_REG_DEF) |
| && !df_ignore_stack_reg (REGNO (mws->mw_reg))) |
| df_set_dead_notes_for_mw (insn, mws, live, do_not_gen, |
| artificial_uses, dflow->flags); |
| } |
| |
| for (use = DF_INSN_UID_USES (df, uid); use; use = use->next_ref) |
| { |
| unsigned int uregno = DF_REF_REGNO (use); |
| |
| if ((dflow->flags & DF_RI_LIFE) && (uregno >= FIRST_PSEUDO_REGISTER)) |
| { |
| REG_FREQ (uregno) += REG_FREQ_FROM_BB (bb); |
| if (REG_BASIC_BLOCK (uregno) == REG_BLOCK_UNKNOWN) |
| REG_BASIC_BLOCK (uregno) = bb->index; |
| else if (REG_BASIC_BLOCK (uregno) != bb->index) |
| REG_BASIC_BLOCK (uregno) = REG_BLOCK_GLOBAL; |
| } |
| |
| #ifdef REG_DEAD_DEBUGGING |
| fprintf (stderr, " regular looking at use "); |
| df_ref_debug (use, stderr); |
| #endif |
| if (!bitmap_bit_p (live, uregno)) |
| { |
| if ( (!(DF_REF_FLAGS (use) & DF_REF_MW_HARDREG)) |
| && (!bitmap_bit_p (do_not_gen, uregno)) |
| && (!bitmap_bit_p (artificial_uses, uregno)) |
| && (!(DF_REF_FLAGS (use) & DF_REF_READ_WRITE)) |
| && (!df_ignore_stack_reg (uregno))) |
| { |
| rtx reg = GET_CODE (*DF_REF_LOC (use)) == SUBREG ? |
| SUBREG_REG (*DF_REF_LOC (use)) : *DF_REF_LOC (use); |
| rtx note = alloc_EXPR_LIST (REG_DEAD, reg, REG_NOTES (insn)); |
| REG_NOTES (insn) = note; |
| if (dflow->flags & DF_RI_LIFE) |
| REG_N_DEATHS (uregno)++; |
| |
| #ifdef REG_DEAD_DEBUGGING |
| print_note ("adding 4: ", insn, note); |
| #endif |
| } |
| /* This register is now live. */ |
| bitmap_set_bit (live, uregno); |
| |
| if (dflow->flags & DF_RI_LIFE) |
| { |
| /* If we have seen this regno, then it has already |
| been processed correctly with the per insn |
| increment. If we have not seen it we set the bit |
| so that begins to get processed locally. Note |
| that we don't even get here if the variable was |
| live at the end of the block since just a ref |
| inside the block does not effect the |
| calculations. */ |
| REG_LIVE_LENGTH (uregno) ++; |
| bitmap_set_bit (local_live, uregno); |
| bitmap_set_bit (local_processed, uregno); |
| } |
| } |
| } |
| } |
| |
| if (dflow->flags & DF_RI_LIFE) |
| { |
| /* Add the length of the block to all of the registers that were |
| not referenced, but still live in this block. */ |
| bitmap_iterator bi; |
| unsigned int regno; |
| bitmap_and_compl_into (live, local_processed); |
| EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi) |
| { |
| REG_LIVE_LENGTH (regno) += luid; |
| } |
| bitmap_clear (local_processed); |
| bitmap_clear (local_live); |
| } |
| } |
| |
| |
| /* 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) |
| { |
| unsigned int bb_index; |
| bitmap_iterator bi; |
| bitmap live = BITMAP_ALLOC (NULL); |
| bitmap do_not_gen = BITMAP_ALLOC (NULL); |
| bitmap artificial_uses = BITMAP_ALLOC (NULL); |
| bitmap local_live = NULL; |
| bitmap local_processed = NULL; |
| bitmap setjumps_crossed = NULL; |
| |
| if (dflow->flags & DF_RI_LIFE) |
| { |
| local_live = BITMAP_ALLOC (NULL); |
| local_processed = BITMAP_ALLOC (NULL); |
| setjumps_crossed = BITMAP_ALLOC (NULL); |
| } |
| |
| |
| #ifdef REG_DEAD_DEBUGGING |
| df_lr_dump (dflow->df->problems_by_index [DF_LR], stderr); |
| print_rtl_with_bb (stderr, get_insns()); |
| #endif |
| |
| EXECUTE_IF_SET_IN_BITMAP (blocks_to_scan, 0, bb_index, bi) |
| { |
| df_ri_bb_compute (dflow, bb_index, live, do_not_gen, artificial_uses, |
| local_live, local_processed, setjumps_crossed); |
| } |
| |
| BITMAP_FREE (live); |
| BITMAP_FREE (do_not_gen); |
| BITMAP_FREE (artificial_uses); |
| if (dflow->flags & DF_RI_LIFE) |
| { |
| bitmap_iterator bi; |
| unsigned int regno; |
| /* See the setjump comment in df_ri_bb_compute. */ |
| EXECUTE_IF_SET_IN_BITMAP (setjumps_crossed, 0, regno, bi) |
| { |
| REG_BASIC_BLOCK (regno) = REG_BLOCK_UNKNOWN; |
| REG_LIVE_LENGTH (regno) = -1; |
| } |
| |
| BITMAP_FREE (local_live); |
| BITMAP_FREE (local_processed); |
| BITMAP_FREE (setjumps_crossed); |
| } |
| } |
| |
| |
| /* Free all storage associated with the problem. */ |
| |
| static void |
| df_ri_free (struct dataflow *dflow) |
| { |
| free (dflow->problem_data); |
| free (dflow); |
| } |
| |
| |
| /* Debugging info. */ |
| |
| static void |
| df_ri_dump (struct dataflow *dflow, FILE *file) |
| { |
| print_rtl_with_bb (file, get_insns ()); |
| |
| if (dflow->flags & DF_RI_LIFE) |
| { |
| fprintf (file, "Register info:\n"); |
| dump_flow_info (file, -1); |
| } |
| } |
| |
| /* All of the information associated every instance of the problem. */ |
| |
| static struct df_problem problem_RI = |
| { |
| DF_RI, /* Problem id. */ |
| DF_NONE, /* Direction. */ |
| df_ri_alloc, /* Allocate the problem specific data. */ |
| NULL, /* Reset global information. */ |
| 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. */ |
| |
| /* Technically this is only dependent on the live registers problem |
| but it will produce information if built one of uninitialized |
| register problems (UR, UREC) is also run. */ |
| df_lr_add_problem, /* Dependent problem. */ |
| 0 /* Changeable flags. */ |
| }; |
| |
| |
| /* 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_ri_add_problem (struct df *df, int flags) |
| { |
| return df_add_problem (df, &problem_RI, flags); |
| } |