/* Standard problems for dataflow support routines.
- Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006
+ Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
Free Software Foundation, Inc.
Originally contributed by Michael P. Hayes
(m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
-Software Foundation; either version 2, or (at your option) any later
+Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
for more details.
You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
-02110-1301, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
#include "bitmap.h"
#include "timevar.h"
#include "df.h"
+#include "except.h"
+#include "dce.h"
+#include "vecprim.h"
+
+/* Note that turning REG_DEAD_DEBUGGING on will cause
+ gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints
+ addresses in the dumps. */
+#if 0
+#define REG_DEAD_DEBUGGING
+#endif
#define DF_SPARSE_THRESHOLD 32
/*----------------------------------------------------------------------------
Public functions access functions for the dataflow problems.
----------------------------------------------------------------------------*/
+/* Get the live at out set for BB no matter what problem happens to be
+ defined. This function is used by the register allocators who
+ choose different dataflow problems depending on the optimization
+ level. */
-/* Get the instance of the problem that DFLOW is dependent on. */
-
-struct dataflow *
-df_get_dependent_problem (struct dataflow *dflow)
-{
- struct df *df = dflow->df;
- struct df_problem *dependent_problem = dflow->problem->dependent_problem;
-
- gcc_assert (dependent_problem);
- return df->problems_by_index[dependent_problem->id];
-}
-
-
-/* Create a du or ud chain from SRC to DST and link it into SRC. */
-
-struct df_link *
-df_chain_create (struct dataflow *dflow, struct df_ref *src, struct df_ref *dst)
-{
- struct df_link *head = DF_REF_CHAIN (src);
- struct df_link *link = pool_alloc (dflow->block_pool);;
-
- DF_REF_CHAIN (src) = link;
- link->next = head;
- link->ref = dst;
- return link;
-}
-
-
-/* Delete a du or ud chain for REF. If LINK is NULL, delete all
- chains for ref and check to see if the reverse chains can also be
- deleted. If LINK is not NULL it must be a link off of ref. In
- this case, the other end is not deleted. */
-
-void
-df_chain_unlink (struct dataflow *dflow, struct df_ref *ref, struct df_link *link)
+bitmap
+df_get_live_out (basic_block bb)
{
- 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;
- }
- }
-}
-
+ gcc_assert (df_lr);
-/* 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;
- }
+ if (df_urec)
+ return DF_RA_LIVE_OUT (bb);
+ else if (df_live)
+ return DF_LIVE_OUT (bb);
+ else
+ return DF_LR_OUT (bb);
}
-
-/* Get the live in set for BB no matter what problem happens to be
- defined. */
+/* Get the live at in set for BB no matter what problem happens to be
+ defined. This function is used by the register allocators who
+ choose different dataflow problems depending on the optimization
+ level. */
bitmap
-df_get_live_in (struct df *df, basic_block bb)
+df_get_live_in (basic_block bb)
{
- gcc_assert (df->problems_by_index[DF_LR]);
+ gcc_assert (df_lr);
- if (df->problems_by_index[DF_UREC])
- return DF_RA_LIVE_IN (df, bb);
- else if (df->problems_by_index[DF_UR])
- return DF_LIVE_IN (df, bb);
+ if (df_urec)
+ return DF_RA_LIVE_IN (bb);
+ else if (df_live)
+ return DF_LIVE_IN (bb);
else
- return DF_UPWARD_LIVE_IN (df, bb);
+ return DF_LR_IN (bb);
}
-
-/* Get the live out set for BB no matter what problem happens to be
- defined. */
+/* Get the live at top set for BB no matter what problem happens to be
+ defined. This function is used by the register allocators who
+ choose different dataflow problems depending on the optimization
+ level. */
bitmap
-df_get_live_out (struct df *df, basic_block bb)
+df_get_live_top (basic_block bb)
{
- gcc_assert (df->problems_by_index[DF_LR]);
+ gcc_assert (df_lr);
- if (df->problems_by_index[DF_UREC])
- return DF_RA_LIVE_OUT (df, bb);
- else if (df->problems_by_index[DF_UR])
- return DF_LIVE_OUT (df, bb);
+ if (df_urec)
+ return DF_RA_LIVE_TOP (bb);
else
- return DF_UPWARD_LIVE_OUT (df, bb);
+ return DF_LR_TOP (bb);
}
----------------------------------------------------------------------------*/
/* Generic versions to get the void* version of the block info. Only
- used inside the problem instace vectors. */
+ used inside the problem instance vectors. */
/* Grow the bb_info array. */
/* Dump a def-use or use-def chain for REF to FILE. */
void
-df_chain_dump (struct df *df ATTRIBUTE_UNUSED, struct df_link *link, FILE *file)
+df_chain_dump (struct df_link *link, FILE *file)
{
fprintf (file, "{ ");
for (; link; link = link->next)
edge e;
edge_iterator ei;
- fprintf (file, "( ");
+ fprintf (file, "\n( ");
FOR_EACH_EDGE (e, ei, bb->preds)
{
basic_block pred = e->src;
- fprintf (file, "%d ", pred->index);
+ fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : "");
}
fprintf (file, ")->[%d]->( ", bb->index);
FOR_EACH_EDGE (e, ei, bb->succs)
{
basic_block succ = e->dest;
- fprintf (file, "%d ", succ->index);
+ fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : "");
}
fprintf (file, ")\n");
}
-/* Return the set of reference ids in CHAIN, caching the result in *BMAP. */
-
-static inline bitmap
-df_ref_bitmap (bitmap *maps, unsigned int regno, int start, int count)
-{
- bitmap ids = maps[regno];
- if (!ids)
- {
- unsigned int i;
- unsigned int end = start + count;;
- ids = BITMAP_ALLOC (NULL);
- maps[regno] = ids;
- for (i = start; i < end; i++)
- bitmap_set_bit (ids, i);
- }
- 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);
+ seen_in_block = BITMAP_ALLOC (&df_bitmap_obstack);
+ seen_in_insn = BITMAP_ALLOC (&df_bitmap_obstack);
}
REACHING USES
Find the locations in the function where each use site for a pseudo
- can reach backwards.
+ 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.
+
+ <= : Data is built directly in the kill set.
+
+ > : One level of indirection is used to keep from generating long
+ strings of 1 bits in the kill sets. Bitvectors that are indexed
+ by the regnum are used to represent that there is a killing def
+ for the register. The confluence and transfer functions use
+ these along with the bitmap_clear_range call to remove ranges of
+ bits without actually generating a knockout vector.
+
+ 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 invalidate by call for ru. */
- bitmap dense_invalidated_by_call;
+ /* The set of defs to regs invalidated by call for ru. */
+ bitmap dense_invalidated_by_call;
+ /* An obstack for the bitmaps we need for this problem. */
+ bitmap_obstack ru_bitmaps;
};
-/* 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)
+df_ru_set_bb_info (unsigned int index, struct df_ru_bb_info *bb_info)
{
- dflow->block_info[index] = bb_info;
+ gcc_assert (df_ru);
+ gcc_assert (index < df_ru->block_info_size);
+ df_ru->block_info[index] = bb_info;
}
/* Free basic block info. */
static void
-df_ru_free_bb_info (struct dataflow *dflow, void *vbb_info)
+df_ru_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
+ void *vbb_info)
{
struct df_ru_bb_info *bb_info = (struct df_ru_bb_info *) vbb_info;
if (bb_info)
BITMAP_FREE (bb_info->gen);
BITMAP_FREE (bb_info->in);
BITMAP_FREE (bb_info->out);
- pool_free (dflow->block_pool, bb_info);
+ pool_free (df_ru->block_pool, bb_info);
}
}
-/* Allocate or reset bitmaps for DFLOW blocks. The solution bits are
+/* Allocate or reset bitmaps for DF_RU blocks. The solution bits are
not touched unless the block is new. */
static void
-df_ru_alloc (struct dataflow *dflow, bitmap blocks_to_rescan)
+df_ru_alloc (bitmap all_blocks)
{
unsigned int bb_index;
bitmap_iterator bi;
- unsigned int reg_size = max_reg_num ();
+ struct df_ru_problem_data *problem_data;
- if (! dflow->block_pool)
- dflow->block_pool = create_alloc_pool ("df_ru_block pool",
+ if (!df_ru->block_pool)
+ df_ru->block_pool = create_alloc_pool ("df_ru_block pool",
sizeof (struct df_ru_bb_info), 50);
- if (dflow->problem_data)
+ if (df_ru->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;
- }
-
+ problem_data = (struct df_ru_problem_data *) df_ru->problem_data;
bitmap_clear (problem_data->sparse_invalidated_by_call);
bitmap_clear (problem_data->dense_invalidated_by_call);
}
else
{
- struct df_ru_problem_data *problem_data =
- xmalloc (sizeof (struct df_ru_problem_data));
- dflow->problem_data = problem_data;
-
- problem_data->use_sites = xcalloc (reg_size, sizeof (bitmap));
- problem_data->use_sites_size = reg_size;
- problem_data->sparse_invalidated_by_call = BITMAP_ALLOC (NULL);
- problem_data->dense_invalidated_by_call = BITMAP_ALLOC (NULL);
+ problem_data = XNEW (struct df_ru_problem_data);
+ df_ru->problem_data = problem_data;
+
+ bitmap_obstack_initialize (&problem_data->ru_bitmaps);
+ problem_data->sparse_invalidated_by_call
+ = BITMAP_ALLOC (&problem_data->ru_bitmaps);
+ problem_data->dense_invalidated_by_call
+ = BITMAP_ALLOC (&problem_data->ru_bitmaps);
}
- df_grow_bb_info (dflow);
+ df_grow_bb_info (df_ru);
/* Because of the clustering of all def sites for the same pseudo,
we have to process all of the blocks before doing the
analysis. */
- EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi)
+ EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
- struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb_index);
+ struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb_index);
if (bb_info)
{
bitmap_clear (bb_info->kill);
}
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);
+ bb_info = (struct df_ru_bb_info *) pool_alloc (df_ru->block_pool);
+ df_ru_set_bb_info (bb_index, bb_info);
+ bb_info->kill = BITMAP_ALLOC (&problem_data->ru_bitmaps);
+ bb_info->sparse_kill = BITMAP_ALLOC (&problem_data->ru_bitmaps);
+ bb_info->gen = BITMAP_ALLOC (&problem_data->ru_bitmaps);
+ bb_info->in = BITMAP_ALLOC (&problem_data->ru_bitmaps);
+ bb_info->out = BITMAP_ALLOC (&problem_data->ru_bitmaps);
}
}
+ df_ru->optional_p = true;
}
/* 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)
+df_ru_bb_local_compute_process_def (struct df_ru_bb_info *bb_info,
+ struct df_ref **def_rec,
+ enum df_ref_flags top_flag)
{
- struct df *df = dflow->df;
- while (def)
+ while (*def_rec)
{
- unsigned int regno = DF_REF_REGNO (def);
- unsigned int begin = DF_REG_USE_GET (df, regno)->begin;
- unsigned int n_uses = DF_REG_USE_GET (df, regno)->n_refs;
- if (!bitmap_bit_p (seen_in_block, regno))
+ struct df_ref *def = *def_rec;
+ 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 | DF_REF_CONDITIONAL))))
{
- /* The first def for regno, causes the kill info to be
- generated and the gen information to cleared. */
- if (!bitmap_bit_p (seen_in_insn, regno))
+ unsigned int regno = DF_REF_REGNO (def);
+ unsigned int begin = DF_USES_BEGIN (regno);
+ unsigned int n_uses = DF_USES_COUNT (regno);
+
+ if (!bitmap_bit_p (seen_in_block, regno))
{
- if (n_uses > DF_SPARSE_THRESHOLD)
- {
- bitmap_set_bit (bb_info->sparse_kill, regno);
- bitmap_clear_range (bb_info->gen, begin, n_uses);
- }
- else
+ /* 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))
{
- struct df_ru_problem_data *problem_data =
- (struct df_ru_problem_data *) dflow->problem_data;
- bitmap uses =
- df_ref_bitmap (problem_data->use_sites, regno,
- begin, n_uses);
- bitmap_ior_into (bb_info->kill, uses);
- bitmap_and_compl_into (bb_info->gen, uses);
+ if (n_uses > DF_SPARSE_THRESHOLD)
+ bitmap_set_bit (bb_info->sparse_kill, regno);
+ else
+ bitmap_set_range (bb_info->kill, begin, n_uses);
}
+ bitmap_set_bit (seen_in_insn, regno);
}
- bitmap_set_bit (seen_in_insn, regno);
}
- def = def->next_ref;
+ def_rec++;
}
}
static void
df_ru_bb_local_compute_process_use (struct df_ru_bb_info *bb_info,
- struct df_ref *use,
+ struct df_ref **use_rec,
enum df_ref_flags top_flag)
{
- while (use)
+ while (*use_rec)
{
+ struct df_ref *use = *use_rec;
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
if (!bitmap_bit_p (seen_in_block, regno))
bitmap_set_bit (bb_info->gen, DF_REF_ID (use));
}
- use = use->next_ref;
+ use_rec++;
}
}
/* Compute local reaching use (upward exposed use) info for basic
block BB. USE_INFO->REGS[R] caches the set of uses for register R. */
static void
-df_ru_bb_local_compute (struct dataflow *dflow, unsigned int bb_index)
+df_ru_bb_local_compute (unsigned int bb_index)
{
- struct df *df = dflow->df;
basic_block bb = BASIC_BLOCK (bb_index);
- struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb_index);
+ struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb_index);
rtx insn;
/* Set when a def for regno is seen. */
/* 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_get_artificial_uses (bb_index),
DF_REF_AT_TOP);
#endif
-
- /* Process the artificial defs first since these are at the top of
- the block. */
- df_ru_bb_local_compute_process_def (dflow, bb_info,
- df_get_artificial_defs (df, bb_index));
+ df_ru_bb_local_compute_process_def (bb_info,
+ df_get_artificial_defs (bb_index),
+ DF_REF_AT_TOP);
FOR_BB_INSNS (bb, insn)
{
unsigned int uid = INSN_UID (insn);
- if (! INSN_P (insn))
+ if (!INSN_P (insn))
continue;
- df_ru_bb_local_compute_process_def (dflow, bb_info,
- DF_INSN_UID_GET (df, uid)->defs);
-
- /* The use processing must happen after the defs processing even
- though the uses logically happen first since the defs clear
- the gen set. Otherwise, a use for regno occuring in the same
- instruction as a def for regno would be cleared. */
df_ru_bb_local_compute_process_use (bb_info,
- DF_INSN_UID_GET (df, uid)->uses, 0);
+ DF_INSN_UID_USES (uid), 0);
+
+ if (df->changeable_flags & DF_EQ_NOTES)
+ df_ru_bb_local_compute_process_use (bb_info,
+ DF_INSN_UID_EQ_USES (uid), 0);
+
+ df_ru_bb_local_compute_process_def (bb_info,
+ DF_INSN_UID_DEFS (uid), 0);
bitmap_ior_into (seen_in_block, seen_in_insn);
bitmap_clear (seen_in_insn);
/* 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_get_artificial_uses (bb_index), 0);
+
+ df_ru_bb_local_compute_process_def (bb_info,
+ df_get_artificial_defs (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)
+df_ru_local_compute (bitmap all_blocks)
{
- struct df *df = dflow->df;
unsigned int bb_index;
bitmap_iterator bi;
unsigned int regno;
- struct df_ru_problem_data *problem_data =
- (struct df_ru_problem_data *) dflow->problem_data;
+ struct df_ru_problem_data *problem_data
+ = (struct df_ru_problem_data *) df_ru->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);
+ df_maybe_reorganize_use_refs (df->changeable_flags & DF_EQ_NOTES ?
+ DF_REF_ORDER_BY_REG_WITH_NOTES : DF_REF_ORDER_BY_REG);
EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
- df_ru_bb_local_compute (dflow, bb_index);
+ df_ru_bb_local_compute (bb_index);
}
/* Set up the knockout bit vectors to be applied across EH_EDGES. */
EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi)
{
- struct df_reg_info *reg_info = DF_REG_USE_GET (df, regno);
- if (reg_info->n_refs > DF_SPARSE_THRESHOLD)
+ if (DF_USES_COUNT (regno) > DF_SPARSE_THRESHOLD)
bitmap_set_bit (sparse_invalidated, regno);
else
- {
- bitmap defs = df_ref_bitmap (problem_data->use_sites, regno,
- reg_info->begin, reg_info->n_refs);
- bitmap_ior_into (dense_invalidated, defs);
- }
+ bitmap_set_range (dense_invalidated,
+ DF_USES_BEGIN (regno),
+ DF_USES_COUNT (regno));
}
df_unset_seen ();
/* Initialize the solution bit vectors for problem. */
static void
-df_ru_init_solution (struct dataflow *dflow, bitmap all_blocks)
+df_ru_init_solution (bitmap all_blocks)
{
unsigned int bb_index;
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
- struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb_index);
+ struct df_ru_bb_info *bb_info = df_ru_get_bb_info (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)
+df_ru_confluence_n (edge e)
{
- bitmap op1 = df_ru_get_bb_info (dflow, e->src->index)->out;
- bitmap op2 = df_ru_get_bb_info (dflow, e->dest->index)->in;
+ bitmap op1 = df_ru_get_bb_info (e->src->index)->out;
+ bitmap op2 = df_ru_get_bb_info (e->dest->index)->in;
if (e->flags & EDGE_EH)
{
- struct df_ru_problem_data *problem_data =
- (struct df_ru_problem_data *) dflow->problem_data;
+ struct df_ru_problem_data *problem_data
+ = (struct df_ru_problem_data *) df_ru->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_ior_and_compl_into (op1, op2, dense_invalidated);
+ bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
+
+ bitmap_copy (tmp, op2);
+ bitmap_and_compl_into (tmp, dense_invalidated);
+
EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
{
- bitmap_clear_range (op1,
- DF_REG_USE_GET (df, regno)->begin,
- DF_REG_USE_GET (df, regno)->n_refs);
+ bitmap_clear_range (tmp,
+ DF_USES_BEGIN (regno),
+ DF_USES_COUNT (regno));
}
+ 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)
+df_ru_transfer_function (int bb_index)
{
- struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb_index);
+ struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb_index);
unsigned int regno;
bitmap_iterator bi;
bitmap in = bb_info->in;
return bitmap_ior_and_compl (in, gen, out, kill);
else
{
- struct df *df = dflow->df;
+ struct df_ru_problem_data *problem_data;
+ bitmap tmp;
bool changed = false;
- bitmap tmp = BITMAP_ALLOC (NULL);
- bitmap_copy (tmp, in);
+
+ /* Note that TMP is _not_ a temporary bitmap if we end up replacing
+ IN with TMP. Therefore, allocate TMP in the RU bitmaps obstack. */
+ problem_data = (struct df_ru_problem_data *) df_ru->problem_data;
+ tmp = BITMAP_ALLOC (&problem_data->ru_bitmaps);
+
+ 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);
+ DF_USES_BEGIN (regno),
+ DF_USES_COUNT (regno));
}
bitmap_and_compl_into (tmp, kill);
bitmap_ior_into (tmp, gen);
- changed = !bitmap_equal_p (tmp, out);
+ changed = !bitmap_equal_p (tmp, in);
if (changed)
{
- BITMAP_FREE (out);
+ BITMAP_FREE (in);
bb_info->in = tmp;
}
else
/* Free all storage associated with the problem. */
static void
-df_ru_free (struct dataflow *dflow)
+df_ru_free (void)
{
unsigned int i;
- struct df_ru_problem_data *problem_data =
- (struct df_ru_problem_data *) dflow->problem_data;
+ struct df_ru_problem_data *problem_data
+ = (struct df_ru_problem_data *) df_ru->problem_data;
- for (i = 0; i < dflow->block_info_size; i++)
+ if (problem_data)
{
- struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, i);
- if (bb_info)
+ for (i = 0; i < df_ru->block_info_size; i++)
{
- 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);
+ struct df_ru_bb_info *bb_info = df_ru_get_bb_info (i);
+ if (bb_info)
+ {
+ BITMAP_FREE (bb_info->kill);
+ BITMAP_FREE (bb_info->sparse_kill);
+ BITMAP_FREE (bb_info->gen);
+ BITMAP_FREE (bb_info->in);
+ BITMAP_FREE (bb_info->out);
+ }
}
+
+ free_alloc_pool (df_ru->block_pool);
+ BITMAP_FREE (problem_data->sparse_invalidated_by_call);
+ BITMAP_FREE (problem_data->dense_invalidated_by_call);
+ bitmap_obstack_release (&problem_data->ru_bitmaps);
+
+ df_ru->block_info_size = 0;
+ free (df_ru->block_info);
+ free (df_ru->problem_data);
}
-
- 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);
+ free (df_ru);
}
/* Debugging info. */
static void
-df_ru_dump (struct dataflow *dflow, FILE *file)
+df_ru_start_dump (FILE *file)
{
- basic_block bb;
- struct df *df = dflow->df;
- struct df_ru_problem_data *problem_data =
- (struct df_ru_problem_data *) dflow->problem_data;
- unsigned int m = max_reg_num ();
+ struct df_ru_problem_data *problem_data
+ = (struct df_ru_problem_data *) df_ru->problem_data;
+ unsigned int m = DF_REG_SIZE(df);
unsigned int regno;
+
+ if (!df_ru->block_info)
+ return;
- fprintf (file, "Reaching uses:\n");
+ fprintf (file, ";; Reaching uses:\n");
- fprintf (file, " sparse invalidated \t");
+ fprintf (file, ";; sparse invalidated \t");
dump_bitmap (file, problem_data->sparse_invalidated_by_call);
- fprintf (file, " dense invalidated \t");
+ 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)
+ if (DF_USES_COUNT (regno))
fprintf (file, "%d[%d,%d] ", regno,
- DF_REG_USE_GET (df, regno)->begin,
- DF_REG_USE_GET (df, regno)->n_refs);
+ DF_USES_BEGIN (regno),
+ DF_USES_COUNT (regno));
fprintf (file, "\n");
-
- FOR_ALL_BB (bb)
- {
- struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb->index);
- df_print_bb_index (bb, file);
-
- if (! bb_info->in)
- continue;
-
- fprintf (file, " in \t");
- dump_bitmap (file, bb_info->in);
- fprintf (file, " gen \t");
- dump_bitmap (file, bb_info->gen);
- fprintf (file, " kill\t");
- dump_bitmap (file, bb_info->kill);
- fprintf (file, " out \t");
- dump_bitmap (file, bb_info->out);
- }
}
+
+/* Debugging info at top of bb. */
+
+static void
+df_ru_top_dump (basic_block bb, FILE *file)
+{
+ struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb->index);
+ if (!bb_info || !bb_info->in)
+ return;
+
+ fprintf (file, ";; ru in \t(%d)\n", (int) bitmap_count_bits (bb_info->in));
+ dump_bitmap (file, bb_info->in);
+ fprintf (file, ";; ru gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen));
+ dump_bitmap (file, bb_info->gen);
+ fprintf (file, ";; ru kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill));
+ dump_bitmap (file, bb_info->kill);
+}
+
+
+/* Debugging info at bottom of bb. */
+
+static void
+df_ru_bottom_dump (basic_block bb, FILE *file)
+{
+ struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb->index);
+ if (!bb_info || !bb_info->out)
+ return;
+
+ fprintf (file, ";; ru 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. */
+ df_worklist_dataflow, /* Worklist 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. */
+ df_ru_free, /* Remove this problem from the stack of dataflow problems. */
+ df_ru_start_dump, /* Debugging. */
+ df_ru_top_dump, /* Debugging start block. */
+ df_ru_bottom_dump, /* Debugging end block. */
+ NULL, /* Incremental solution verify start. */
+ NULL, /* Incremental solution verify end. */
+ NULL, /* Dependent problem. */
+ TV_DF_RU, /* Timing variable. */
+ true /* Reset blocks on dropping out of blocks_to_analyze. */
};
of DF. The returned structure is what is used to get at the
solution. */
-struct dataflow *
-df_ru_add_problem (struct df *df)
+void
+df_ru_add_problem (void)
{
- return df_add_problem (df, &problem_RU);
+ df_add_problem (&problem_RU);
}
\f
REACHING DEFINITIONS
Find the locations in the function where each definition site for a
- pseudo reaches.
-----------------------------------------------------------------------------*/
+ 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
{
- bitmap *def_sites; /* Bitmap of defs for each pseudo. */
- unsigned int def_sites_size; /* Size of def_sites. */
/* The set of defs to regs invalidated by call. */
bitmap sparse_invalidated_by_call;
- /* The set of defs to regs invalidate by call for ru. */
- bitmap dense_invalidated_by_call;
+ /* The set of defs to regs invalidate by call for rd. */
+ bitmap dense_invalidated_by_call;
+ /* An obstack for the bitmaps we need for this problem. */
+ bitmap_obstack rd_bitmaps;
};
-/* 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,
+df_rd_set_bb_info (unsigned int index,
struct df_rd_bb_info *bb_info)
{
- dflow->block_info[index] = bb_info;
+ gcc_assert (df_rd);
+ gcc_assert (index < df_rd->block_info_size);
+ df_rd->block_info[index] = bb_info;
}
/* Free basic block info. */
static void
-df_rd_free_bb_info (struct dataflow *dflow, void *vbb_info)
+df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
+ void *vbb_info)
{
struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info;
if (bb_info)
BITMAP_FREE (bb_info->gen);
BITMAP_FREE (bb_info->in);
BITMAP_FREE (bb_info->out);
- pool_free (dflow->block_pool, bb_info);
+ pool_free (df_rd->block_pool, bb_info);
}
}
-/* Allocate or reset bitmaps for DFLOW blocks. The solution bits are
+/* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
not touched unless the block is new. */
static void
-df_rd_alloc (struct dataflow *dflow, bitmap blocks_to_rescan)
+df_rd_alloc (bitmap all_blocks)
{
unsigned int bb_index;
bitmap_iterator bi;
- unsigned int reg_size = max_reg_num ();
+ struct df_rd_problem_data *problem_data;
- if (! dflow->block_pool)
- dflow->block_pool = create_alloc_pool ("df_rd_block pool",
+ if (!df_rd->block_pool)
+ df_rd->block_pool = create_alloc_pool ("df_rd_block pool",
sizeof (struct df_rd_bb_info), 50);
- if (dflow->problem_data)
+ if (df_rd->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;
- }
-
+ problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
bitmap_clear (problem_data->sparse_invalidated_by_call);
bitmap_clear (problem_data->dense_invalidated_by_call);
}
else
{
- struct df_rd_problem_data *problem_data =
- xmalloc (sizeof (struct df_rd_problem_data));
- dflow->problem_data = problem_data;
-
- problem_data->def_sites = xcalloc (reg_size, sizeof (bitmap));
- problem_data->def_sites_size = reg_size;
- problem_data->sparse_invalidated_by_call = BITMAP_ALLOC (NULL);
- problem_data->dense_invalidated_by_call = BITMAP_ALLOC (NULL);
+ problem_data = XNEW (struct df_rd_problem_data);
+ df_rd->problem_data = problem_data;
+
+ bitmap_obstack_initialize (&problem_data->rd_bitmaps);
+ problem_data->sparse_invalidated_by_call
+ = BITMAP_ALLOC (&problem_data->rd_bitmaps);
+ problem_data->dense_invalidated_by_call
+ = BITMAP_ALLOC (&problem_data->rd_bitmaps);
}
- df_grow_bb_info (dflow);
+ df_grow_bb_info (df_rd);
- /* Because of the clustering of all def sites for the same pseudo,
+ /* Because of the clustering of all use sites for the same pseudo,
we have to process all of the blocks before doing the
analysis. */
- EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi)
+ EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
- struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb_index);
+ struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
if (bb_info)
{
bitmap_clear (bb_info->kill);
}
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);
+ bb_info = (struct df_rd_bb_info *) pool_alloc (df_rd->block_pool);
+ df_rd_set_bb_info (bb_index, bb_info);
+ bb_info->kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
+ bb_info->sparse_kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
+ bb_info->gen = BITMAP_ALLOC (&problem_data->rd_bitmaps);
+ bb_info->in = BITMAP_ALLOC (&problem_data->rd_bitmaps);
+ bb_info->out = BITMAP_ALLOC (&problem_data->rd_bitmaps);
}
}
+ df_rd->optional_p = true;
}
/* 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)
+df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info,
+ struct df_ref **def_rec,
+ enum df_ref_flags top_flag)
{
- struct df *df = dflow->df;
- while (def)
+ while (*def_rec)
{
- 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))
+ struct df_ref *def = *def_rec;
+ if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
{
- /* The first def for regno in insn gets to knock out the
- defs from other instructions. */
- if (!bitmap_bit_p (seen_in_insn, regno))
+ unsigned int regno = DF_REF_REGNO (def);
+ unsigned int begin = DF_DEFS_BEGIN (regno);
+ unsigned int n_defs = DF_DEFS_COUNT (regno);
+
+ if ((!(df->changeable_flags & DF_NO_HARD_REGS))
+ || (regno >= FIRST_PSEUDO_REGISTER))
{
- if (n_defs > DF_SPARSE_THRESHOLD)
+ /* Only the last def(s) for a regno in the block has any
+ effect. */
+ if (!bitmap_bit_p (seen_in_block, regno))
{
- 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);
+ /* The first def for regno in insn gets to knock out the
+ defs from other instructions. */
+ if ((!bitmap_bit_p (seen_in_insn, regno))
+ /* If the def is to only part of the reg, it does
+ not kill the other defs that reach here. */
+ && (!(DF_REF_FLAGS (def) &
+ (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
+ {
+ if (n_defs > DF_SPARSE_THRESHOLD)
+ {
+ bitmap_set_bit (bb_info->sparse_kill, regno);
+ bitmap_clear_range(bb_info->gen, begin, n_defs);
+ }
+ else
+ {
+ bitmap_set_range (bb_info->kill, begin, n_defs);
+ bitmap_clear_range (bb_info->gen, begin, n_defs);
+ }
+ }
+
+ bitmap_set_bit (seen_in_insn, regno);
+ /* All defs for regno in the instruction may be put into
+ the gen set. */
+ if (!(DF_REF_FLAGS (def)
+ & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
+ bitmap_set_bit (bb_info->gen, DF_REF_ID (def));
}
}
-
- bitmap_set_bit (seen_in_insn, regno);
- /* All defs for regno in the instruction may be put into
- the gen set. */
- if (! (DF_REF_FLAGS (def) & DF_REF_CLOBBER))
- bitmap_set_bit (bb_info->gen, DF_REF_ID (def));
}
- def = def->next_ref;
+ def_rec++;
}
}
/* Compute local reaching def info for basic block BB. */
static void
-df_rd_bb_local_compute (struct dataflow *dflow, unsigned int bb_index)
+df_rd_bb_local_compute (unsigned int bb_index)
{
- struct df *df = dflow->df;
basic_block bb = BASIC_BLOCK (bb_index);
- struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb_index);
+ struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
rtx insn;
bitmap_clear (seen_in_block);
bitmap_clear (seen_in_insn);
+ /* Artificials are only hard regs. */
+ if (!(df->changeable_flags & DF_NO_HARD_REGS))
+ df_rd_bb_local_compute_process_def (bb_info,
+ df_get_artificial_defs (bb_index),
+ 0);
+
FOR_BB_INSNS_REVERSE (bb, insn)
{
unsigned int uid = INSN_UID (insn);
- if (! INSN_P (insn))
+ if (!INSN_P (insn))
continue;
- df_rd_bb_local_compute_process_def (dflow, bb_info,
- DF_INSN_UID_GET (df, uid)->defs);
+ df_rd_bb_local_compute_process_def (bb_info,
+ DF_INSN_UID_DEFS (uid), 0);
/* This complex dance with the two bitmaps is required because
instructions can assign twice to the same pseudo. This
bitmap_clear (seen_in_insn);
}
- /* Process the artificial defs last since we are going backwards
- thur the block and these are logically at the start. */
- df_rd_bb_local_compute_process_def (dflow, bb_info,
- df_get_artificial_defs (df, bb_index));
+ /* Process the artificial defs at the top of the block last since we
+ are going backwards through the block and these are logically at
+ the start. */
+ if (!(df->changeable_flags & DF_NO_HARD_REGS))
+ df_rd_bb_local_compute_process_def (bb_info,
+ df_get_artificial_defs (bb_index),
+ DF_REF_AT_TOP);
}
/* Compute local reaching 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)
+df_rd_local_compute (bitmap all_blocks)
{
- 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;
+ struct df_rd_problem_data *problem_data
+ = (struct df_rd_problem_data *) df_rd->problem_data;
bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
df_set_seen ();
- if (!df->def_info.refs_organized)
- df_reorganize_refs (&df->def_info);
+ df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
- df_rd_bb_local_compute (dflow, bb_index);
+ df_rd_bb_local_compute (bb_index);
}
/* Set up the knockout bit vectors to be applied across EH_EDGES. */
EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi)
{
- 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);
- }
+ if (DF_DEFS_COUNT (regno) > 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);
- }
+ bitmap_set_range (dense_invalidated,
+ DF_DEFS_BEGIN (regno),
+ DF_DEFS_COUNT (regno));
}
df_unset_seen ();
}
/* Initialize the solution bit vectors for problem. */
static void
-df_rd_init_solution (struct dataflow *dflow, bitmap all_blocks)
+df_rd_init_solution (bitmap all_blocks)
{
unsigned int bb_index;
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
- struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb_index);
+ struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
bitmap_copy (bb_info->out, bb_info->gen);
bitmap_clear (bb_info->in);
/* In of target gets or of out of source. */
static void
-df_rd_confluence_n (struct dataflow *dflow, edge e)
+df_rd_confluence_n (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;
+ bitmap op1 = df_rd_get_bb_info (e->dest->index)->in;
+ bitmap op2 = df_rd_get_bb_info (e->src->index)->out;
if (e->flags & EDGE_EH)
{
- struct df_rd_problem_data *problem_data =
- (struct df_rd_problem_data *) dflow->problem_data;
+ struct df_rd_problem_data *problem_data
+ = (struct df_rd_problem_data *) df_rd->problem_data;
bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
- struct df *df = dflow->df;
bitmap_iterator bi;
unsigned int regno;
- bitmap_ior_and_compl_into (op1, op2, dense_invalidated);
+ bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
+
+ bitmap_copy (tmp, op2);
+ bitmap_and_compl_into (tmp, dense_invalidated);
+
EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
{
- bitmap_clear_range (op1,
- DF_REG_DEF_GET (df, regno)->begin,
- DF_REG_DEF_GET (df, regno)->n_refs);
+ bitmap_clear_range (tmp,
+ DF_DEFS_BEGIN (regno),
+ DF_DEFS_COUNT (regno));
}
+ bitmap_ior_into (op1, tmp);
+ BITMAP_FREE (tmp);
}
else
bitmap_ior_into (op1, op2);
/* Transfer function. */
static bool
-df_rd_transfer_function (struct dataflow *dflow, int bb_index)
+df_rd_transfer_function (int bb_index)
{
- struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb_index);
+ struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
unsigned int regno;
bitmap_iterator bi;
bitmap in = bb_info->in;
return bitmap_ior_and_compl (out, gen, in, kill);
else
{
- struct df *df = dflow->df;
+ struct df_rd_problem_data *problem_data;
bool changed = false;
- bitmap tmp = BITMAP_ALLOC (NULL);
+ bitmap tmp;
+
+ /* Note that TMP is _not_ a temporary bitmap if we end up replacing
+ OUT with TMP. Therefore, allocate TMP in the RD bitmaps obstack. */
+ problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
+ tmp = BITMAP_ALLOC (&problem_data->rd_bitmaps);
+
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);
+ DF_DEFS_BEGIN (regno),
+ DF_DEFS_COUNT (regno));
}
bitmap_and_compl_into (tmp, kill);
bitmap_ior_into (tmp, gen);
/* Free all storage associated with the problem. */
static void
-df_rd_free (struct dataflow *dflow)
+df_rd_free (void)
{
unsigned int i;
- struct df_rd_problem_data *problem_data =
- (struct df_rd_problem_data *) dflow->problem_data;
+ struct df_rd_problem_data *problem_data
+ = (struct df_rd_problem_data *) df_rd->problem_data;
- for (i = 0; i < dflow->block_info_size; i++)
+ if (problem_data)
{
- struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, i);
- if (bb_info)
+ for (i = 0; i < df_rd->block_info_size; i++)
{
- 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);
+ struct df_rd_bb_info *bb_info = df_rd_get_bb_info (i);
+ if (bb_info)
+ {
+ BITMAP_FREE (bb_info->kill);
+ BITMAP_FREE (bb_info->sparse_kill);
+ BITMAP_FREE (bb_info->gen);
+ BITMAP_FREE (bb_info->in);
+ BITMAP_FREE (bb_info->out);
+ }
}
+
+ free_alloc_pool (df_rd->block_pool);
+ BITMAP_FREE (problem_data->sparse_invalidated_by_call);
+ BITMAP_FREE (problem_data->dense_invalidated_by_call);
+ bitmap_obstack_release (&problem_data->rd_bitmaps);
+
+ df_rd->block_info_size = 0;
+ free (df_rd->block_info);
+ free (df_rd->problem_data);
}
-
- 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);
+ free (df_rd);
}
/* Debugging info. */
static void
-df_rd_dump (struct dataflow *dflow, FILE *file)
+df_rd_start_dump (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 ();
+ struct df_rd_problem_data *problem_data
+ = (struct df_rd_problem_data *) df_rd->problem_data;
+ unsigned int m = DF_REG_SIZE(df);
unsigned int regno;
- fprintf (file, "Reaching defs:\n\n");
+ if (!df_rd->block_info)
+ return;
+
+ fprintf (file, ";; Reaching defs:\n\n");
fprintf (file, " sparse invalidated \t");
dump_bitmap (file, problem_data->sparse_invalidated_by_call);
dump_bitmap (file, problem_data->dense_invalidated_by_call);
for (regno = 0; regno < m; regno++)
- if (DF_REG_DEF_GET (df, regno)->n_refs)
+ if (DF_DEFS_COUNT (regno))
fprintf (file, "%d[%d,%d] ", regno,
- DF_REG_DEF_GET (df, regno)->begin,
- DF_REG_DEF_GET (df, regno)->n_refs);
+ DF_DEFS_BEGIN (regno),
+ DF_DEFS_COUNT (regno));
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);
- }
+}
+
+
+/* Debugging info at top of bb. */
+
+static void
+df_rd_top_dump (basic_block bb, FILE *file)
+{
+ struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
+ if (!bb_info || !bb_info->in)
+ return;
+
+ fprintf (file, ";; rd in \t(%d)\n", (int) bitmap_count_bits (bb_info->in));
+ dump_bitmap (file, bb_info->in);
+ fprintf (file, ";; rd gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen));
+ dump_bitmap (file, bb_info->gen);
+ fprintf (file, ";; rd kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill));
+ dump_bitmap (file, bb_info->kill);
+}
+
+
+/* Debugging info at top of bb. */
+
+static void
+df_rd_bottom_dump (basic_block bb, FILE *file)
+{
+ struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
+ if (!bb_info || !bb_info->out)
+ return;
+
+ fprintf (file, ";; rd 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. */
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. */
+ df_worklist_dataflow, /* Worklist solver. */
NULL, /* Confluence operator 0. */
df_rd_confluence_n, /* Confluence operator n. */
df_rd_transfer_function, /* Transfer function. */
NULL, /* Finalize function. */
df_rd_free, /* Free all of the problem information. */
- df_rd_dump, /* Debugging. */
- NULL /* Dependent problem. */
+ df_rd_free, /* Remove this problem from the stack of dataflow problems. */
+ df_rd_start_dump, /* Debugging. */
+ df_rd_top_dump, /* Debugging start block. */
+ df_rd_bottom_dump, /* Debugging end block. */
+ NULL, /* Incremental solution verify start. */
+ NULL, /* Incremental solution verify end. */
+ NULL, /* Dependent problem. */
+ TV_DF_RD, /* Timing variable. */
+ true /* Reset blocks on dropping out of blocks_to_analyze. */
};
of DF. The returned structure is what is used to get at the
solution. */
-struct dataflow *
-df_rd_add_problem (struct df *df)
+void
+df_rd_add_problem (void)
{
- return df_add_problem (df, &problem_RD);
+ df_add_problem (&problem_RD);
}
/*----------------------------------------------------------------------------
LIVE REGISTERS
- Find the locations in the function where any use of a pseudo can reach
- in the backwards direction.
-----------------------------------------------------------------------------*/
-
-/* Get basic block info. */
+ Find the locations in the function where any use of a pseudo can
+ reach in the backwards direction. In and out bitvectors are built
+ for each basic block. The regnum is used to index into these sets.
+ See df.h for details.
+ ----------------------------------------------------------------------------*/
-struct df_lr_bb_info *
-df_lr_get_bb_info (struct dataflow *dflow, unsigned int index)
+/* Private data used to verify the solution for this problem. */
+struct df_lr_problem_data
{
- return (struct df_lr_bb_info *) dflow->block_info[index];
-}
+ bitmap *in;
+ bitmap *out;
+};
/* Set basic block info. */
static void
-df_lr_set_bb_info (struct dataflow *dflow, unsigned int index,
+df_lr_set_bb_info (unsigned int index,
struct df_lr_bb_info *bb_info)
{
- dflow->block_info[index] = bb_info;
+ gcc_assert (df_lr);
+ gcc_assert (index < df_lr->block_info_size);
+ df_lr->block_info[index] = bb_info;
}
/* Free basic block info. */
static void
-df_lr_free_bb_info (struct dataflow *dflow, void *vbb_info)
+df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
+ void *vbb_info)
{
struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info;
if (bb_info)
{
BITMAP_FREE (bb_info->use);
BITMAP_FREE (bb_info->def);
+ if (bb_info->in == bb_info->top)
+ bb_info->top = NULL;
+ else
+ {
+ BITMAP_FREE (bb_info->top);
+ BITMAP_FREE (bb_info->ause);
+ BITMAP_FREE (bb_info->adef);
+ }
BITMAP_FREE (bb_info->in);
BITMAP_FREE (bb_info->out);
- pool_free (dflow->block_pool, bb_info);
+ pool_free (df_lr->block_pool, bb_info);
}
}
-/* Allocate or reset bitmaps for DFLOW blocks. The solution bits are
+/* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
not touched unless the block is new. */
static void
-df_lr_alloc (struct dataflow *dflow, bitmap blocks_to_rescan)
+df_lr_alloc (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",
+ if (!df_lr->block_pool)
+ df_lr->block_pool = create_alloc_pool ("df_lr_block pool",
sizeof (struct df_lr_bb_info), 50);
- df_grow_bb_info (dflow);
-
- /* Because of the clustering of all def sites for the same pseudo,
- we have to process all of the blocks before doing the
- analysis. */
+ df_grow_bb_info (df_lr);
- EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi)
+ EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
{
- struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb_index);
+ struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
if (bb_info)
{
bitmap_clear (bb_info->def);
bitmap_clear (bb_info->use);
+ if (bb_info->adef)
+ {
+ bitmap_clear (bb_info->adef);
+ bitmap_clear (bb_info->ause);
+ }
}
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 = (struct df_lr_bb_info *) pool_alloc (df_lr->block_pool);
+ df_lr_set_bb_info (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);
+ bb_info->top = bb_info->in;
+ bb_info->adef = NULL;
+ bb_info->ause = NULL;
}
}
+
+ df_lr->optional_p = false;
+}
+
+
+/* Reset the global solution for recalculation. */
+
+static void
+df_lr_reset (bitmap all_blocks)
+{
+ unsigned int bb_index;
+ bitmap_iterator bi;
+
+ EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+ {
+ struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
+ gcc_assert (bb_info);
+ bitmap_clear (bb_info->in);
+ bitmap_clear (bb_info->out);
+ bitmap_clear (bb_info->top);
+ }
}
/* 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)
+df_lr_bb_local_compute (unsigned int bb_index)
{
basic_block bb = BASIC_BLOCK (bb_index);
- struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb_index);
+ struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
rtx insn;
- struct df_ref *def;
- struct df_ref *use;
+ struct df_ref **def_rec;
+ struct df_ref **use_rec;
- /* 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));
+ /* Process the registers set in an exception handler. */
+ for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
+ {
+ struct df_ref *def = *def_rec;
+ if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
+ {
+ unsigned int dregno = DF_REF_REGNO (def);
+ bitmap_set_bit (bb_info->def, dregno);
+ bitmap_clear_bit (bb_info->use, dregno);
+ }
+ }
+
+ /* Process the hardware registers that are always live. */
+ for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
+ {
+ struct df_ref *use = *use_rec;
+ /* Add use to set of uses in this BB. */
+ if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
+ bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
+ }
FOR_BB_INSNS_REVERSE (bb, insn)
{
unsigned int uid = INSN_UID (insn);
- if (! INSN_P (insn))
+ if (!INSN_P (insn))
continue;
if (CALL_P (insn))
{
- for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
+ for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
{
+ struct df_ref *def = *def_rec;
unsigned int dregno = DF_REF_REGNO (def);
- if (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 (DF_REF_FLAGS (def) & DF_REF_MUST_CLOBBER)
{
- /* Add def to set of defs in this BB. */
- bitmap_set_bit (bb_info->def, dregno);
- bitmap_clear_bit (bb_info->use, dregno);
+ 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 | DF_REF_CONDITIONAL)))
+ {
+ bitmap_set_bit (bb_info->def, dregno);
+ bitmap_clear_bit (bb_info->use, dregno);
+ }
+ }
}
+ else
+ /* This is the return value. */
+ if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
+ {
+ bitmap_set_bit (bb_info->def, dregno);
+ bitmap_clear_bit (bb_info->use, dregno);
+ }
}
}
else
{
- for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
+ for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
{
- unsigned int dregno = DF_REF_REGNO (def);
-
- if (DF_INSN_CONTAINS_ASM (df, insn)
- && dregno < FIRST_PSEUDO_REGISTER)
+ struct df_ref *def = *def_rec;
+ /* If the def is to only part of the reg, it does
+ not kill the other defs that reach here. */
+ if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
{
- unsigned int 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;
+ unsigned int dregno = DF_REF_REGNO (def);
+ bitmap_set_bit (bb_info->def, dregno);
+ bitmap_clear_bit (bb_info->use, dregno);
}
- /* Add def to set of defs in this BB. */
- bitmap_set_bit (bb_info->def, dregno);
- bitmap_clear_bit (bb_info->use, dregno);
}
}
- for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
- /* Add use to set of uses in this BB. */
- bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
+ for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
+ {
+ struct df_ref *use = *use_rec;
+ /* 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)
+ for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
{
- unsigned int dregno = DF_REF_REGNO (def);
- bitmap_set_bit (bb_info->def, dregno);
- bitmap_clear_bit (bb_info->use, dregno);
+ struct df_ref *def = *def_rec;
+ if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP)
+ && (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))))
+ {
+ unsigned int dregno = DF_REF_REGNO (def);
+ if (bb_info->adef == NULL)
+ {
+ gcc_assert (bb_info->ause == NULL);
+ gcc_assert (bb_info->top == bb_info->in);
+ bb_info->adef = BITMAP_ALLOC (NULL);
+ bb_info->ause = BITMAP_ALLOC (NULL);
+ bb_info->top = BITMAP_ALLOC (NULL);
+ }
+ bitmap_set_bit (bb_info->adef, 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));
+ for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
+ {
+ struct df_ref *use = *use_rec;
+ /* Add use to set of uses in this BB. */
+ if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
+ {
+ if (bb_info->adef == NULL)
+ {
+ gcc_assert (bb_info->ause == NULL);
+ gcc_assert (bb_info->top == bb_info->in);
+ bb_info->adef = BITMAP_ALLOC (NULL);
+ bb_info->ause = BITMAP_ALLOC (NULL);
+ bb_info->top = BITMAP_ALLOC (NULL);
+ }
+ bitmap_set_bit (bb_info->ause, DF_REF_REGNO (use));
+ }
+ }
#endif
+
+ /* If the df_live problem is not defined, such as at -O0 and -O1, we
+ still need to keep the luids up to date. This is normally done
+ in the df_live problem since this problem has a forwards
+ scan. */
+ if (!df_live)
+ df_recompute_luids (bb);
}
+
/* Compute local live register info for each basic block within BLOCKS. */
static void
-df_lr_local_compute (struct dataflow *dflow,
- bitmap all_blocks,
- bitmap rescan_blocks)
+df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
{
- struct df *df = dflow->df;
unsigned int bb_index;
bitmap_iterator bi;
- /* Assume that the stack pointer is unchanging if alloca hasn't
- been used. */
- if (bitmap_equal_p (all_blocks, rescan_blocks))
- memset (regs_asm_clobbered, 0, sizeof (regs_asm_clobbered));
-
bitmap_clear (df->hardware_regs_used);
/* The all-important stack pointer must always be live. */
/* 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)
+ 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, 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)
+ EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
{
if (bb_index == EXIT_BLOCK)
- continue;
- df_lr_bb_local_compute (dflow, df, bb_index);
+ {
+ /* The exit block is special for this problem and its bits are
+ computed from thin air. */
+ struct df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
+ bitmap_copy (bb_info->use, df->exit_block_uses);
+ }
+ else
+ df_lr_bb_local_compute (bb_index);
}
+
+ bitmap_clear (df_lr->out_of_date_transfer_functions);
}
/* Initialize the solution vectors. */
static void
-df_lr_init (struct dataflow *dflow, bitmap all_blocks)
+df_lr_init (bitmap all_blocks)
{
unsigned int bb_index;
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
- struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb_index);
+ struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
bitmap_copy (bb_info->in, bb_info->use);
bitmap_clear (bb_info->out);
}
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)
+df_lr_confluence_0 (basic_block bb)
{
- struct df *df = dflow->df;
-
- bitmap op1 = df_lr_get_bb_info (dflow, bb->index)->out;
+ bitmap op1 = df_lr_get_bb_info (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)
+df_lr_confluence_n (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;
+ bitmap op1 = df_lr_get_bb_info (e->src->index)->out;
+ bitmap op2 = df_lr_get_bb_info (e->dest->index)->in;
/* Call-clobbered registers die across exception and call edges. */
/* ??? Abnormal call edges ignored for the moment, as this gets
else
bitmap_ior_into (op1, op2);
- bitmap_ior_into (op1, dflow->df->hardware_regs_used);
+ bitmap_ior_into (op1, df->hardware_regs_used);
}
/* Transfer function. */
+
static bool
-df_lr_transfer_function (struct dataflow *dflow, int bb_index)
+df_lr_transfer_function (int bb_index)
{
- struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb_index);
+ struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
bitmap in = bb_info->in;
bitmap out = bb_info->out;
bitmap use = bb_info->use;
bitmap def = bb_info->def;
+ bitmap top = bb_info->top;
+ bitmap ause = bb_info->ause;
+ bitmap adef = bb_info->adef;
+ bool changed;
+
+ changed = bitmap_ior_and_compl (top, use, out, def);
+ if (in != top)
+ {
+ gcc_assert (ause && adef);
+ changed |= bitmap_ior_and_compl (in, ause, top, adef);
+ }
+
+ return changed;
+}
+
- return bitmap_ior_and_compl (in, use, out, def);
+/* Run the fast dce as a side effect of building LR. */
+
+static void
+df_lr_local_finalize (bitmap all_blocks ATTRIBUTE_UNUSED)
+{
+ if (df->changeable_flags & DF_LR_RUN_DCE)
+ {
+ run_fast_df_dce ();
+ if (df_lr->problem_data && df_lr->solutions_dirty)
+ {
+ /* If we are here, then it is because we are both verifying
+ the solution and the dce changed the function. In that case
+ the verification info built will be wrong. So we leave the
+ dirty flag true so that the verifier will skip the checking
+ part and just clean up.*/
+ df_lr->solutions_dirty = true;
+ }
+ else
+ df_lr->solutions_dirty = false;
+ }
+ else
+ df_lr->solutions_dirty = false;
}
/* Free all storage associated with the problem. */
static void
-df_lr_free (struct dataflow *dflow)
+df_lr_free (void)
{
- unsigned int i;
- for (i = 0; i < dflow->block_info_size; i++)
+ if (df_lr->block_info)
{
- struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, i);
- if (bb_info)
+ unsigned int i;
+ for (i = 0; i < df_lr->block_info_size; i++)
{
- BITMAP_FREE (bb_info->use);
- BITMAP_FREE (bb_info->def);
- BITMAP_FREE (bb_info->in);
- BITMAP_FREE (bb_info->out);
+ struct df_lr_bb_info *bb_info = df_lr_get_bb_info (i);
+ if (bb_info)
+ {
+ BITMAP_FREE (bb_info->use);
+ BITMAP_FREE (bb_info->def);
+ if (bb_info->in == bb_info->top)
+ bb_info->top = NULL;
+ else
+ {
+ BITMAP_FREE (bb_info->top);
+ BITMAP_FREE (bb_info->ause);
+ BITMAP_FREE (bb_info->adef);
+ }
+ BITMAP_FREE (bb_info->in);
+ BITMAP_FREE (bb_info->out);
+ }
}
+ free_alloc_pool (df_lr->block_pool);
+
+ df_lr->block_info_size = 0;
+ free (df_lr->block_info);
}
- free_alloc_pool (dflow->block_pool);
- dflow->block_info_size = 0;
- free (dflow->block_info);
- free (dflow);
+ BITMAP_FREE (df_lr->out_of_date_transfer_functions);
+ free (df_lr);
}
-/* Debugging info. */
+/* Debugging info at top of bb. */
static void
-df_lr_dump (struct dataflow *dflow, FILE *file)
+df_lr_top_dump (basic_block bb, FILE *file)
{
- basic_block bb;
+ struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
+ struct df_lr_problem_data *problem_data;
+ if (!bb_info || !bb_info->in)
+ return;
+
+ fprintf (file, ";; lr in \t");
+ df_print_regset (file, bb_info->in);
+ if (df_lr->problem_data)
+ {
+ problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
+ fprintf (file, ";; old in \t");
+ df_print_regset (file, problem_data->in[bb->index]);
+ }
+ fprintf (file, ";; lr use \t");
+ df_print_regset (file, bb_info->use);
+ fprintf (file, ";; lr def \t");
+ df_print_regset (file, bb_info->def);
+}
+
+
+/* Debugging info at bottom of bb. */
+
+static void
+df_lr_bottom_dump (basic_block bb, FILE *file)
+{
+ struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
+ struct df_lr_problem_data *problem_data;
+ if (!bb_info || !bb_info->out)
+ return;
- fprintf (file, "Live Registers:\n");
+ fprintf (file, ";; lr out \t");
+ df_print_regset (file, bb_info->out);
+ if (df_lr->problem_data)
+ {
+ problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
+ fprintf (file, ";; old out \t");
+ df_print_regset (file, problem_data->out[bb->index]);
+ }
+}
+
+
+/* Build the datastructure to verify that the solution to the dataflow
+ equations is not dirty. */
+
+static void
+df_lr_verify_solution_start (void)
+{
+ basic_block bb;
+ struct df_lr_problem_data *problem_data;
+ if (df_lr->solutions_dirty)
+ {
+ df_lr->problem_data = NULL;
+ return;
+ }
+
+ /* Set it true so that the solution is recomputed. */
+ df_lr->solutions_dirty = true;
+
+ problem_data = XNEW (struct df_lr_problem_data);
+ df_lr->problem_data = problem_data;
+ problem_data->in = XNEWVEC (bitmap, last_basic_block);
+ problem_data->out = XNEWVEC (bitmap, last_basic_block);
+
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);
+ problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
+ problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
+ bitmap_copy (problem_data->in[bb->index], DF_LR_IN (bb));
+ bitmap_copy (problem_data->out[bb->index], DF_LR_OUT (bb));
+ }
+}
+
+
+/* Compare the saved datastructure and the new solution to the dataflow
+ equations. */
+
+static void
+df_lr_verify_solution_end (void)
+{
+ struct df_lr_problem_data *problem_data;
+ basic_block bb;
+
+ if (df_lr->problem_data == NULL)
+ return;
+
+ problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
+
+ if (df_lr->solutions_dirty)
+ /* Do not check if the solution is still dirty. See the comment
+ in df_lr_local_finalize for details. */
+ df_lr->solutions_dirty = false;
+ else
+ FOR_ALL_BB (bb)
+ {
+ if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LR_IN (bb)))
+ || (!bitmap_equal_p (problem_data->out[bb->index], DF_LR_OUT (bb))))
+ {
+ /*df_dump (stderr);*/
+ gcc_unreachable ();
+ }
+ }
+
+ /* Cannot delete them immediately because you may want to dump them
+ if the comparison fails. */
+ FOR_ALL_BB (bb)
+ {
+ BITMAP_FREE (problem_data->in[bb->index]);
+ BITMAP_FREE (problem_data->out[bb->index]);
}
+
+ free (problem_data->in);
+ free (problem_data->out);
+ free (problem_data);
+ df_lr->problem_data = NULL;
}
+
/* All of the information associated with every instance of the problem. */
static struct df_problem problem_LR =
DF_LR, /* Problem id. */
DF_BACKWARD, /* Direction. */
df_lr_alloc, /* Allocate the problem specific data. */
+ df_lr_reset, /* Reset global information. */
df_lr_free_bb_info, /* Free basic block info. */
df_lr_local_compute, /* Local compute function. */
df_lr_init, /* Init the solution specific data. */
- df_iterative_dataflow, /* Iterative solver. */
+ df_worklist_dataflow, /* Worklist solver. */
df_lr_confluence_0, /* Confluence operator 0. */
df_lr_confluence_n, /* Confluence operator n. */
df_lr_transfer_function, /* Transfer function. */
- NULL, /* Finalize function. */
+ df_lr_local_finalize, /* Finalize function. */
df_lr_free, /* Free all of the problem information. */
- df_lr_dump, /* Debugging. */
- NULL /* Dependent problem. */
+ NULL, /* Remove this problem from the stack of dataflow problems. */
+ NULL, /* Debugging. */
+ df_lr_top_dump, /* Debugging start block. */
+ df_lr_bottom_dump, /* Debugging end block. */
+ df_lr_verify_solution_start,/* Incremental solution verify start. */
+ df_lr_verify_solution_end, /* Incremental solution verify end. */
+ NULL, /* Dependent problem. */
+ TV_DF_LR, /* Timing variable. */
+ false /* Reset blocks on dropping out of blocks_to_analyze. */
};
of DF. The returned structure is what is used to get at the
solution. */
-struct dataflow *
-df_lr_add_problem (struct df *df)
+void
+df_lr_add_problem (void)
+{
+ df_add_problem (&problem_LR);
+ /* These will be initialized when df_scan_blocks processes each
+ block. */
+ df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
+}
+
+
+/* Verify that all of the lr related info is consistent and
+ correct. */
+
+void
+df_lr_verify_transfer_functions (void)
{
- return df_add_problem (df, &problem_LR);
+ basic_block bb;
+ bitmap saved_def;
+ bitmap saved_use;
+ bitmap saved_adef;
+ bitmap saved_ause;
+ bitmap all_blocks;
+ bool need_as;
+
+ if (!df)
+ return;
+
+ saved_def = BITMAP_ALLOC (NULL);
+ saved_use = BITMAP_ALLOC (NULL);
+ saved_adef = BITMAP_ALLOC (NULL);
+ saved_ause = BITMAP_ALLOC (NULL);
+ all_blocks = BITMAP_ALLOC (NULL);
+
+ FOR_ALL_BB (bb)
+ {
+ struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
+ bitmap_set_bit (all_blocks, bb->index);
+
+ if (bb_info)
+ {
+ /* Make a copy of the transfer functions and then compute
+ new ones to see if the transfer functions have
+ changed. */
+ if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions,
+ bb->index))
+ {
+ bitmap_copy (saved_def, bb_info->def);
+ bitmap_copy (saved_use, bb_info->use);
+ bitmap_clear (bb_info->def);
+ bitmap_clear (bb_info->use);
+
+ if (bb_info->adef)
+ {
+ need_as = true;
+ bitmap_copy (saved_adef, bb_info->adef);
+ bitmap_copy (saved_ause, bb_info->ause);
+ bitmap_clear (bb_info->adef);
+ bitmap_clear (bb_info->ause);
+ }
+ else
+ need_as = false;
+
+ df_lr_bb_local_compute (bb->index);
+ gcc_assert (bitmap_equal_p (saved_def, bb_info->def));
+ gcc_assert (bitmap_equal_p (saved_use, bb_info->use));
+
+ if (need_as)
+ {
+ gcc_assert (bb_info->adef);
+ gcc_assert (bb_info->ause);
+ gcc_assert (bitmap_equal_p (saved_adef, bb_info->adef));
+ gcc_assert (bitmap_equal_p (saved_ause, bb_info->ause));
+ }
+ else
+ {
+ gcc_assert (!bb_info->adef);
+ gcc_assert (!bb_info->ause);
+ }
+ }
+ }
+ else
+ {
+ /* If we do not have basic block info, the block must be in
+ the list of dirty blocks or else some one has added a
+ block behind our backs. */
+ gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions,
+ bb->index));
+ }
+ /* Make sure no one created a block without following
+ procedures. */
+ gcc_assert (df_scan_get_bb_info (bb->index));
+ }
+
+ /* Make sure there are no dirty bits in blocks that have been deleted. */
+ gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions,
+ all_blocks));
+
+ BITMAP_FREE (saved_def);
+ BITMAP_FREE (saved_use);
+ BITMAP_FREE (saved_adef);
+ BITMAP_FREE (saved_ause);
+ BITMAP_FREE (all_blocks);
}
\f
/*----------------------------------------------------------------------------
- UNINITIALIZED REGISTERS
+ COMBINED LIVE REGISTERS AND UNINITIALIZED REGISTERS.
- Find the set of uses for registers that are reachable from the entry
- block without passing thru a definition.
-----------------------------------------------------------------------------*/
+ First 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. */
+ Then the in and out sets here are the anded results of the in and
+ out sets from the lr and ur
+ problems.
+----------------------------------------------------------------------------*/
-struct df_ur_bb_info *
-df_ur_get_bb_info (struct dataflow *dflow, unsigned int index)
+/* Private data used to verify the solution for this problem. */
+struct df_live_problem_data
{
- return (struct df_ur_bb_info *) dflow->block_info[index];
-}
+ bitmap *in;
+ bitmap *out;
+};
/* Set basic block info. */
static void
-df_ur_set_bb_info (struct dataflow *dflow, unsigned int index,
- struct df_ur_bb_info *bb_info)
+df_live_set_bb_info (unsigned int index,
+ struct df_live_bb_info *bb_info)
{
- dflow->block_info[index] = bb_info;
+ gcc_assert (df_live);
+ gcc_assert (index < df_live->block_info_size);
+ df_live->block_info[index] = bb_info;
}
/* Free basic block info. */
static void
-df_ur_free_bb_info (struct dataflow *dflow, void *vbb_info)
+df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
+ void *vbb_info)
{
- struct df_ur_bb_info *bb_info = (struct df_ur_bb_info *) vbb_info;
+ struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;
if (bb_info)
{
BITMAP_FREE (bb_info->gen);
BITMAP_FREE (bb_info->kill);
BITMAP_FREE (bb_info->in);
BITMAP_FREE (bb_info->out);
- pool_free (dflow->block_pool, bb_info);
+ pool_free (df_live->block_pool, bb_info);
}
}
-/* Allocate or reset bitmaps for DFLOW blocks. The solution bits are
+/* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
not touched unless the block is new. */
static void
-df_ur_alloc (struct dataflow *dflow, bitmap blocks_to_rescan)
+df_live_alloc (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);
+ if (!df_live->block_pool)
+ df_live->block_pool = create_alloc_pool ("df_live_block pool",
+ sizeof (struct df_live_bb_info), 100);
- /* Because of the clustering of all def sites for the same pseudo,
- we have to process all of the blocks before doing the
- analysis. */
+ df_grow_bb_info (df_live);
- EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi)
+ EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
{
- struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index);
+ struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
if (bb_info)
{
bitmap_clear (bb_info->kill);
}
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 = (struct df_live_bb_info *) pool_alloc (df_live->block_pool);
+ df_live_set_bb_info (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);
}
}
+ df_live->optional_p = (optimize <= 1);
+}
+
+
+/* Reset the global solution for recalculation. */
+
+static void
+df_live_reset (bitmap all_blocks)
+{
+ unsigned int bb_index;
+ bitmap_iterator bi;
+
+ EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+ {
+ struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
+ gcc_assert (bb_info);
+ bitmap_clear (bb_info->in);
+ bitmap_clear (bb_info->out);
+ }
}
/* Compute local uninitialized register info for basic block BB. */
static void
-df_ur_bb_local_compute (struct dataflow *dflow, unsigned int bb_index)
+df_live_bb_local_compute (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);
+ struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
rtx insn;
- struct df_ref *def;
+ struct df_ref **def_rec;
+ int luid = 0;
- bitmap_clear (seen_in_block);
- bitmap_clear (seen_in_insn);
+ for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
+ {
+ struct df_ref *def = *def_rec;
+ if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
+ bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
+ }
- FOR_BB_INSNS_REVERSE (bb, insn)
+ FOR_BB_INSNS (bb, insn)
{
unsigned int uid = INSN_UID (insn);
+ struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
+
+ /* Inserting labels does not always trigger the incremental
+ rescanning. */
+ if (!insn_info)
+ {
+ gcc_assert (!INSN_P (insn));
+ df_insn_create_insn_record (insn);
+ }
+
+ DF_INSN_LUID (insn) = luid;
if (!INSN_P (insn))
continue;
- for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
+ luid++;
+ for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
{
+ struct df_ref *def = *def_rec;
unsigned int regno = DF_REF_REGNO (def);
- /* Only the last def counts. */
- if (!bitmap_bit_p (seen_in_block, regno))
- {
- bitmap_set_bit (seen_in_insn, regno);
-
- if (DF_REF_FLAGS (def) & DF_REF_CLOBBER)
- bitmap_set_bit (bb_info->kill, regno);
- else
- bitmap_set_bit (bb_info->gen, regno);
- }
+
+ if (DF_REF_FLAGS_IS_SET (def,
+ DF_REF_PARTIAL | DF_REF_CONDITIONAL))
+ /* All partial or conditional def
+ seen are included in the gen set. */
+ bitmap_set_bit (bb_info->gen, regno);
+ else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
+ /* Only must clobbers for the entire reg destroy the
+ value. */
+ bitmap_set_bit (bb_info->kill, regno);
+ else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
+ bitmap_set_bit (bb_info->gen, regno);
}
- 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)
+ for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
{
- 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);
- }
+ struct df_ref *def = *def_rec;
+ if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
+ bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
}
}
/* Compute local uninitialized register info. */
static void
-df_ur_local_compute (struct dataflow *dflow,
- bitmap all_blocks ATTRIBUTE_UNUSED,
- bitmap rescan_blocks)
+df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
{
unsigned int bb_index;
bitmap_iterator bi;
- df_set_seen ();
+ df_grow_insn_info ();
- EXECUTE_IF_SET_IN_BITMAP (rescan_blocks, 0, bb_index, bi)
+ EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
+ 0, bb_index, bi)
{
- df_ur_bb_local_compute (dflow, bb_index);
+ df_live_bb_local_compute (bb_index);
}
- df_unset_seen ();
+ bitmap_clear (df_live->out_of_date_transfer_functions);
}
/* Initialize the solution vectors. */
static void
-df_ur_init (struct dataflow *dflow, bitmap all_blocks)
+df_live_init (bitmap all_blocks)
{
unsigned int bb_index;
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
- struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index);
+ struct df_live_bb_info *bb_info = df_live_get_bb_info (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);
-
- bitmap_ior_into (bb_info->in, df_all_hard_regs);
- bitmap_ior_into (bb_info->out, df_all_hard_regs);
-
- /* No register may reach a location where it is not used. Thus
- we trim the rr result to the places where it is used. */
- bitmap_and_into (bb_info->in, bb_lr_info->in);
- bitmap_and_into (bb_info->out, bb_lr_info->out);
-
-#if 1
- /* Hard registers may still stick in the ur_out set, but not
- be in the ur_in set, if their only mention was in a call
- in this block. This is because a call kills in the lr
- problem but does not kill in the ur problem. To clean
- this up, we execute the transfer function on the lr_in
- set and then use that to knock bits out of ur_out. */
- bitmap_ior_and_compl (tmp, bb_info->gen, bb_lr_info->in,
- bb_info->kill);
- bitmap_and_into (bb_info->out, tmp);
-#endif
- }
-
- BITMAP_FREE (tmp);
-}
-
-
/* Confluence function that ignores fake edges. */
static void
-df_ur_confluence_n (struct dataflow *dflow, edge e)
+df_live_confluence_n (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;
+ bitmap op1 = df_live_get_bb_info (e->dest->index)->in;
+ bitmap op2 = df_live_get_bb_info (e->src->index)->out;
if (e->flags & EDGE_FAKE)
return;
/* Transfer function. */
static bool
-df_ur_transfer_function (struct dataflow *dflow, int bb_index)
+df_live_transfer_function (int bb_index)
{
- struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index);
+ struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
bitmap in = bb_info->in;
bitmap out = bb_info->out;
bitmap gen = bb_info->gen;
}
-/* Free all storage associated with the problem. */
+/* And the LR and UR info to produce the LIVE info. */
static void
-df_ur_free (struct dataflow *dflow)
+df_live_local_finalize (bitmap all_blocks)
{
- unsigned int i;
- for (i = 0; i < dflow->block_info_size; i++)
+ if (df_live->solutions_dirty)
{
- struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, i);
- if (bb_info)
+ bitmap_iterator bi;
+ unsigned int bb_index;
+
+ EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
- BITMAP_FREE (bb_info->gen);
- BITMAP_FREE (bb_info->kill);
- BITMAP_FREE (bb_info->in);
- BITMAP_FREE (bb_info->out);
+ struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
+ struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
+
+ /* No register may reach a location where it is not used. Thus
+ we trim the rr result to the places where it is used. */
+ bitmap_and_into (bb_live_info->in, bb_lr_info->in);
+ bitmap_and_into (bb_live_info->out, bb_lr_info->out);
}
+
+ df_live->solutions_dirty = false;
}
-
- free_alloc_pool (dflow->block_pool);
- dflow->block_info_size = 0;
- free (dflow->block_info);
- free (dflow);
}
-/* Debugging info. */
+/* Free all storage associated with the problem. */
static void
-df_ur_dump (struct dataflow *dflow, FILE *file)
+df_live_free (void)
{
- basic_block bb;
-
- fprintf (file, "Undefined regs:\n");
-
- FOR_ALL_BB (bb)
+ if (df_live->block_info)
{
- struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb->index);
- df_print_bb_index (bb, file);
+ unsigned int i;
- if (! bb_info->in)
- continue;
+ for (i = 0; i < df_live->block_info_size; i++)
+ {
+ struct df_live_bb_info *bb_info = df_live_get_bb_info (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 (df_live->block_pool);
+ df_live->block_info_size = 0;
+ free (df_live->block_info);
+ }
+ BITMAP_FREE (df_live->out_of_date_transfer_functions);
+ free (df_live);
+}
+
+
+/* Debugging info at top of bb. */
+
+static void
+df_live_top_dump (basic_block bb, FILE *file)
+{
+ struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
+ struct df_live_problem_data *problem_data;
+
+ if (!bb_info || !bb_info->in)
+ return;
+
+ fprintf (file, ";; live in \t");
+ df_print_regset (file, bb_info->in);
+ if (df_live->problem_data)
+ {
+ problem_data = (struct df_live_problem_data *)df_live->problem_data;
+ fprintf (file, ";; old in \t");
+ df_print_regset (file, problem_data->in[bb->index]);
+ }
+ fprintf (file, ";; live gen \t");
+ df_print_regset (file, bb_info->gen);
+ fprintf (file, ";; live kill\t");
+ df_print_regset (file, bb_info->kill);
+}
+
+
+/* Debugging info at bottom of bb. */
+
+static void
+df_live_bottom_dump (basic_block bb, FILE *file)
+{
+ struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
+ struct df_live_problem_data *problem_data;
+
+ if (!bb_info || !bb_info->out)
+ return;
- 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);
+ fprintf (file, ";; live out \t");
+ df_print_regset (file, bb_info->out);
+ if (df_live->problem_data)
+ {
+ problem_data = (struct df_live_problem_data *)df_live->problem_data;
+ fprintf (file, ";; old out \t");
+ df_print_regset (file, problem_data->out[bb->index]);
+ }
+}
+
+
+/* Build the datastructure to verify that the solution to the dataflow
+ equations is not dirty. */
+
+static void
+df_live_verify_solution_start (void)
+{
+ basic_block bb;
+ struct df_live_problem_data *problem_data;
+ if (df_live->solutions_dirty)
+ {
+ df_live->problem_data = NULL;
+ return;
+ }
+
+ /* Set it true so that the solution is recomputed. */
+ df_live->solutions_dirty = true;
+
+ problem_data = XNEW (struct df_live_problem_data);
+ df_live->problem_data = problem_data;
+ problem_data->in = XNEWVEC (bitmap, last_basic_block);
+ problem_data->out = XNEWVEC (bitmap, last_basic_block);
+
+ FOR_ALL_BB (bb)
+ {
+ problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
+ problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
+ bitmap_copy (problem_data->in[bb->index], DF_LIVE_IN (bb));
+ bitmap_copy (problem_data->out[bb->index], DF_LIVE_OUT (bb));
+ }
+}
+
+
+/* Compare the saved datastructure and the new solution to the dataflow
+ equations. */
+
+static void
+df_live_verify_solution_end (void)
+{
+ struct df_live_problem_data *problem_data;
+ basic_block bb;
+
+ if (df_live->problem_data == NULL)
+ return;
+
+ problem_data = (struct df_live_problem_data *)df_live->problem_data;
+
+ FOR_ALL_BB (bb)
+ {
+ if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LIVE_IN (bb)))
+ || (!bitmap_equal_p (problem_data->out[bb->index], DF_LIVE_OUT (bb))))
+ {
+ /*df_dump (stderr);*/
+ gcc_unreachable ();
+ }
+ }
+
+ /* Cannot delete them immediately because you may want to dump them
+ if the comparison fails. */
+ FOR_ALL_BB (bb)
+ {
+ BITMAP_FREE (problem_data->in[bb->index]);
+ BITMAP_FREE (problem_data->out[bb->index]);
}
+
+ free (problem_data->in);
+ free (problem_data->out);
+ free (problem_data);
+ df_live->problem_data = NULL;
}
+
/* All of the information associated with every instance of the problem. */
-static struct df_problem problem_UR =
+static struct df_problem problem_LIVE =
{
- DF_UR, /* Problem id. */
- DF_FORWARD, /* Direction. */
- df_ur_alloc, /* Allocate the problem specific data. */
- df_ur_free_bb_info, /* Free basic block info. */
- df_ur_local_compute, /* Local compute function. */
- df_ur_init, /* Init the solution specific data. */
- df_iterative_dataflow, /* Iterative solver. */
- NULL, /* Confluence operator 0. */
- df_ur_confluence_n, /* Confluence operator n. */
- df_ur_transfer_function, /* Transfer function. */
- df_ur_local_finalize, /* Finalize function. */
- df_ur_free, /* Free all of the problem information. */
- df_ur_dump, /* Debugging. */
- &problem_LR /* Dependent problem. */
+ DF_LIVE, /* Problem id. */
+ DF_FORWARD, /* Direction. */
+ df_live_alloc, /* Allocate the problem specific data. */
+ df_live_reset, /* Reset global information. */
+ df_live_free_bb_info, /* Free basic block info. */
+ df_live_local_compute, /* Local compute function. */
+ df_live_init, /* Init the solution specific data. */
+ df_worklist_dataflow, /* Worklist solver. */
+ NULL, /* Confluence operator 0. */
+ df_live_confluence_n, /* Confluence operator n. */
+ df_live_transfer_function, /* Transfer function. */
+ df_live_local_finalize, /* Finalize function. */
+ df_live_free, /* Free all of the problem information. */
+ df_live_free, /* Remove this problem from the stack of dataflow problems. */
+ NULL, /* Debugging. */
+ df_live_top_dump, /* Debugging start block. */
+ df_live_bottom_dump, /* Debugging end block. */
+ df_live_verify_solution_start,/* Incremental solution verify start. */
+ df_live_verify_solution_end, /* Incremental solution verify end. */
+ &problem_LR, /* Dependent problem. */
+ TV_DF_LIVE, /* Timing variable. */
+ false /* Reset blocks on dropping out of blocks_to_analyze. */
};
of DF. The returned structure is what is used to get at the
solution. */
-struct dataflow *
-df_ur_add_problem (struct df *df)
+void
+df_live_add_problem (void)
+{
+ df_add_problem (&problem_LIVE);
+ /* These will be initialized when df_scan_blocks processes each
+ block. */
+ df_live->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
+}
+
+
+/* Set all of the blocks as dirty. This needs to be done if this
+ problem is added after all of the insns have been scanned. */
+
+void
+df_live_set_all_dirty (void)
+{
+ basic_block bb;
+ FOR_ALL_BB (bb)
+ bitmap_set_bit (df_live->out_of_date_transfer_functions,
+ bb->index);
+}
+
+
+/* Verify that all of the lr related info is consistent and
+ correct. */
+
+void
+df_live_verify_transfer_functions (void)
{
- return df_add_problem (df, &problem_UR);
+ basic_block bb;
+ bitmap saved_gen;
+ bitmap saved_kill;
+ bitmap all_blocks;
+
+ if (!df)
+ return;
+
+ saved_gen = BITMAP_ALLOC (NULL);
+ saved_kill = BITMAP_ALLOC (NULL);
+ all_blocks = BITMAP_ALLOC (NULL);
+
+ df_grow_insn_info ();
+
+ FOR_ALL_BB (bb)
+ {
+ struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
+ bitmap_set_bit (all_blocks, bb->index);
+
+ if (bb_info)
+ {
+ /* Make a copy of the transfer functions and then compute
+ new ones to see if the transfer functions have
+ changed. */
+ if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,
+ bb->index))
+ {
+ bitmap_copy (saved_gen, bb_info->gen);
+ bitmap_copy (saved_kill, bb_info->kill);
+ bitmap_clear (bb_info->gen);
+ bitmap_clear (bb_info->kill);
+
+ df_live_bb_local_compute (bb->index);
+ gcc_assert (bitmap_equal_p (saved_gen, bb_info->gen));
+ gcc_assert (bitmap_equal_p (saved_kill, bb_info->kill));
+ }
+ }
+ else
+ {
+ /* If we do not have basic block info, the block must be in
+ the list of dirty blocks or else some one has added a
+ block behind our backs. */
+ gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,
+ bb->index));
+ }
+ /* Make sure no one created a block without following
+ procedures. */
+ gcc_assert (df_scan_get_bb_info (bb->index));
+ }
+
+ /* Make sure there are no dirty bits in blocks that have been deleted. */
+ gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
+ all_blocks));
+ BITMAP_FREE (saved_gen);
+ BITMAP_FREE (saved_kill);
+ BITMAP_FREE (all_blocks);
}
UNINITIALIZED REGISTERS WITH EARLYCLOBBER
Find the set of uses for registers that are reachable from the entry
- block without passing thru a definition.
+ 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.
-----------------------------------------------------------------------------*/
+ features just for the register allocation phase. This problem
+ should go 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
};
-/* 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)
+df_urec_set_bb_info (unsigned int index,
+ struct df_urec_bb_info *bb_info)
{
- dflow->block_info[index] = bb_info;
+ gcc_assert (df_urec);
+ gcc_assert (index < df_urec->block_info_size);
+ df_urec->block_info[index] = bb_info;
}
/* Free basic block info. */
static void
-df_urec_free_bb_info (struct dataflow *dflow, void *vbb_info)
+df_urec_free_bb_info (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->in);
BITMAP_FREE (bb_info->out);
BITMAP_FREE (bb_info->earlyclobber);
- pool_free (dflow->block_pool, bb_info);
+ pool_free (df_urec->block_pool, bb_info);
}
}
-/* Allocate or reset bitmaps for DFLOW blocks. The solution bits are
+/* Allocate or reset bitmaps for DF_UREC blocks. The solution bits are
not touched unless the block is new. */
static void
-df_urec_alloc (struct dataflow *dflow, bitmap blocks_to_rescan)
+df_urec_alloc (bitmap all_blocks)
+
{
unsigned int bb_index;
bitmap_iterator bi;
- struct df_urec_problem_data *problem_data =
- (struct df_urec_problem_data *) dflow->problem_data;
+ struct df_urec_problem_data *problem_data
+ = (struct df_urec_problem_data *) df_urec->problem_data;
- if (! dflow->block_pool)
- dflow->block_pool = create_alloc_pool ("df_urec_block pool",
+ if (!df_urec->block_pool)
+ df_urec->block_pool = create_alloc_pool ("df_urec_block pool",
sizeof (struct df_urec_bb_info), 50);
- if (!dflow->problem_data)
+ if (!df_urec->problem_data)
{
- problem_data = xmalloc (sizeof (struct df_urec_problem_data));
- dflow->problem_data = problem_data;
+ problem_data = XNEW (struct df_urec_problem_data);
+ df_urec->problem_data = problem_data;
}
problem_data->earlyclobbers_found = false;
- df_grow_bb_info (dflow);
-
- /* Because of the clustering of all def sites for the same pseudo,
- we have to process all of the blocks before doing the
- analysis. */
+ df_grow_bb_info (df_urec);
- EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi)
+ EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
- struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index);
+ struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
if (bb_info)
{
bitmap_clear (bb_info->kill);
}
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 = (struct df_urec_bb_info *) pool_alloc (df_urec->block_pool);
+ df_urec_set_bb_info (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->top = BITMAP_ALLOC (NULL);
bb_info->earlyclobber = BITMAP_ALLOC (NULL);
}
}
+ df_urec->optional_p = true;
}
if (!REG_P (reg))
return;
-
- endregno = regno = REGNO (reg);
+ regno = REGNO (reg);
if (regno < FIRST_PSEUDO_REGISTER)
{
- endregno +=hard_regno_nregs[regno][GET_MODE (reg)];
-
+ endregno = END_HARD_REGNO (reg);
for (i = regno; i < endregno; i++)
{
bitmap_set_bit (bb_info->kill, i);
/* Classes of registers which could be early clobbered in the current
insn. */
-DEF_VEC_I(int);
-DEF_VEC_ALLOC_I(int,heap);
-
static VEC(int,heap) *earlyclobber_regclass;
/* This function finds and stores register classes that could be early
/* Compute local uninitialized register info for basic block BB. */
static void
-df_urec_bb_local_compute (struct dataflow *dflow, unsigned int bb_index)
+df_urec_bb_local_compute (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);
+ struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
rtx insn;
- struct df_ref *def;
+ struct df_ref **def_rec;
- for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref)
+ for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
{
- unsigned int regno = DF_REF_REGNO (def);
- bitmap_set_bit (bb_info->gen, regno);
+ struct df_ref *def = *def_rec;
+ 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_state & (DF_SCAN_GLOBAL | DF_SCAN_POST_ALLOC)
- && df_urec_check_earlyclobber (insn))
+ if (df_urec_check_earlyclobber (insn))
{
- struct df_urec_problem_data *problem_data =
- (struct df_urec_problem_data *) dflow->problem_data;
+ struct df_urec_problem_data *problem_data
+ = (struct df_urec_problem_data *) df_urec->problem_data;
problem_data->earlyclobbers_found = true;
note_uses (&PATTERN (insn),
df_urec_mark_reg_use_for_earlyclobber_1, bb_info);
}
}
}
+
+ for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
+ {
+ struct df_ref *def = *def_rec;
+ if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
+ {
+ 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)
+df_urec_local_compute (bitmap all_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;
+ HARD_REG_SET stack_hard_regs, used;
+ struct df_urec_problem_data *problem_data
+ = (struct df_urec_problem_data *) df_urec->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
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);
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:
- ;
+ if (!hard_reg_set_empty_p (used))
+ bitmap_set_bit (problem_data->stack_regs, i);
}
#endif
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)
+ EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
- df_urec_bb_local_compute (dflow, bb_index);
+ df_urec_bb_local_compute (bb_index);
}
VEC_free (int, heap, earlyclobber_regclass);
/* Initialize the solution vectors. */
static void
-df_urec_init (struct dataflow *dflow, bitmap all_blocks)
+df_urec_init (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);
+ struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
- /* FIXME: This is a hack, it has been copied over from
- make_accurate_live_analysis by Vlad. Most likely it is necessary
- because the generation of gen and kill information for hardware
- registers in ur is a subset of what is really necessary and what
- is done for the lr problem. */
-
- /* Inside the register allocator, partial availability is only
- allowed for the psuedo registers. To implement this, the rr is
- initially iored with a mask ones for the hard registers and zeros
- for the pseudos before being iterated. This means that each
- hardware register will be live unless explicitly killed by some
- statement. Eventually most of these bit will die because the
- results of rr are anded with the results of lr before being used.
- Outside of register allocation, a more conservative strategy of
- completely ignoring the unintialized registers is imployed in the
- finalizer function. */
- if (df_state & DF_SCAN_GLOBAL)
- {
- bitmap_ior (bb_info->out, bb_info->gen, df_all_hard_regs);
- bitmap_copy (bb_info->in, df_all_hard_regs);
- }
- else
- {
- bitmap_copy (bb_info->out, bb_info->gen);
- bitmap_clear (bb_info->in);
- }
+ 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. */
+/* Or in the stack regs, hard regs and early clobber regs into the
+ urec_in sets of all of the blocks. */
+
static void
-df_urec_local_finalize (struct dataflow *dflow, bitmap all_blocks)
+df_urec_local_finalize (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;
+ struct df_urec_problem_data *problem_data
+ = (struct df_urec_problem_data *) df_urec->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);
+ struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
+ struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
if (bb_index != ENTRY_BLOCK && bb_index != EXIT_BLOCK)
{
#endif
}
- if (!(df_state & DF_SCAN_GLOBAL))
- {
- bitmap_ior_into (bb_info->in, df_all_hard_regs);
- bitmap_ior_into (bb_info->out, df_all_hard_regs);
- }
-
/* No register may reach a location where it is not used. Thus
we trim the rr result to the places where it is used. */
bitmap_and_into (bb_info->in, bb_lr_info->in);
bitmap_and_into (bb_info->out, bb_lr_info->out);
-
-#if 1
+ bitmap_copy (bb_info->top, bb_info->in);
+ if (bb_lr_info->adef)
+ bitmap_ior_into (bb_info->top, bb_lr_info->adef);
+ bitmap_and_into (bb_info->top, bb_lr_info->top);
+#if 0
/* 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
/* Confluence function that ignores fake edges. */
static void
-df_urec_confluence_n (struct dataflow *dflow, edge e)
+df_urec_confluence_n (edge e)
{
- bitmap op1 = df_urec_get_bb_info (dflow, e->dest->index)->in;
- bitmap op2 = df_urec_get_bb_info (dflow, e->src->index)->out;
+ bitmap op1 = df_urec_get_bb_info (e->dest->index)->in;
+ bitmap op2 = df_urec_get_bb_info (e->src->index)->out;
if (e->flags & EDGE_FAKE)
return;
/* Transfer function. */
static bool
-df_urec_transfer_function (struct dataflow *dflow, int bb_index)
+df_urec_transfer_function (int bb_index)
{
- struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index);
+ struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
bitmap in = bb_info->in;
bitmap out = bb_info->out;
bitmap gen = bb_info->gen;
/* Free all storage associated with the problem. */
static void
-df_urec_free (struct dataflow *dflow)
+df_urec_free (void)
{
- unsigned int i;
-
- for (i = 0; i < dflow->block_info_size; i++)
+ if (df_urec->block_info)
{
- struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, i);
- if (bb_info)
+ unsigned int i;
+
+ for (i = 0; i < df_urec->block_info_size; i++)
{
- 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);
+ struct df_urec_bb_info *bb_info = df_urec_get_bb_info (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);
+ BITMAP_FREE (bb_info->top);
+ }
}
+
+ free_alloc_pool (df_urec->block_pool);
+
+ df_urec->block_info_size = 0;
+ free (df_urec->block_info);
+ free (df_urec->problem_data);
}
-
- free_alloc_pool (dflow->block_pool);
-
- dflow->block_info_size = 0;
- free (dflow->block_info);
- free (dflow->problem_data);
- free (dflow);
+ free (df_urec);
}
-/* Debugging info. */
+/* Debugging info at top of bb. */
static void
-df_urec_dump (struct dataflow *dflow, FILE *file)
+df_urec_top_dump (basic_block bb, FILE *file)
{
- basic_block bb;
-
- 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;
+ struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb->index);
+ if (!bb_info || !bb_info->in)
+ return;
- 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);
- }
+ fprintf (file, ";; urec in \t");
+ df_print_regset (file, bb_info->in);
+ fprintf (file, ";; urec gen \t");
+ df_print_regset (file, bb_info->gen);
+ fprintf (file, ";; urec kill\t");
+ df_print_regset (file, bb_info->kill);
+ fprintf (file, ";; urec ec\t");
+ df_print_regset (file, bb_info->earlyclobber);
+}
+
+
+/* Debugging info at bottom of bb. */
+
+static void
+df_urec_bottom_dump (basic_block bb, FILE *file)
+{
+ struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb->index);
+ if (!bb_info || !bb_info->out)
+ return;
+ fprintf (file, ";; urec out \t");
+ df_print_regset (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. */
+ df_worklist_dataflow, /* Worklist solver. */
NULL, /* Confluence operator 0. */
df_urec_confluence_n, /* Confluence operator n. */
df_urec_transfer_function, /* Transfer function. */
df_urec_local_finalize, /* Finalize function. */
df_urec_free, /* Free all of the problem information. */
- df_urec_dump, /* Debugging. */
- &problem_LR /* Dependent problem. */
+ df_urec_free, /* Remove this problem from the stack of dataflow problems. */
+ NULL, /* Debugging. */
+ df_urec_top_dump, /* Debugging start block. */
+ df_urec_bottom_dump, /* Debugging end block. */
+ NULL, /* Incremental solution verify start. */
+ NULL, /* Incremental solution verify end. */
+ &problem_LR, /* Dependent problem. */
+ TV_DF_UREC, /* Timing variable. */
+ false /* Reset blocks on dropping out of blocks_to_analyze. */
};
of DF. The returned structure is what is used to get at the
solution. */
-struct dataflow *
-df_urec_add_problem (struct df *df)
+void
+df_urec_add_problem (void)
{
- return df_add_problem (df, &problem_UREC);
+ df_add_problem (&problem_UREC);
}
the reaching defs information (the dependent problem).
----------------------------------------------------------------------------*/
-struct df_chain_problem_data
-{
- int flags;
-};
-
+#define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
-/* Create def-use or use-def chains. */
+/* Create a du or ud chain from SRC to DST and link it into SRC. */
-static void
-df_chain_alloc (struct dataflow *dflow,
- bitmap blocks_to_rescan ATTRIBUTE_UNUSED)
+struct df_link *
+df_chain_create (struct df_ref *src, struct df_ref *dst)
{
- struct df *df = dflow->df;
- unsigned int i;
- struct df_chain_problem_data *problem_data =
- (struct df_chain_problem_data *) dflow->problem_data;
+ struct df_link *head = DF_REF_CHAIN (src);
+ struct df_link *link = pool_alloc (df_chain->block_pool);;
+
+ DF_REF_CHAIN (src) = link;
+ link->next = head;
+ link->ref = dst;
+ return link;
+}
- /* 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);
+/* Delete any du or ud chains that start at REF and point to
+ TARGET. */
+static void
+df_chain_unlink_1 (struct df_ref *ref, struct df_ref *target)
+{
+ struct df_link *chain = DF_REF_CHAIN (ref);
+ struct df_link *prev = NULL;
- if (problem_data->flags & DF_DU_CHAIN)
+ while (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++)
+ if (chain->ref == target)
{
- struct df_ref *ref = df->def_info.refs[i];
- DF_REF_CHAIN (ref) = NULL;
+ if (prev)
+ prev->next = chain->next;
+ else
+ DF_REF_CHAIN (ref) = chain->next;
+ pool_free (df_chain->block_pool, chain);
+ return;
}
+ prev = chain;
+ chain = chain->next;
}
-
- if (problem_data->flags & DF_UD_CHAIN)
+}
+
+
+/* Delete a du or ud chain that leave or point to REF. */
+
+void
+df_chain_unlink (struct df_ref *ref)
+{
+ struct df_link *chain = DF_REF_CHAIN (ref);
+ while (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;
- }
+ struct df_link *next = chain->next;
+ /* Delete the other side if it exists. */
+ df_chain_unlink_1 (chain->ref, ref);
+ pool_free (df_chain->block_pool, chain);
+ chain = next;
}
+ DF_REF_CHAIN (ref) = NULL;
}
-/* Create the chains for a list of USEs. */
+/* Copy the du or ud chain starting at FROM_REF and attach it to
+ TO_REF. */
+
+void
+df_chain_copy (struct df_ref *to_ref,
+ struct df_link *from_ref)
+{
+ while (from_ref)
+ {
+ df_chain_create (to_ref, from_ref->ref);
+ from_ref = from_ref->next;
+ }
+}
+
+
+/* Remove this problem from the stack of dataflow problems. */
static void
-df_chain_create_bb_process_use (struct dataflow *dflow,
- struct df_chain_problem_data *problem_data,
- bitmap local_rd,
- struct df_ref *use,
- enum df_ref_flags top_flag)
+df_chain_remove_problem (void)
{
- struct df *df = dflow->df;
bitmap_iterator bi;
- unsigned int def_index;
-
- while (use)
+ unsigned int bb_index;
+
+ /* Wholesale destruction of the old chains. */
+ if (df_chain->block_pool)
+ free_alloc_pool (df_chain->block_pool);
+
+ EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
{
- /* Do not want to go thur this for an uninitialized var. */
- unsigned int uregno = DF_REF_REGNO (use);
- int count = DF_REG_DEF_GET (df, uregno)->n_refs;
- if (count)
+ rtx insn;
+ struct df_ref **def_rec;
+ struct df_ref **use_rec;
+ basic_block bb = BASIC_BLOCK (bb_index);
+
+ if (df_chain_problem_p (DF_DU_CHAIN))
+ for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
+ DF_REF_CHAIN (*def_rec) = NULL;
+ if (df_chain_problem_p (DF_UD_CHAIN))
+ for (use_rec = df_get_artificial_uses (bb->index); *use_rec; use_rec++)
+ DF_REF_CHAIN (*use_rec) = NULL;
+
+ FOR_BB_INSNS (bb, insn)
{
- if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
+ unsigned int uid = INSN_UID (insn);
+
+ if (INSN_P (insn))
{
- 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)
+ if (df_chain_problem_p (DF_DU_CHAIN))
+ for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+ DF_REF_CHAIN (*def_rec) = NULL;
+ if (df_chain_problem_p (DF_UD_CHAIN))
{
- struct df_ref *def;
- if (def_index > last_index)
- break;
-
- def = DF_DEFS_GET (df, def_index);
- if (problem_data->flags & DF_DU_CHAIN)
- df_chain_create (dflow, def, use);
- if (problem_data->flags & DF_UD_CHAIN)
- df_chain_create (dflow, use, def);
+ for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
+ DF_REF_CHAIN (*use_rec) = NULL;
+ for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
+ DF_REF_CHAIN (*use_rec) = NULL;
}
}
}
- use = use->next_ref;
}
+
+ bitmap_clear (df_chain->out_of_date_transfer_functions);
+ df_chain->block_pool = NULL;
}
-/* 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. */
+/* Remove the chain problem completely. */
+
static void
-df_chain_create_bb (struct dataflow *dflow,
- struct dataflow *rd_dflow,
- unsigned int bb_index)
+df_chain_fully_remove_problem (void)
{
- basic_block bb = BASIC_BLOCK (bb_index);
- struct df_rd_bb_info *bb_info = df_rd_get_bb_info (rd_dflow, bb_index);
- rtx insn;
- bitmap cpy = BITMAP_ALLOC (NULL);
- struct df *df = dflow->df;
- struct df_chain_problem_data *problem_data =
- (struct df_chain_problem_data *) dflow->problem_data;
- struct df_ref *def;
+ df_chain_remove_problem ();
+ BITMAP_FREE (df_chain->out_of_date_transfer_functions);
+ free (df_chain);
+}
- bitmap_copy (cpy, bb_info->in);
- /* Since we are going forwards, process the artificial uses first
- then the artificial defs second. */
+/* Create def-use or use-def chains. */
-#ifdef EH_USES
- /* Create the chains for the artificial uses from the EH_USES at the
- beginning of the block. */
- df_chain_create_bb_process_use (dflow, problem_data, cpy,
- df_get_artificial_uses (df, bb->index),
- DF_REF_AT_TOP);
-#endif
+static void
+df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
+{
+ df_chain_remove_problem ();
+ df_chain->block_pool = create_alloc_pool ("df_chain_block pool",
+ sizeof (struct df_link), 50);
+ df_chain->optional_p = true;
+}
- for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref)
- {
- unsigned int dregno = DF_REF_REGNO (def);
- bitmap_clear_range (cpy,
- DF_REG_DEF_GET (df, dregno)->begin,
- DF_REG_DEF_GET (df, dregno)->n_refs);
- if (! (DF_REF_FLAGS (def) & DF_REF_CLOBBER))
- bitmap_set_bit (cpy, DF_REF_ID (def));
- }
-
- /* Process the regular instructions next. */
- FOR_BB_INSNS (bb, insn)
- {
- struct df_ref *def;
+
+/* Reset all of the chains when the set of basic blocks changes. */
+
+static void
+df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
+{
+ df_chain_remove_problem ();
+}
+
+
+/* Create the chains for a list of USEs. */
+
+static void
+df_chain_create_bb_process_use (bitmap local_rd,
+ struct df_ref **use_rec,
+ enum df_ref_flags top_flag)
+{
+ bitmap_iterator bi;
+ unsigned int def_index;
+
+ while (*use_rec)
+ {
+ struct df_ref *use = *use_rec;
+ unsigned int uregno = DF_REF_REGNO (use);
+ if ((!(df->changeable_flags & DF_NO_HARD_REGS))
+ || (uregno >= FIRST_PSEUDO_REGISTER))
+ {
+ /* Do not want to go through this for an uninitialized var. */
+ int count = DF_DEFS_COUNT (uregno);
+ if (count)
+ {
+ if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
+ {
+ unsigned int first_index = DF_DEFS_BEGIN (uregno);
+ unsigned int last_index = first_index + count - 1;
+
+ EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
+ {
+ struct df_ref *def;
+ if (def_index > last_index)
+ break;
+
+ def = DF_DEFS_GET (def_index);
+ if (df_chain_problem_p (DF_DU_CHAIN))
+ df_chain_create (def, use);
+ if (df_chain_problem_p (DF_UD_CHAIN))
+ df_chain_create (use, def);
+ }
+ }
+ }
+ }
+
+ use_rec++;
+ }
+}
+
+
+/* Create chains from reaching defs bitmaps for basic block BB. */
+
+static void
+df_chain_create_bb (unsigned int bb_index)
+{
+ basic_block bb = BASIC_BLOCK (bb_index);
+ struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
+ rtx insn;
+ bitmap cpy = BITMAP_ALLOC (NULL);
+ struct df_ref **def_rec;
+
+ bitmap_copy (cpy, bb_info->in);
+ bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
+
+ /* Since we are going forwards, process the artificial uses first
+ then the artificial defs second. */
+
+#ifdef EH_USES
+ /* Create the chains for the artificial uses from the EH_USES at the
+ beginning of the block. */
+
+ /* Artificials are only hard regs. */
+ if (!(df->changeable_flags & DF_NO_HARD_REGS))
+ df_chain_create_bb_process_use (cpy,
+ df_get_artificial_uses (bb->index),
+ DF_REF_AT_TOP);
+#endif
+
+ for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
+ {
+ struct df_ref *def = *def_rec;
+ if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
+ {
+ unsigned int dregno = DF_REF_REGNO (def);
+ if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
+ bitmap_clear_range (cpy,
+ DF_DEFS_BEGIN (dregno),
+ DF_DEFS_COUNT (dregno));
+ bitmap_set_bit (cpy, DF_REF_ID (def));
+ }
+ }
+
+ /* Process the regular instructions next. */
+ FOR_BB_INSNS (bb, insn)
+ {
+ struct df_ref **def_rec;
unsigned int uid = INSN_UID (insn);
- if (! INSN_P (insn))
+ 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, problem_data, cpy,
- DF_INSN_UID_GET (df, uid)->uses, 0);
+ df_chain_create_bb_process_use (cpy, DF_INSN_UID_USES (uid), 0);
+
+ if (df->changeable_flags & DF_EQ_NOTES)
+ df_chain_create_bb_process_use (cpy, DF_INSN_UID_EQ_USES (uid), 0);
+
/* Since we are going forwards, process the defs second. This
pass only changes the bits in cpy. */
- for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
+ for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
{
+ struct df_ref *def = *def_rec;
unsigned int dregno = DF_REF_REGNO (def);
- bitmap_clear_range (cpy,
- DF_REG_DEF_GET (df, dregno)->begin,
- DF_REG_DEF_GET (df, dregno)->n_refs);
- if (! (DF_REF_FLAGS (def) & DF_REF_CLOBBER))
- bitmap_set_bit (cpy, DF_REF_ID (def));
+ if ((!(df->changeable_flags & DF_NO_HARD_REGS))
+ || (dregno >= FIRST_PSEUDO_REGISTER))
+ {
+ if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
+ bitmap_clear_range (cpy,
+ DF_DEFS_BEGIN (dregno),
+ DF_DEFS_COUNT (dregno));
+ if (!(DF_REF_FLAGS (def)
+ & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
+ bitmap_set_bit (cpy, DF_REF_ID (def));
+ }
}
}
/* Create the chains for the artificial uses of the hard registers
at the end of the block. */
- df_chain_create_bb_process_use (dflow, problem_data, cpy,
- df_get_artificial_uses (df, bb->index), 0);
+ if (!(df->changeable_flags & DF_NO_HARD_REGS))
+ df_chain_create_bb_process_use (cpy,
+ df_get_artificial_uses (bb->index),
+ 0);
+
+ BITMAP_FREE (cpy);
}
/* Create def-use chains from reaching use bitmaps for basic blocks
in BLOCKS. */
static void
-df_chain_finalize (struct dataflow *dflow, bitmap all_blocks)
+df_chain_finalize (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);
+ df_chain_create_bb (bb_index);
}
}
/* Free all storage associated with the problem. */
static void
-df_chain_free (struct dataflow *dflow)
+df_chain_free (void)
{
- free_alloc_pool (dflow->block_pool);
- free (dflow->problem_data);
- free (dflow);
+ free_alloc_pool (df_chain->block_pool);
+ BITMAP_FREE (df_chain->out_of_date_transfer_functions);
+ free (df_chain);
}
/* Debugging info. */
static void
-df_chains_dump (struct dataflow *dflow, FILE *file)
+df_chain_top_dump (basic_block bb, FILE *file)
{
- struct df *df = dflow->df;
- unsigned int j;
- struct df_chain_problem_data *problem_data =
- (struct df_chain_problem_data *) dflow->problem_data;
-
- if (problem_data->flags & DF_DU_CHAIN)
+ if (df_chain_problem_p (DF_DU_CHAIN))
{
- fprintf (file, "Def-use chains:\n");
- for (j = 0; j < df->def_info.bitmap_size; j++)
+ rtx insn;
+ struct df_ref **def_rec = df_get_artificial_defs (bb->index);
+ if (*def_rec)
{
- struct df_ref *def = DF_DEFS_GET (df, j);
- if (def)
+
+ fprintf (file, ";; DU chains for artificial defs\n");
+ while (*def_rec)
{
- fprintf (file, "d%d bb %d luid %d insn %d reg %d ",
- j, DF_REF_BBNO (def),
- DF_INSN_LUID (df, DF_REF_INSN (def)),
- DF_REF_INSN (def) ? DF_REF_INSN_UID (def) : -1,
- DF_REF_REGNO (def));
- if (def->flags & DF_REF_READ_WRITE)
- fprintf (file, "read/write ");
- df_chain_dump (df, DF_REF_CHAIN (def), file);
+ struct df_ref *def = *def_rec;
+ fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
+ df_chain_dump (DF_REF_CHAIN (def), file);
fprintf (file, "\n");
+ def_rec++;
+ }
+ }
+
+ FOR_BB_INSNS (bb, insn)
+ {
+ unsigned int uid = INSN_UID (insn);
+ if (INSN_P (insn))
+ {
+ def_rec = DF_INSN_UID_DEFS (uid);
+ if (*def_rec)
+ {
+ fprintf (file, ";; DU chains for insn luid %d uid %d\n",
+ DF_INSN_LUID (insn), uid);
+
+ while (*def_rec)
+ {
+ struct df_ref *def = *def_rec;
+ fprintf (file, ";; reg %d ", 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");
+ def_rec++;
+ }
+ }
}
}
}
+}
- if (problem_data->flags & DF_UD_CHAIN)
+
+static void
+df_chain_bottom_dump (basic_block bb, FILE *file)
+{
+ if (df_chain_problem_p (DF_UD_CHAIN))
{
- fprintf (file, "Use-def chains:\n");
- for (j = 0; j < df->use_info.bitmap_size; j++)
+ rtx insn;
+ struct df_ref **use_rec = df_get_artificial_uses (bb->index);
+
+ if (*use_rec)
{
- struct df_ref *use = DF_USES_GET (df, j);
- if (use)
+ fprintf (file, ";; UD chains for artificial uses\n");
+ while (*use_rec)
{
- fprintf (file, "u%d bb %d luid %d insn %d reg %d ",
- j, DF_REF_BBNO (use),
- DF_REF_INSN (use) ?
- DF_INSN_LUID (df, DF_REF_INSN (use))
- : -1,
- DF_REF_INSN (DF_USES_GET (df, j)) ?
- DF_REF_INSN_UID (DF_USES_GET (df,j))
- : -1,
- DF_REF_REGNO (use));
- if (use->flags & DF_REF_READ_WRITE)
- fprintf (file, "read/write ");
- if (use->flags & DF_REF_STRIPPED)
- fprintf (file, "stripped ");
- if (use->flags & DF_REF_IN_NOTE)
- fprintf (file, "note ");
- df_chain_dump (df, DF_REF_CHAIN (use), file);
+ struct df_ref *use = *use_rec;
+ fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
+ df_chain_dump (DF_REF_CHAIN (use), file);
fprintf (file, "\n");
+ use_rec++;
+ }
+ }
+
+ FOR_BB_INSNS (bb, insn)
+ {
+ unsigned int uid = INSN_UID (insn);
+ if (INSN_P (insn))
+ {
+ struct df_ref **eq_use_rec = DF_INSN_UID_EQ_USES (uid);
+ use_rec = DF_INSN_UID_USES (uid);
+ if (*use_rec || *eq_use_rec)
+ {
+ fprintf (file, ";; UD chains for insn luid %d uid %d\n",
+ DF_INSN_LUID (insn), uid);
+
+ while (*use_rec)
+ {
+ struct df_ref *use = *use_rec;
+ fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
+ if (use->flags & DF_REF_READ_WRITE)
+ fprintf (file, "read/write ");
+ df_chain_dump (DF_REF_CHAIN (use), file);
+ fprintf (file, "\n");
+ use_rec++;
+ }
+ while (*eq_use_rec)
+ {
+ struct df_ref *use = *eq_use_rec;
+ fprintf (file, ";; eq_note reg %d ", DF_REF_REGNO (use));
+ df_chain_dump (DF_REF_CHAIN (use), file);
+ fprintf (file, "\n");
+ eq_use_rec++;
+ }
+ }
}
}
}
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, /* Transfer function. */
df_chain_finalize, /* Finalize function. */
df_chain_free, /* Free all of the problem information. */
- df_chains_dump, /* Debugging. */
- &problem_RD /* Dependent problem. */
+ df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems. */
+ NULL, /* Debugging. */
+ df_chain_top_dump, /* Debugging start block. */
+ df_chain_bottom_dump, /* Debugging end block. */
+ NULL, /* Incremental solution verify start. */
+ NULL, /* Incremental solution verify end. */
+ &problem_RD, /* Dependent problem. */
+ TV_DF_CHAIN, /* Timing variable. */
+ false /* Reset blocks on dropping out of blocks_to_analyze. */
};
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)
+void
+df_chain_add_problem (enum df_chain_flags chain_flags)
{
- struct df_chain_problem_data *problem_data =
- xmalloc (sizeof (struct df_chain_problem_data));
- struct dataflow *dflow = df_add_problem (df, &problem_CHAIN);
-
- dflow->problem_data = problem_data;
- problem_data->flags = flags;
-
- return dflow;
+ df_add_problem (&problem_CHAIN);
+ df_chain->local_flags = (unsigned int)chain_flags;
+ df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
}
+#undef df_chain_problem_p
+\f
/*----------------------------------------------------------------------------
- REGISTER INFORMATION
+ This pass computes REG_DEAD and REG_UNUSED notes.
+ ----------------------------------------------------------------------------*/
+
+static void
+df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
+{
+ df_note->optional_p = true;
+}
+
+#ifdef REG_DEAD_DEBUGGING
+static void
+df_print_note (const char *prefix, rtx insn, rtx note)
+{
+ if (dump_file)
+ {
+ fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
+ print_rtl (dump_file, note);
+ fprintf (dump_file, "\n");
+ }
+}
+#endif
- Currently this consists of only lifetime information. But the plan is
- to enhance it so that it produces all of the register information needed
- by the register allocators.
-----------------------------------------------------------------------------*/
+/* 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. */
-struct df_ri_problem_data
+#ifdef STACK_REGS
+static inline bool
+df_ignore_stack_reg (int regno)
{
- int *lifetime;
-};
+ return regstack_completed
+ && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
+}
+#else
+static inline bool
+df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
+{
+ return false;
+}
+#endif
-/* Allocate the lifetime information. */
+/* Remove all of the REG_DEAD or REG_UNUSED notes from INSN and add
+ them to OLD_DEAD_NOTES and OLD_UNUSED_NOTES. */
-static void
-df_ri_alloc (struct dataflow *dflow, bitmap blocks_to_rescan ATTRIBUTE_UNUSED)
+static void
+df_kill_notes (rtx insn, rtx *old_dead_notes, rtx *old_unused_notes)
{
- struct df_ri_problem_data *problem_data =
- (struct df_ri_problem_data *) dflow->problem_data;
+ rtx *pprev = ®_NOTES (insn);
+ rtx link = *pprev;
+ rtx dead = NULL;
+ rtx unused = NULL;
- if (!dflow->problem_data)
+ while (link)
{
- struct df_ri_problem_data *problem_data =
- xmalloc (sizeof (struct df_ri_problem_data));
- dflow->problem_data = problem_data;
+ switch (REG_NOTE_KIND (link))
+ {
+ case REG_DEAD:
+ /* After reg-stack, we need to ignore any unused notes
+ for the stack registers. */
+ if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
+ {
+ pprev = &XEXP (link, 1);
+ link = *pprev;
+ }
+ else
+ {
+ rtx next = XEXP (link, 1);
+#ifdef REG_DEAD_DEBUGGING
+ df_print_note ("deleting: ", insn, link);
+#endif
+ XEXP (link, 1) = dead;
+ dead = link;
+ *pprev = link = next;
+ }
+ break;
+
+ case REG_UNUSED:
+ /* After reg-stack, we need to ignore any unused notes
+ for the stack registers. */
+ if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
+ {
+ pprev = &XEXP (link, 1);
+ link = *pprev;
+ }
+ else
+ {
+ rtx next = XEXP (link, 1);
+#ifdef REG_DEAD_DEBUGGING
+ df_print_note ("deleting: ", insn, link);
+#endif
+ XEXP (link, 1) = unused;
+ unused = link;
+ *pprev = link = next;
+ }
+ break;
+
+ default:
+ pprev = &XEXP (link, 1);
+ link = *pprev;
+ break;
+ }
}
- problem_data->lifetime = xrealloc (problem_data->lifetime,
- max_reg_num () *sizeof (int));
- memset (problem_data->lifetime, 0, max_reg_num () *sizeof (int));
+ *old_dead_notes = dead;
+ *old_unused_notes = unused;
}
-/* Compute register info: lifetime, bb, and number of defs and uses
- for basic block BB. */
+
+/* Set a NOTE_TYPE note for REG in INSN. Try to pull it from the OLD
+ list, otherwise create a new one. */
+
+static inline rtx
+df_set_note (enum reg_note note_type, rtx insn, rtx old, rtx reg)
+{
+ rtx this = old;
+ rtx prev = NULL;
+
+ while (this)
+ if (XEXP (this, 0) == reg)
+ {
+ if (prev)
+ XEXP (prev, 1) = XEXP (this, 1);
+ else
+ old = XEXP (this, 1);
+ XEXP (this, 1) = REG_NOTES (insn);
+ REG_NOTES (insn) = this;
+ return old;
+ }
+ else
+ {
+ prev = this;
+ this = XEXP (this, 1);
+ }
+
+ /* Did not find the note. */
+ REG_NOTES (insn) = alloc_EXPR_LIST (note_type, reg, REG_NOTES (insn));
+ return old;
+}
+
+/* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
+ based on the bits in LIVE. Do not generate notes for registers in
+ artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are
+ not generated if the reg is both read and written by the
+ instruction.
+*/
+
+static rtx
+df_set_unused_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
+ bitmap live, bitmap do_not_gen,
+ bitmap artificial_uses)
+{
+ bool all_dead = true;
+ unsigned int r;
+
+#ifdef REG_DEAD_DEBUGGING
+ if (dump_file)
+ fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
+ mws->start_regno, mws->end_regno);
+#endif
+ for (r=mws->start_regno; r <= mws->end_regno; r++)
+ if ((bitmap_bit_p (live, r))
+ || bitmap_bit_p (artificial_uses, r))
+ {
+ all_dead = false;
+ break;
+ }
+
+ if (all_dead)
+ {
+ unsigned int regno = mws->start_regno;
+ old = df_set_note (REG_UNUSED, insn, old, *(mws->loc));
+
+#ifdef REG_DEAD_DEBUGGING
+ df_print_note ("adding 1: ", insn, REG_NOTES (insn));
+#endif
+ bitmap_set_bit (do_not_gen, regno);
+ /* Only do this if the value is totally dead. */
+ }
+ else
+ for (r = mws->start_regno; r <= mws->end_regno; r++)
+ {
+ if (!bitmap_bit_p (live, r)
+ && !bitmap_bit_p (artificial_uses, r))
+ {
+ old = df_set_note (REG_UNUSED, insn, old, regno_reg_rtx[r]);
+#ifdef REG_DEAD_DEBUGGING
+ df_print_note ("adding 2: ", insn, REG_NOTES (insn));
+#endif
+ }
+ bitmap_set_bit (do_not_gen, r);
+ }
+ return old;
+}
+
+
+/* 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 rtx
+df_set_dead_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
+ bitmap live, bitmap do_not_gen,
+ bitmap artificial_uses)
+{
+ bool all_dead = true;
+ unsigned int r;
+
+#ifdef REG_DEAD_DEBUGGING
+ if (dump_file)
+ {
+ fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n do_not_gen =",
+ mws->start_regno, mws->end_regno);
+ df_print_regset (dump_file, do_not_gen);
+ fprintf (dump_file, " live =");
+ df_print_regset (dump_file, live);
+ fprintf (dump_file, " artificial uses =");
+ df_print_regset (dump_file, artificial_uses);
+ }
+#endif
+
+ for (r = mws->start_regno; r <= mws->end_regno; r++)
+ if ((bitmap_bit_p (live, r))
+ || bitmap_bit_p (artificial_uses, r)
+ || bitmap_bit_p (do_not_gen, r))
+ {
+ all_dead = false;
+ break;
+ }
+
+ if (all_dead)
+ {
+ if (!bitmap_bit_p (do_not_gen, mws->start_regno))
+ {
+ /* Add a dead note for the entire multi word register. */
+ old = df_set_note (REG_DEAD, insn, old, *(mws->loc));
+#ifdef REG_DEAD_DEBUGGING
+ df_print_note ("adding 1: ", insn, REG_NOTES (insn));
+#endif
+ }
+ }
+ else
+ {
+ for (r = mws->start_regno; r <= mws->end_regno; r++)
+ if (!bitmap_bit_p (live, r)
+ && !bitmap_bit_p (artificial_uses, r)
+ && !bitmap_bit_p (do_not_gen, r))
+ {
+ old = df_set_note (REG_DEAD, insn, old, regno_reg_rtx[r]);
+#ifdef REG_DEAD_DEBUGGING
+ df_print_note ("adding 2: ", insn, REG_NOTES (insn));
+#endif
+ }
+ }
+ return old;
+}
+
+
+/* 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 rtx
+df_create_unused_note (rtx insn, rtx old, struct df_ref *def,
+ bitmap live, bitmap do_not_gen, bitmap artificial_uses)
+{
+ unsigned int dregno = DF_REF_REGNO (def);
+
+#ifdef REG_DEAD_DEBUGGING
+ if (dump_file)
+ {
+ fprintf (dump_file, " regular looking at def ");
+ df_ref_debug (def, dump_file);
+ }
+#endif
+
+ if (!(bitmap_bit_p (live, dregno)
+ || (DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
+ || bitmap_bit_p (artificial_uses, dregno)
+ || df_ignore_stack_reg (dregno)))
+ {
+ rtx reg = (DF_REF_LOC (def))
+ ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
+ old = df_set_note (REG_UNUSED, insn, old, reg);
+#ifdef REG_DEAD_DEBUGGING
+ df_print_note ("adding 3: ", insn, REG_NOTES (insn));
+#endif
+ }
+
+ 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 or conditional store. */
+ if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
+ bitmap_clear_bit (live, dregno);
+ return old;
+}
+
+
+/* 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)
+df_note_bb_compute (unsigned int bb_index,
+ bitmap live, bitmap do_not_gen, bitmap artificial_uses)
{
- struct df *df = dflow->df;
- struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index);
- struct df_ri_problem_data *problem_data =
- (struct df_ri_problem_data *) dflow->problem_data;
basic_block bb = BASIC_BLOCK (bb_index);
rtx insn;
+ struct df_ref **def_rec;
+ struct df_ref **use_rec;
- bitmap_copy (live, bb_info->out);
+ bitmap_copy (live, df_get_live_out (bb));
+ bitmap_clear (artificial_uses);
+
+#ifdef REG_DEAD_DEBUGGING
+ if (dump_file)
+ {
+ fprintf (dump_file, "live at bottom ");
+ df_print_regset (dump_file, live);
+ }
+#endif
+
+ /* Process the artificial defs and uses at the bottom of the block
+ to begin processing. */
+ for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
+ {
+ struct df_ref *def = *def_rec;
+#ifdef REG_DEAD_DEBUGGING
+ if (dump_file)
+ fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
+#endif
+
+ if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
+ bitmap_clear_bit (live, DF_REF_REGNO (def));
+ }
+
+ for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
+ {
+ struct df_ref *use = *use_rec;
+ if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
+ {
+ unsigned int regno = DF_REF_REGNO (use);
+ bitmap_set_bit (live, regno);
+
+ /* Notes are not generated for any of the artificial registers
+ at the bottom of the block. */
+ bitmap_set_bit (artificial_uses, regno);
+ }
+ }
+
+#ifdef REG_DEAD_DEBUGGING
+ if (dump_file)
+ {
+ fprintf (dump_file, "live before artificials out ");
+ df_print_regset (dump_file, live);
+ }
+#endif
FOR_BB_INSNS_REVERSE (bb, insn)
{
unsigned int uid = INSN_UID (insn);
- unsigned int regno;
- bitmap_iterator bi;
- struct df_ref *def;
- struct df_ref *use;
-
- if (! INSN_P (insn))
+ struct df_mw_hardreg **mws_rec;
+ rtx old_dead_notes;
+ rtx old_unused_notes;
+
+ if (!INSN_P (insn))
continue;
- for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
+ bitmap_clear (do_not_gen);
+ df_kill_notes (insn, &old_dead_notes, &old_unused_notes);
+
+ /* Process the defs. */
+ if (CALL_P (insn))
{
- unsigned int dregno = DF_REF_REGNO (def);
+#ifdef REG_DEAD_DEBUGGING
+ if (dump_file)
+ {
+ fprintf (dump_file, "processing call %d\n live =", INSN_UID (insn));
+ df_print_regset (dump_file, live);
+ }
+#endif
+ /* We only care about real sets for calls. Clobbers cannot
+ be depended on to really die. */
+ mws_rec = DF_INSN_UID_MWS (uid);
+ while (*mws_rec)
+ {
+ struct df_mw_hardreg *mws = *mws_rec;
+ if ((mws->type == DF_REF_REG_DEF)
+ && !df_ignore_stack_reg (REGNO (mws->mw_reg)))
+ old_unused_notes
+ = df_set_unused_notes_for_mw (insn, old_unused_notes,
+ mws, live, do_not_gen,
+ artificial_uses);
+ mws_rec++;
+ }
- /* Kill this register. */
- bitmap_clear_bit (live, dregno);
+ /* All of the defs except the return value are some sort of
+ clobber. This code is for the return. */
+ for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+ {
+ struct df_ref *def = *def_rec;
+ if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
+ old_unused_notes
+ = df_create_unused_note (insn, old_unused_notes,
+ def, live, do_not_gen,
+ artificial_uses);
+
+ /* However a may or must clobber still needs to kill the
+ reg so that REG_DEAD notes are later placed
+ appropriately. */
+ else
+ bitmap_clear_bit (live, DF_REF_REGNO (def));
+ }
}
+ else
+ {
+ /* Regular insn. */
+ mws_rec = DF_INSN_UID_MWS (uid);
+ while (*mws_rec)
+ {
+ struct df_mw_hardreg *mws = *mws_rec;
+ if (mws->type == DF_REF_REG_DEF)
+ old_unused_notes
+ = df_set_unused_notes_for_mw (insn, old_unused_notes,
+ mws, live, do_not_gen,
+ artificial_uses);
+ mws_rec++;
+ }
- for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
+ for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+ {
+ struct df_ref *def = *def_rec;
+ old_unused_notes
+ = df_create_unused_note (insn, old_unused_notes,
+ def, live, do_not_gen,
+ artificial_uses);
+ }
+ }
+
+ /* Process the uses. */
+ mws_rec = DF_INSN_UID_MWS (uid);
+ while (*mws_rec)
{
+ struct df_mw_hardreg *mws = *mws_rec;
+ if ((mws->type != DF_REF_REG_DEF)
+ && !df_ignore_stack_reg (REGNO (mws->mw_reg)))
+ old_dead_notes
+ = df_set_dead_notes_for_mw (insn, old_dead_notes,
+ mws, live, do_not_gen,
+ artificial_uses);
+ mws_rec++;
+ }
+
+ for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
+ {
+ struct df_ref *use = *use_rec;
unsigned int uregno = DF_REF_REGNO (use);
- /* This register is now live. */
- bitmap_set_bit (live, uregno);
+#ifdef REG_DEAD_DEBUGGING
+ if (dump_file)
+ {
+ fprintf (dump_file, " regular looking at use ");
+ df_ref_debug (use, dump_file);
+ }
+#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 = (DF_REF_LOC (use))
+ ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
+ old_dead_notes = df_set_note (REG_DEAD, insn, old_dead_notes, reg);
+
+#ifdef REG_DEAD_DEBUGGING
+ df_print_note ("adding 4: ", insn, REG_NOTES (insn));
+#endif
+ }
+ /* This register is now live. */
+ bitmap_set_bit (live, uregno);
+ }
}
- /* Increment lifetimes of all live registers. */
- EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
+ while (old_unused_notes)
+ {
+ rtx next = XEXP (old_unused_notes, 1);
+ free_EXPR_LIST_node (old_unused_notes);
+ old_unused_notes = next;
+ }
+ while (old_dead_notes)
{
- problem_data->lifetime[regno]++;
+ rtx next = XEXP (old_dead_notes, 1);
+ free_EXPR_LIST_node (old_dead_notes);
+ old_dead_notes = next;
}
}
}
/* Compute register info: lifetime, bb, and number of defs and uses. */
static void
-df_ri_compute (struct dataflow *dflow, bitmap all_blocks ATTRIBUTE_UNUSED,
- bitmap blocks_to_scan)
+df_note_compute (bitmap all_blocks)
{
unsigned int bb_index;
bitmap_iterator bi;
- bitmap live;
+ bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
+ bitmap do_not_gen = BITMAP_ALLOC (&df_bitmap_obstack);
+ bitmap artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
- live = BITMAP_ALLOC (NULL);
+#ifdef REG_DEAD_DEBUGGING
+ if (dump_file)
+ print_rtl_with_bb (dump_file, get_insns());
+#endif
- EXECUTE_IF_SET_IN_BITMAP (blocks_to_scan, 0, bb_index, bi)
+ EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
- df_ri_bb_compute (dflow, bb_index, live);
+ df_note_bb_compute (bb_index, live, do_not_gen, artificial_uses);
}
BITMAP_FREE (live);
+ BITMAP_FREE (do_not_gen);
+ BITMAP_FREE (artificial_uses);
}
/* Free all storage associated with the problem. */
static void
-df_ri_free (struct dataflow *dflow)
+df_note_free (void)
{
- struct df_ri_problem_data *problem_data =
- (struct df_ri_problem_data *) dflow->problem_data;
-
- free (problem_data->lifetime);
- free (dflow->problem_data);
- free (dflow);
+ free (df_note);
}
-/* Debugging info. */
-
-static void
-df_ri_dump (struct dataflow *dflow, FILE *file)
-{
- struct df_ri_problem_data *problem_data =
- (struct df_ri_problem_data *) dflow->problem_data;
- int j;
-
- fprintf (file, "Register info:\n");
- for (j = 0; j < max_reg_num (); j++)
- {
- fprintf (file, "reg %d life %d\n", j, problem_data->lifetime[j]);
- }
-}
-
/* All of the information associated every instance of the problem. */
-static struct df_problem problem_RI =
+static struct df_problem problem_NOTE =
{
- DF_RI, /* Problem id. */
+ DF_NOTE, /* Problem id. */
DF_NONE, /* Direction. */
- df_ri_alloc, /* Allocate the problem specific data. */
+ df_note_alloc, /* Allocate the problem specific data. */
+ NULL, /* Reset global information. */
NULL, /* Free basic block info. */
- df_ri_compute, /* Local compute function. */
+ df_note_compute, /* Local compute function. */
NULL, /* Init the solution specific data. */
NULL, /* Iterative solver. */
NULL, /* Confluence operator 0. */
NULL, /* Confluence operator n. */
NULL, /* Transfer function. */
NULL, /* Finalize function. */
- df_ri_free, /* Free all of the problem information. */
- df_ri_dump, /* Debugging. */
- &problem_UR /* Dependent problem. */
+ df_note_free, /* Free all of the problem information. */
+ df_note_free, /* Remove this problem from the stack of dataflow problems. */
+ NULL, /* Debugging. */
+ NULL, /* Debugging start block. */
+ NULL, /* Debugging end block. */
+ NULL, /* Incremental solution verify start. */
+ NULL, /* Incremental solution verify end. */
+
+ /* 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. */
+ &problem_LR, /* Dependent problem. */
+ TV_DF_NOTE, /* Timing variable. */
+ false /* Reset blocks on dropping out of blocks_to_analyze. */
};
of DF. The returned structure is what is used to get at the
solution. */
-struct dataflow *
-df_ri_add_problem (struct df *df)
+void
+df_note_add_problem (void)
+{
+ df_add_problem (&problem_NOTE);
+}
+
+
+
+\f
+/*----------------------------------------------------------------------------
+ Functions for simulating the effects of single insns.
+
+ You can either simulate in the forwards direction, starting from
+ the top of a block or the backwards direction from the end of the
+ block. The main difference is that if you go forwards, the uses
+ are examined first then the defs, and if you go backwards, the defs
+ are examined first then the uses.
+
+ If you start at the top of the block, use one of DF_LIVE_IN or
+ DF_LR_IN. If you start at the bottom of the block use one of
+ DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS,
+ THEY WILL BE DESTROYED.
+
+----------------------------------------------------------------------------*/
+
+
+/* Find the set of DEFs for INSN. */
+
+void
+df_simulate_find_defs (rtx insn, bitmap defs)
+{
+ struct df_ref **def_rec;
+ unsigned int uid = INSN_UID (insn);
+
+ if (CALL_P (insn))
+ {
+ for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+ {
+ struct df_ref *def = *def_rec;
+ unsigned int dregno = DF_REF_REGNO (def);
+
+ if (DF_REF_FLAGS (def) & DF_REF_MUST_CLOBBER)
+ {
+ 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 | DF_REF_CONDITIONAL)))
+ bitmap_set_bit (defs, dregno);
+ }
+ }
+ else
+ /* This is the return value. */
+ if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
+ bitmap_set_bit (defs, dregno);
+ }
+ }
+ else
+ {
+ for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+ {
+ struct df_ref *def = *def_rec;
+ /* If the def is to only part of the reg, it does
+ not kill the other defs that reach here. */
+ if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
+ bitmap_set_bit (defs, DF_REF_REGNO (def));
+ }
+ }
+}
+
+
+/* Simulate the effects of the defs of INSN on LIVE. */
+
+void
+df_simulate_defs (rtx insn, bitmap live)
{
- return df_add_problem (df, &problem_RI);
+ struct df_ref **def_rec;
+ unsigned int uid = INSN_UID (insn);
+
+ if (CALL_P (insn))
+ {
+ for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+ {
+ struct df_ref *def = *def_rec;
+ unsigned int dregno = DF_REF_REGNO (def);
+
+ if (DF_REF_FLAGS (def) & DF_REF_MUST_CLOBBER)
+ {
+ 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 | DF_REF_CONDITIONAL)))
+ bitmap_clear_bit (live, dregno);
+ }
+ }
+ else
+ /* This is the return value. */
+ if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
+ bitmap_clear_bit (live, dregno);
+ }
+ }
+ else
+ {
+ for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+ {
+ struct df_ref *def = *def_rec;
+ unsigned int dregno = DF_REF_REGNO (def);
+
+ /* If the def is to only part of the reg, it does
+ not kill the other defs that reach here. */
+ if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
+ bitmap_clear_bit (live, dregno);
+ }
+ }
+}
+
+
+/* Simulate the effects of the uses of INSN on LIVE. */
+
+void
+df_simulate_uses (rtx insn, bitmap live)
+{
+ struct df_ref **use_rec;
+ unsigned int uid = INSN_UID (insn);
+
+ for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
+ {
+ struct df_ref *use = *use_rec;
+ /* Add use to set of uses in this BB. */
+ bitmap_set_bit (live, DF_REF_REGNO (use));
+ }
+}
+
+
+/* Add back the always live regs in BB to LIVE. */
+
+static inline void
+df_simulate_fixup_sets (basic_block bb, bitmap live)
+{
+ /* These regs are considered always live so if they end up dying
+ because of some def, we need to bring the back again. */
+ if (df_has_eh_preds (bb))
+ bitmap_ior_into (live, df->eh_block_artificial_uses);
+ else
+ bitmap_ior_into (live, df->regular_block_artificial_uses);
+}
+
+
+/* Apply the artificial uses and defs at the top of BB in a forwards
+ direction. */
+
+void
+df_simulate_artificial_refs_at_top (basic_block bb, bitmap live)
+{
+ struct df_ref **def_rec;
+ struct df_ref **use_rec;
+ int bb_index = bb->index;
+
+ for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
+ {
+ struct df_ref *use = *use_rec;
+ if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
+ bitmap_set_bit (live, DF_REF_REGNO (use));
+ }
+
+ for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
+ {
+ struct df_ref *def = *def_rec;
+ if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
+ bitmap_clear_bit (live, DF_REF_REGNO (def));
+ }
+}
+
+
+/* Simulate the forwards effects of INSN on the bitmap LIVE. */
+
+void
+df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live)
+{
+ if (! INSN_P (insn))
+ return;
+
+ df_simulate_uses (insn, live);
+ df_simulate_defs (insn, live);
+ df_simulate_fixup_sets (bb, live);
}
-/* Return total lifetime (in insns) of REG. */
-int
-df_reg_lifetime (struct df *df, rtx reg)
+/* Apply the artificial uses and defs at the end of BB in a backwards
+ direction. */
+
+void
+df_simulate_artificial_refs_at_end (basic_block bb, bitmap live)
{
- struct dataflow *dflow = df->problems_by_index[DF_RI];
- struct df_ri_problem_data *problem_data =
- (struct df_ri_problem_data *) dflow->problem_data;
- return problem_data->lifetime[REGNO (reg)];
+ struct df_ref **def_rec;
+ struct df_ref **use_rec;
+ int bb_index = bb->index;
+
+ for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
+ {
+ struct df_ref *def = *def_rec;
+ if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
+ bitmap_clear_bit (live, DF_REF_REGNO (def));
+ }
+
+ for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
+ {
+ struct df_ref *use = *use_rec;
+ if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
+ bitmap_set_bit (live, DF_REF_REGNO (use));
+ }
+}
+
+
+/* Simulate the backwards effects of INSN on the bitmap LIVE. */
+
+void
+df_simulate_one_insn_backwards (basic_block bb, rtx insn, bitmap live)
+{
+ if (! INSN_P (insn))
+ return;
+
+ df_simulate_defs (insn, live);
+ df_simulate_uses (insn, live);
+ df_simulate_fixup_sets (bb, live);
}