diff options
Diffstat (limited to 'gcc-4.2.1-5666.3/gcc/df-problems.c')
| -rw-r--r-- | gcc-4.2.1-5666.3/gcc/df-problems.c | 3815 |
1 files changed, 0 insertions, 3815 deletions
diff --git a/gcc-4.2.1-5666.3/gcc/df-problems.c b/gcc-4.2.1-5666.3/gcc/df-problems.c deleted file mode 100644 index cdf4141f7..000000000 --- a/gcc-4.2.1-5666.3/gcc/df-problems.c +++ /dev/null @@ -1,3815 +0,0 @@ -/* 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); -} |