#include "bitmap.h"
#include "timevar.h"
#include "df.h"
+#include "vecprim.h"
+#include "except.h"
+
+#if 0
+#define REG_DEAD_DEBUGGING
+#endif
#define DF_SPARSE_THRESHOLD 32
static bitmap seen_in_block = NULL;
static bitmap seen_in_insn = NULL;
+static void df_ri_dump (struct dataflow *, FILE *);
\f
/*----------------------------------------------------------------------------
Public functions access functions for the dataflow problems.
----------------------------------------------------------------------------*/
-/* Get the instance of the problem that DFLOW is dependent on. */
-
-struct dataflow *
-df_get_dependent_problem (struct dataflow *dflow)
-{
- struct df *df = dflow->df;
- struct df_problem *dependent_problem = dflow->problem->dependent_problem;
-
- gcc_assert (dependent_problem);
- return df->problems_by_index[dependent_problem->id];
-}
-
-
/* Create a du or ud chain from SRC to DST and link it into SRC. */
struct df_link *
----------------------------------------------------------------------------*/
/* 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)
}
-/* Return the set of reference ids in CHAIN, caching the result in *BMAP. */
+/* Return a bitmap for REGNO from the cache MAPS. The bitmap is to
+ contain COUNT bits starting at START. These bitmaps are not to be
+ changed since there is a cache of them. */
static inline bitmap
df_ref_bitmap (bitmap *maps, unsigned int regno, int start, int count)
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.
+
+ <= : There is a bitmap for each register, uses_sites[N], that is
+ built on demand. This bitvector contains a 1 for each use or reg
+ N.
+
+ > : One level of indirection is used to keep from generating long
+ strings of 1 bits in the kill sets. Bitvectors that are indexed
+ by the regnum are used to represent that there is a killing def
+ for the register. The confluence and transfer functions use
+ these along with the bitmap_clear_range call to remove ranges of
+ bits without actually generating a knockout vector.
+
+ The kill and sparse_kill and the dense_invalidated_by_call and
+ sparse_invalidated_by call both play this game. */
+
+/* Private data used to compute the solution for this problem. These
+ data structures are not accessible outside of this module. */
struct df_ru_problem_data
{
+
bitmap *use_sites; /* Bitmap of uses for each pseudo. */
unsigned int use_sites_size; /* Size of use_sites. */
/* The set of defs to regs invalidated by call. */
not touched unless the block is new. */
static void
-df_ru_alloc (struct dataflow *dflow, bitmap blocks_to_rescan)
+df_ru_alloc (struct dataflow *dflow,
+ bitmap blocks_to_rescan ATTRIBUTE_UNUSED,
+ bitmap all_blocks)
{
unsigned int bb_index;
bitmap_iterator bi;
unsigned int reg_size = max_reg_num ();
- if (! dflow->block_pool)
+ if (!dflow->block_pool)
dflow->block_pool = create_alloc_pool ("df_ru_block pool",
sizeof (struct df_ru_bb_info), 50);
if (dflow->problem_data)
{
unsigned int i;
- struct df_ru_problem_data *problem_data =
- (struct df_ru_problem_data *) dflow->problem_data;
+ 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++)
{
we have to process all of the blocks before doing the
analysis. */
- EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi)
+ EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb_index);
if (bb_info)
struct df *df = dflow->df;
while (def)
{
- if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
+ if ((top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
+ /* If the def is to only part of the reg, it is as if it did
+ not happen, since some of the bits may get thru. */
+ && (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL)))
{
unsigned int regno = DF_REF_REGNO (def);
unsigned int begin = DF_REG_USE_GET (df, regno)->begin;
unsigned int n_uses = DF_REG_USE_GET (df, regno)->n_refs;
if (!bitmap_bit_p (seen_in_block, regno))
{
- /* The first def for regno, causes the kill info to be
- generated and the gen information to cleared. */
+ /* The first def for regno in the insn, causes the kill
+ info to be generated. Do not modify the gen set
+ because the only values in it are the uses from here
+ to the top of the block and this def does not effect
+ them. */
if (!bitmap_bit_p (seen_in_insn, regno))
{
if (n_uses > DF_SPARSE_THRESHOLD)
- {
- bitmap_set_bit (bb_info->sparse_kill, regno);
- bitmap_clear_range (bb_info->gen, begin, n_uses);
- }
+ bitmap_set_bit (bb_info->sparse_kill, regno);
else
{
- struct df_ru_problem_data * problem_data =
- (struct df_ru_problem_data *)dflow->problem_data;
- bitmap uses =
- df_ref_bitmap (problem_data->use_sites, regno,
+ struct df_ru_problem_data * problem_data
+ = (struct df_ru_problem_data *)dflow->problem_data;
+ bitmap uses
+ = df_ref_bitmap (problem_data->use_sites, regno,
begin, n_uses);
bitmap_ior_into (bb_info->kill, uses);
- bitmap_and_compl_into (bb_info->gen, uses);
}
}
bitmap_set_bit (seen_in_insn, regno);
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, 0);
-
- /* 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 (df, uid), 0);
+
+ df_ru_bb_local_compute_process_def (dflow, bb_info,
+ DF_INSN_UID_DEFS (df, uid), 0);
bitmap_ior_into (seen_in_block, seen_in_insn);
bitmap_clear (seen_in_insn);
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 *) dflow->problem_data;
bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
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 *) dflow->problem_data;
bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
struct df *df = dflow->df;
struct df *df = dflow->df;
bool changed = false;
bitmap tmp = BITMAP_ALLOC (NULL);
- bitmap_copy (tmp, in);
+ bitmap_copy (tmp, out);
EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
{
bitmap_clear_range (tmp,
changed = !bitmap_equal_p (tmp, in);
if (changed)
{
- BITMAP_FREE (out);
+ BITMAP_FREE (in);
bb_info->in = tmp;
}
else
df_ru_free (struct dataflow *dflow)
{
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 *) dflow->problem_data;
if (problem_data)
{
{
basic_block bb;
struct df *df = dflow->df;
- 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 *) dflow->problem_data;
unsigned int m = max_reg_num ();
unsigned int regno;
+
+ if (!dflow->block_info)
+ return;
fprintf (file, "Reaching uses:\n");
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)
+ if (!bb_info->in)
continue;
- fprintf (file, " in \t");
+ fprintf (file, " in \t(%d)\n", (int) bitmap_count_bits (bb_info->in));
dump_bitmap (file, bb_info->in);
- fprintf (file, " gen \t");
+ fprintf (file, " gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen));
dump_bitmap (file, bb_info->gen);
- fprintf (file, " kill\t");
+ fprintf (file, " kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill));
dump_bitmap (file, bb_info->kill);
- fprintf (file, " out \t");
+ fprintf (file, " out \t(%d)\n", (int) bitmap_count_bits (bb_info->out));
dump_bitmap (file, bb_info->out);
}
}
NULL, /* Finalize function. */
df_ru_free, /* Free all of the problem information. */
df_ru_dump, /* Debugging. */
- NULL /* Dependent problem. */
+ NULL, /* Dependent problem. */
+ 0 /* Changeable flags. */
};
solution. */
struct dataflow *
-df_ru_add_problem (struct df *df)
+df_ru_add_problem (struct df *df, int flags)
{
- return df_add_problem (df, &problem_RU);
+ return df_add_problem (df, &problem_RU, flags);
}
\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
{
+ /* If the number of defs for regnum N is less than
+ DF_SPARSE_THRESHOLD, uses_sites[N] contains a mask of the all of
+ the defs of reg N indexed by the id in the ref structure. If
+ there are more than DF_SPARSE_THRESHOLD defs for regnum N a
+ different mechanism is used to mask the def. */
bitmap *def_sites; /* Bitmap of defs for each pseudo. */
unsigned int def_sites_size; /* Size of def_sites. */
/* The set of defs to regs invalidated by call. */
bitmap sparse_invalidated_by_call;
- /* The set of defs to regs invalidate by call for ru. */
+ /* The set of defs to regs invalidate by call for rd. */
bitmap dense_invalidated_by_call;
};
not touched unless the block is new. */
static void
-df_rd_alloc (struct dataflow *dflow, bitmap blocks_to_rescan)
+df_rd_alloc (struct dataflow *dflow,
+ bitmap blocks_to_rescan ATTRIBUTE_UNUSED,
+ bitmap all_blocks)
{
unsigned int bb_index;
bitmap_iterator bi;
unsigned int reg_size = max_reg_num ();
- if (! dflow->block_pool)
+ if (!dflow->block_pool)
dflow->block_pool = create_alloc_pool ("df_rd_block pool",
sizeof (struct df_rd_bb_info), 50);
if (dflow->problem_data)
{
unsigned int i;
- struct df_rd_problem_data *problem_data =
- (struct df_rd_problem_data *) dflow->problem_data;
+ 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++)
{
df_grow_bb_info (dflow);
- /* 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);
if (bb_info)
{
/* 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 ((!bitmap_bit_p (seen_in_insn, regno))
+ /* If the def is to only part of the reg, it does
+ not kill the other defs that reach here. */
+ && (!((DF_REF_FLAGS (def) & DF_REF_PARTIAL)
+ || (DF_REF_FLAGS (def) & DF_REF_MAY_CLOBBER))))
{
if (n_defs > DF_SPARSE_THRESHOLD)
{
}
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);
+ struct df_rd_problem_data * problem_data
+ = (struct df_rd_problem_data *)dflow->problem_data;
+ bitmap defs = df_ref_bitmap (problem_data->def_sites,
+ regno, begin, n_defs);
bitmap_ior_into (bb_info->kill, defs);
bitmap_and_compl_into (bb_info->gen, defs);
}
bitmap_set_bit (seen_in_insn, regno);
/* All defs for regno in the instruction may be put into
the gen set. */
- if (! (DF_REF_FLAGS (def) & DF_REF_CLOBBER))
+ if (!(DF_REF_FLAGS (def)
+ & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
bitmap_set_bit (bb_info->gen, DF_REF_ID (def));
}
}
{
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, 0);
+ DF_INSN_UID_DEFS (df, uid), 0);
/* This complex dance with the two bitmaps is required because
instructions can assign twice to the same pseudo. This
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 *) dflow->problem_data;
bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
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 *) dflow->problem_data;
bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
struct df *df = dflow->df;
df_rd_free (struct dataflow *dflow)
{
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 *) dflow->problem_data;
if (problem_data)
{
{
struct df *df = dflow->df;
basic_block bb;
- 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 *) dflow->problem_data;
unsigned int m = max_reg_num ();
unsigned int regno;
+ if (!dflow->block_info)
+ return;
+
fprintf (file, "Reaching defs:\n\n");
fprintf (file, " sparse invalidated \t");
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)
+ if (!bb_info->in)
continue;
- fprintf (file, " in\t(%d)\n", (int) bitmap_count_bits (bb_info->in));
+ 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));
+ fprintf (file, " out \t(%d)\n", (int) bitmap_count_bits (bb_info->out));
dump_bitmap (file, bb_info->out);
}
}
NULL, /* Finalize function. */
df_rd_free, /* Free all of the problem information. */
df_rd_dump, /* Debugging. */
- NULL /* Dependent problem. */
+ NULL, /* Dependent problem. */
+ 0 /* Changeable flags. */
};
solution. */
struct dataflow *
-df_rd_add_problem (struct df *df)
+df_rd_add_problem (struct df *df, int flags)
{
- return df_add_problem (df, &problem_RD);
+ return df_add_problem (df, &problem_RD, flags);
}
/*----------------------------------------------------------------------------
LIVE REGISTERS
- Find the locations in the function where any use of a pseudo can reach
- in the backwards direction.
-----------------------------------------------------------------------------*/
+ Find the locations in the function where any use of a pseudo can
+ reach in the backwards direction. In and out bitvectors are built
+ for each basic block. The regnum is used to index into these sets.
+ See df.h for details.
+ ----------------------------------------------------------------------------*/
/* Get basic block info. */
not touched unless the block is new. */
static void
-df_lr_alloc (struct dataflow *dflow, bitmap blocks_to_rescan)
+df_lr_alloc (struct dataflow *dflow, bitmap blocks_to_rescan,
+ bitmap all_blocks ATTRIBUTE_UNUSED)
{
unsigned int bb_index;
bitmap_iterator bi;
- if (! dflow->block_pool)
+ if (!dflow->block_pool)
dflow->block_pool = create_alloc_pool ("df_lr_block pool",
sizeof (struct df_lr_bb_info), 50);
df_grow_bb_info (dflow);
- /* 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)
{
struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb_index);
/* Process the registers set in an exception handler. */
for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref)
- if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
+ if (((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
+ && (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL)))
{
unsigned int dregno = DF_REF_REGNO (def);
bitmap_set_bit (bb_info->def, dregno);
{
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 = DF_INSN_UID_DEFS (df, uid); def; def = def->next_ref)
{
unsigned int dregno = DF_REF_REGNO (def);
current_function_return_rtx,
(rtx *)0)))
{
- /* Add def to set of defs in this BB. */
- bitmap_set_bit (bb_info->def, dregno);
- bitmap_clear_bit (bb_info->use, dregno);
+ /* If the def is to only part of the reg, it does
+ not kill the other defs that reach here. */
+ if (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL))
+ {
+ bitmap_set_bit (bb_info->def, dregno);
+ bitmap_clear_bit (bb_info->use, dregno);
+ }
}
}
}
else
{
- for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
+ for (def = DF_INSN_UID_DEFS (df, uid); def; def = def->next_ref)
{
unsigned int dregno = DF_REF_REGNO (def);
&& dregno < FIRST_PSEUDO_REGISTER)
{
unsigned int i;
- unsigned int end =
- dregno + hard_regno_nregs[dregno][GET_MODE (DF_REF_REG (def))] - 1;
+ unsigned int end = dregno
+ + hard_regno_nregs[dregno][GET_MODE (DF_REF_REG (def))] - 1;
for (i = dregno; i <= end; ++i)
regs_asm_clobbered[i] = 1;
}
- /* Add def to set of defs in this BB. */
- bitmap_set_bit (bb_info->def, dregno);
- bitmap_clear_bit (bb_info->use, dregno);
+ /* If the def is to only part of the reg, it does
+ not kill the other defs that reach here. */
+ if (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL))
+ {
+ bitmap_set_bit (bb_info->def, dregno);
+ bitmap_clear_bit (bb_info->use, dregno);
+ }
}
}
- for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
+ for (use = DF_INSN_UID_USES (df, uid); use; use = use->next_ref)
/* Add use to set of uses in this BB. */
bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
}
/* Process the registers set in an exception handler. */
for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref)
- if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
+ if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP)
+ && (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL)))
{
unsigned int dregno = DF_REF_REGNO (def);
bitmap_set_bit (bb_info->def, dregno);
#endif
}
+
/* Compute local live register info for each basic block within BLOCKS. */
static void
/* 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. */
/* Confluence function that ignores fake edges. */
+
static void
df_lr_confluence_n (struct dataflow *dflow, edge e)
{
/* Transfer function. */
+
static bool
df_lr_transfer_function (struct dataflow *dflow, int bb_index)
{
dflow->block_info_size = 0;
free (dflow->block_info);
}
+
+ free (dflow->problem_data);
free (dflow);
}
{
basic_block bb;
+ if (!dflow->block_info)
+ return;
+
fprintf (file, "Live Registers:\n");
FOR_ALL_BB (bb)
{
NULL, /* Finalize function. */
df_lr_free, /* Free all of the problem information. */
df_lr_dump, /* Debugging. */
- NULL /* Dependent problem. */
+ NULL, /* Dependent problem. */
+ 0
};
solution. */
struct dataflow *
-df_lr_add_problem (struct df *df)
+df_lr_add_problem (struct df *df, int flags)
{
- return df_add_problem (df, &problem_LR);
+ return df_add_problem (df, &problem_LR, flags);
}
UNINITIALIZED REGISTERS
Find the set of uses for registers that are reachable from the entry
- block without passing thru a definition.
+ 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. */
not touched unless the block is new. */
static void
-df_ur_alloc (struct dataflow *dflow, bitmap blocks_to_rescan)
+df_ur_alloc (struct dataflow *dflow, bitmap blocks_to_rescan,
+ bitmap all_blocks ATTRIBUTE_UNUSED)
{
unsigned int bb_index;
bitmap_iterator bi;
- if (! dflow->block_pool)
+ 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);
- /* 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)
{
struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index);
if (!INSN_P (insn))
continue;
- for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
+ for (def = DF_INSN_UID_DEFS (df, uid); def; def = def->next_ref)
{
unsigned int regno = DF_REF_REGNO (def);
- /* Only the last def counts. */
+ /* 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);
+ if (DF_REF_FLAGS (def)
+ & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
+ {
+ /* Only must clobbers for the entire reg destroy the
+ value. */
+ if ((DF_REF_FLAGS (def) & DF_REF_MUST_CLOBBER)
+ && (!DF_REF_FLAGS (def) & DF_REF_PARTIAL))
+ bitmap_set_bit (bb_info->kill, regno);
+ }
else
bitmap_set_bit (bb_info->gen, regno);
}
bitmap_and_into (bb_info->out, tmp);
#endif
}
-
+
BITMAP_FREE (tmp);
}
{
basic_block bb;
+ if (!dflow->block_info)
+ return;
+
fprintf (file, "Undefined regs:\n");
FOR_ALL_BB (bb)
struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb->index);
df_print_bb_index (bb, file);
- if (! bb_info->in)
+ if (!bb_info->in)
continue;
fprintf (file, " in \t");
df_ur_local_finalize, /* Finalize function. */
df_ur_free, /* Free all of the problem information. */
df_ur_dump, /* Debugging. */
- &problem_LR /* Dependent problem. */
+ df_lr_add_problem, /* Dependent problem. */
+ 0 /* Changeable flags. */
};
solution. */
struct dataflow *
-df_ur_add_problem (struct df *df)
+df_ur_add_problem (struct df *df, int flags)
{
- return df_add_problem (df, &problem_UR);
+ return df_add_problem (df, &problem_UR, flags);
}
UNINITIALIZED REGISTERS WITH EARLYCLOBBER
Find the set of uses for registers that are reachable from the entry
- block without passing thru a definition.
+ 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 a away if someone would fix the interference graph.
+ ----------------------------------------------------------------------------*/
+
+/* Private data used to compute the solution for this problem. These
+ data structures are not accessible outside of this module. */
struct df_urec_problem_data
{
bool earlyclobbers_found; /* True if any instruction contains an
not touched unless the block is new. */
static void
-df_urec_alloc (struct dataflow *dflow, bitmap blocks_to_rescan)
+df_urec_alloc (struct dataflow *dflow, bitmap blocks_to_rescan,
+ bitmap all_blocks ATTRIBUTE_UNUSED)
+
{
unsigned int bb_index;
bitmap_iterator bi;
- struct df_urec_problem_data *problem_data =
- (struct df_urec_problem_data *) dflow->problem_data;
+ struct df_urec_problem_data *problem_data
+ = (struct df_urec_problem_data *) dflow->problem_data;
- if (! dflow->block_pool)
+ if (!dflow->block_pool)
dflow->block_pool = create_alloc_pool ("df_urec_block pool",
sizeof (struct df_urec_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. */
-
EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi)
{
struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index);
/* 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
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 *) dflow->problem_data;
problem_data->earlyclobbers_found = true;
note_uses (&PATTERN (insn),
df_urec_mark_reg_use_for_earlyclobber_1, bb_info);
#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;
+ struct df_urec_problem_data *problem_data
+ = (struct df_urec_problem_data *) dflow->problem_data;
/* Any register that MAY be allocated to a register stack (like the
387) is treated poorly. Each such register is marked as being
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 *) dflow->problem_data;
EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
{
basic_block bb;
+ if (!dflow->block_info)
+ return;
+
fprintf (file, "Undefined regs:\n");
FOR_ALL_BB (bb)
struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb->index);
df_print_bb_index (bb, file);
- if (! bb_info->in)
+ if (!bb_info->in)
continue;
fprintf (file, " in \t");
df_urec_local_finalize, /* Finalize function. */
df_urec_free, /* Free all of the problem information. */
df_urec_dump, /* Debugging. */
- &problem_LR /* Dependent problem. */
+ df_lr_add_problem, /* Dependent problem. */
+ 0 /* Changeable flags. */
};
solution. */
struct dataflow *
-df_urec_add_problem (struct df *df)
+df_urec_add_problem (struct df *df, int flags)
{
- return df_add_problem (df, &problem_UREC);
+ return df_add_problem (df, &problem_UREC, flags);
}
the reaching defs information (the dependent problem).
----------------------------------------------------------------------------*/
-struct df_chain_problem_data
-{
- int flags;
-};
-
-
/* Create def-use or use-def chains. */
static void
df_chain_alloc (struct dataflow *dflow,
- bitmap blocks_to_rescan ATTRIBUTE_UNUSED)
+ bitmap blocks_to_rescan ATTRIBUTE_UNUSED,
+ bitmap all_blocks ATTRIBUTE_UNUSED)
+
{
struct df *df = dflow->df;
unsigned int i;
- struct df_chain_problem_data *problem_data =
- (struct df_chain_problem_data *) dflow->problem_data;
/* Wholesale destruction of the old chains. */
if (dflow->block_pool)
dflow->block_pool = create_alloc_pool ("df_chain_chain_block pool",
sizeof (struct df_link), 100);
- if (problem_data->flags & DF_DU_CHAIN)
+ if (dflow->flags & DF_DU_CHAIN)
{
if (!df->def_info.refs_organized)
df_reorganize_refs (&df->def_info);
}
}
- if (problem_data->flags & DF_UD_CHAIN)
+ if (dflow->flags & DF_UD_CHAIN)
{
if (!df->use_info.refs_organized)
df_reorganize_refs (&df->use_info);
df_chain_insn_reset (struct dataflow *dflow, rtx insn)
{
struct df *df = dflow->df;
- struct df_chain_problem_data *problem_data =
- (struct df_chain_problem_data *) dflow->problem_data;
unsigned int uid = INSN_UID (insn);
struct df_insn_info *insn_info = NULL;
struct df_ref *ref;
if (insn_info)
{
- if (problem_data->flags & DF_DU_CHAIN)
+ if (dflow->flags & DF_DU_CHAIN)
{
ref = insn_info->defs;
while (ref)
}
}
- if (problem_data->flags & DF_UD_CHAIN)
+ if (dflow->flags & DF_UD_CHAIN)
{
ref = insn_info->uses;
while (ref)
df_chain_bb_reset (struct dataflow *dflow, unsigned int bb_index)
{
struct df *df = dflow->df;
- struct df_chain_problem_data *problem_data =
- (struct df_chain_problem_data *) dflow->problem_data;
rtx insn;
basic_block bb = BASIC_BLOCK (bb_index);
}
}
- /* Get rid of any chains in artifical uses or defs. */
- if (problem_data->flags & DF_DU_CHAIN)
+ /* Get rid of any chains in artificial uses or defs. */
+ if (dflow->flags & DF_DU_CHAIN)
{
struct df_ref *def;
def = df_get_artificial_defs (df, bb_index);
}
}
- if (problem_data->flags & DF_UD_CHAIN)
+ if (dflow->flags & DF_UD_CHAIN)
{
struct df_ref *use;
use = df_get_artificial_uses (df, bb_index);
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)
break;
def = DF_DEFS_GET (df, def_index);
- if (problem_data->flags & DF_DU_CHAIN)
+ if (dflow->flags & DF_DU_CHAIN)
df_chain_create (dflow, def, use);
- if (problem_data->flags & DF_UD_CHAIN)
+ if (dflow->flags & DF_UD_CHAIN)
df_chain_create (dflow, use, def);
}
}
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;
bitmap_copy (cpy, bb_info->in);
#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_chain_create_bb_process_use (dflow, cpy,
df_get_artificial_uses (df, bb->index),
DF_REF_AT_TOP);
#endif
if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
{
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_REF_FLAGS (def) & DF_REF_PARTIAL))
+ bitmap_clear_range (cpy,
+ DF_REG_DEF_GET (df, dregno)->begin,
+ DF_REG_DEF_GET (df, dregno)->n_refs);
+ bitmap_set_bit (cpy, DF_REF_ID (def));
}
/* Process the regular instructions next. */
struct df_ref *def;
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 (dflow, cpy,
+ DF_INSN_UID_USES (df, uid), 0);
/* Since we are going forwards, process the defs second. This
pass only changes the bits in cpy. */
- for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
+ for (def = DF_INSN_UID_DEFS (df, uid); 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))
+ if (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL))
+ bitmap_clear_range (cpy,
+ DF_REG_DEF_GET (df, dregno)->begin,
+ DF_REG_DEF_GET (df, dregno)->n_refs);
+ if (!(DF_REF_FLAGS (def)
+ & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
bitmap_set_bit (cpy, DF_REF_ID (def));
}
}
/* Create the chains for the artificial uses of the hard registers
at the end of the block. */
- df_chain_create_bb_process_use (dflow, problem_data, cpy,
+ df_chain_create_bb_process_use (dflow, cpy,
df_get_artificial_uses (df, bb->index), 0);
}
df_chain_free (struct dataflow *dflow)
{
free_alloc_pool (dflow->block_pool);
- free (dflow->problem_data);
free (dflow);
}
{
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 (dflow->flags & DF_DU_CHAIN)
{
fprintf (file, "Def-use chains:\n");
for (j = 0; j < df->def_info.bitmap_size; j++)
{
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_INSN_LUID (df, DF_REF_INSN (def)):
+ -1,
DF_REF_INSN (def) ? DF_REF_INSN_UID (def) : -1,
DF_REF_REGNO (def));
if (def->flags & DF_REF_READ_WRITE)
fprintf (file, "read/write ");
- df_chain_dump (df, DF_REF_CHAIN (def), file);
+ df_chain_dump (DF_REF_CHAIN (def), file);
fprintf (file, "\n");
}
}
}
- if (problem_data->flags & DF_UD_CHAIN)
+ if (dflow->flags & DF_UD_CHAIN)
{
fprintf (file, "Use-def chains:\n");
for (j = 0; j < df->use_info.bitmap_size; j++)
fprintf (file, "stripped ");
if (use->flags & DF_REF_IN_NOTE)
fprintf (file, "note ");
- df_chain_dump (df, DF_REF_CHAIN (use), file);
+ df_chain_dump (DF_REF_CHAIN (use), file);
fprintf (file, "\n");
}
}
df_chain_finalize, /* Finalize function. */
df_chain_free, /* Free all of the problem information. */
df_chains_dump, /* Debugging. */
- &problem_RD /* Dependent problem. */
+ df_rd_add_problem, /* Dependent problem. */
+ 0 /* Changeable flags. */
};
struct dataflow *
df_chain_add_problem (struct df *df, int flags)
{
- struct df_chain_problem_data *problem_data =
- XNEW (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;
+ return df_add_problem (df, &problem_CHAIN, flags);
}
/*----------------------------------------------------------------------------
REGISTER INFORMATION
- Currently this consists of only lifetime information. But the plan is
- to enhance it so that it produces all of the register information needed
- by the register allocators.
-----------------------------------------------------------------------------*/
+ This pass properly computes REG_DEAD and REG_UNUSED notes.
+ If the DF_RI_LIFE flag is set the following vectors containing
+ information about register usage are properly set: REG_N_REFS,
+ REG_N_DEATHS, REG_N_SETS, REG_LIVE_LENGTH, REG_N_CALLS_CROSSED,
+ REG_N_THROWING_CALLS_CROSSED and REG_BASIC_BLOCK.
-struct df_ri_problem_data
-{
- int *lifetime;
-};
+ ----------------------------------------------------------------------------*/
+#ifdef REG_DEAD_DEBUGGING
+static void
+print_note (char *prefix, rtx insn, rtx note)
+{
+ fprintf (stderr, "%s %d ", prefix, INSN_UID (insn));
+ print_rtl (stderr, note);
+ fprintf (stderr, "\n");
+}
+#endif
/* Allocate the lifetime information. */
static void
-df_ri_alloc (struct dataflow *dflow, bitmap blocks_to_rescan ATTRIBUTE_UNUSED)
+df_ri_alloc (struct dataflow *dflow,
+ bitmap blocks_to_rescan ATTRIBUTE_UNUSED,
+ bitmap all_blocks ATTRIBUTE_UNUSED)
{
- struct df_ri_problem_data *problem_data =
- (struct df_ri_problem_data *) dflow->problem_data;
+ int i;
+ struct df *df = dflow->df;
- if (!dflow->problem_data)
+ if (dflow->flags & DF_RI_LIFE)
{
- struct df_ri_problem_data *problem_data = XNEW (struct df_ri_problem_data);
- dflow->problem_data = problem_data;
+ max_regno = max_reg_num ();
+ allocate_reg_info (max_regno, FALSE, FALSE);
+
+ /* Reset all the data we'll collect. */
+ for (i = 0; i < max_regno; i++)
+ {
+ REG_N_SETS (i) = DF_REG_DEF_COUNT (df, i);
+ REG_N_REFS (i) = DF_REG_USE_COUNT (df, i) + REG_N_SETS (i);
+ REG_N_DEATHS (i) = 0;
+ REG_N_CALLS_CROSSED (i) = 0;
+ REG_N_THROWING_CALLS_CROSSED (i) = 0;
+ REG_LIVE_LENGTH (i) = 0;
+ REG_FREQ (i) = 0;
+ REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN;
+ }
+ }
+}
+
+
+/* After reg-stack, the x86 floating point stack regs are difficult to
+ analyze because of all of the pushes, pops and rotations. Thus, we
+ just leave the notes alone. */
+
+static inline bool
+df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
+{
+#ifdef STACK_REGS
+ return (regstack_completed
+ && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG));
+#else
+ return false;
+#endif
+}
+
+
+/* Remove all of the REG_DEAD or REG_UNUSED notes from INSN. */
+
+static void
+df_kill_notes (rtx insn, int flags)
+{
+ rtx *pprev = ®_NOTES (insn);
+ rtx link = *pprev;
+
+ while (link)
+ {
+ switch (REG_NOTE_KIND (link))
+ {
+ case REG_DEAD:
+ if (flags & DF_RI_LIFE)
+ if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
+ REG_N_DEATHS (REGNO (XEXP (link, 0)))++;
+
+ /* Fallthru */
+ case REG_UNUSED:
+ if (!df_ignore_stack_reg (REGNO (XEXP (link, 0))))
+ {
+ rtx next = XEXP (link, 1);
+#ifdef REG_DEAD_DEBUGGING
+ print_note ("deleting: ", insn, link);
+#endif
+ free_EXPR_LIST_node (link);
+ *pprev = link = next;
+ }
+ break;
+
+ default:
+ pprev = &XEXP (link, 1);
+ link = *pprev;
+ break;
+ }
+ }
+}
+
+
+/* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
+ based on the bits in LIVE. Do not generate notes for registers in
+ artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are
+ not generated if the reg is both read and written by the
+ instruction.
+*/
+
+static void
+df_set_unused_notes_for_mw (rtx insn, struct df_mw_hardreg *mws,
+ bitmap live, bitmap do_not_gen,
+ bitmap artificial_uses, int flags)
+{
+ bool all_dead = true;
+ struct df_link *regs = mws->regs;
+ unsigned int regno = DF_REF_REGNO (regs->ref);
+
+#ifdef REG_DEAD_DEBUGGING
+ fprintf (stderr, "mw unused looking at %d\n", DF_REF_REGNO (regs->ref));
+ df_ref_debug (regs->ref, stderr);
+#endif
+ while (regs)
+ {
+ unsigned int regno = DF_REF_REGNO (regs->ref);
+ if ((bitmap_bit_p (live, regno))
+ || bitmap_bit_p (artificial_uses, regno))
+ {
+ all_dead = false;
+ break;
+ }
+ regs = regs->next;
+ }
+
+ if (all_dead)
+ {
+ struct df_link *regs = mws->regs;
+ rtx note = alloc_EXPR_LIST (REG_UNUSED, *DF_REF_LOC (regs->ref),
+ REG_NOTES (insn));
+ REG_NOTES (insn) = note;
+#ifdef REG_DEAD_DEBUGGING
+ print_note ("adding 1: ", insn, note);
+#endif
+ bitmap_set_bit (do_not_gen, regno);
+ /* Only do this if the value is totally dead. */
+ if (flags & DF_RI_LIFE)
+ {
+ REG_N_DEATHS (regno) ++;
+ REG_LIVE_LENGTH (regno)++;
+ }
+ }
+ else
+ {
+ struct df_link *regs = mws->regs;
+ while (regs)
+ {
+ struct df_ref *ref = regs->ref;
+
+ regno = DF_REF_REGNO (ref);
+ if ((!bitmap_bit_p (live, regno))
+ && (!bitmap_bit_p (artificial_uses, regno)))
+ {
+ rtx note = alloc_EXPR_LIST (REG_UNUSED, regno_reg_rtx[regno],
+ REG_NOTES (insn));
+ REG_NOTES (insn) = note;
+#ifdef REG_DEAD_DEBUGGING
+ print_note ("adding 2: ", insn, note);
+#endif
+ }
+ bitmap_set_bit (do_not_gen, regno);
+ regs = regs->next;
+ }
+ }
+}
+
+
+/* Set the REG_DEAD notes for the multiword hardreg use in INSN based
+ on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes
+ from being set if the instruction both reads and writes the
+ register. */
+
+static void
+df_set_dead_notes_for_mw (rtx insn, struct df_mw_hardreg *mws,
+ bitmap live, bitmap do_not_gen,
+ bitmap artificial_uses, int flags)
+{
+ bool all_dead = true;
+ struct df_link *regs = mws->regs;
+ unsigned int regno = DF_REF_REGNO (regs->ref);
+
+#ifdef REG_DEAD_DEBUGGING
+ fprintf (stderr, "mw looking at %d\n", DF_REF_REGNO (regs->ref));
+ df_ref_debug (regs->ref, stderr);
+#endif
+ while (regs)
+ {
+ unsigned int regno = DF_REF_REGNO (regs->ref);
+ if ((bitmap_bit_p (live, regno))
+ || bitmap_bit_p (artificial_uses, regno))
+ {
+ all_dead = false;
+ break;
+ }
+ regs = regs->next;
+ }
+
+ if (all_dead)
+ {
+ if (!bitmap_bit_p (do_not_gen, regno))
+ {
+ /* Add a dead note for the entire multi word register. */
+ struct df_link *regs = mws->regs;
+ rtx note = alloc_EXPR_LIST (REG_DEAD, *DF_REF_LOC (regs->ref),
+ REG_NOTES (insn));
+ REG_NOTES (insn) = note;
+#ifdef REG_DEAD_DEBUGGING
+ print_note ("adding 1: ", insn, note);
+#endif
+
+ if (flags & DF_RI_LIFE)
+ {
+ struct df_link *regs = mws->regs;
+ while (regs)
+ {
+ struct df_ref *ref = regs->ref;
+ regno = DF_REF_REGNO (ref);
+ REG_N_DEATHS (regno)++;
+ regs = regs->next;
+ }
+ }
+ }
+ }
+ else
+ {
+ struct df_link *regs = mws->regs;
+ while (regs)
+ {
+ struct df_ref *ref = regs->ref;
+
+ regno = DF_REF_REGNO (ref);
+ if ((!bitmap_bit_p (live, regno))
+ && (!bitmap_bit_p (artificial_uses, regno))
+ && (!bitmap_bit_p (do_not_gen, regno)))
+ {
+ rtx note = alloc_EXPR_LIST (REG_DEAD, regno_reg_rtx[regno],
+ REG_NOTES (insn));
+ REG_NOTES (insn) = note;
+ if (flags & DF_RI_LIFE)
+ REG_N_DEATHS (regno)++;
+#ifdef REG_DEAD_DEBUGGING
+ print_note ("adding 2: ", insn, note);
+#endif
+ }
+
+ regs = regs->next;
+ }
}
+}
+
+
+/* Create a REG_UNUSED note if necessary for DEF in INSN updating LIVE
+ and DO_NOT_GEN. Do not generate notes for registers in artificial
+ uses. */
+
+static void
+df_create_unused_note (basic_block bb, rtx insn, struct df_ref *def,
+ bitmap live, bitmap do_not_gen, bitmap artificial_uses,
+ bitmap local_live, bitmap local_processed,
+ int flags, int luid)
+{
+ unsigned int dregno = DF_REF_REGNO (def);
+
+#ifdef REG_DEAD_DEBUGGING
+ fprintf (stderr, " regular looking at def ");
+ df_ref_debug (def, stderr);
+#endif
- problem_data->lifetime = xrealloc (problem_data->lifetime,
- max_reg_num () *sizeof (int));
- memset (problem_data->lifetime, 0, max_reg_num () *sizeof (int));
+ if (bitmap_bit_p (live, dregno))
+ {
+ if (flags & DF_RI_LIFE)
+ {
+ /* If we have seen this regno, then it has already been
+ processed correctly with the per insn increment. If we
+ have not seen it we need to add the length from here to
+ the end of the block to the live length. */
+ if (bitmap_bit_p (local_processed, dregno))
+ {
+ if (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL))
+ bitmap_clear_bit (local_live, dregno);
+ }
+ else
+ {
+ bitmap_set_bit (local_processed, dregno);
+ REG_LIVE_LENGTH (dregno) += luid;
+ }
+ }
+ }
+ else if ((!(DF_REF_FLAGS (def) & DF_REF_MW_HARDREG))
+ && (!bitmap_bit_p (artificial_uses, dregno))
+ && (!df_ignore_stack_reg (dregno)))
+ {
+ rtx reg = GET_CODE (*DF_REF_LOC (def)) == SUBREG ?
+ SUBREG_REG (*DF_REF_LOC (def)) : *DF_REF_LOC (def);
+ rtx note = alloc_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn));
+ REG_NOTES (insn) = note;
+#ifdef REG_DEAD_DEBUGGING
+ print_note ("adding 3: ", insn, note);
+#endif
+ if (flags & DF_RI_LIFE)
+ {
+ REG_N_DEATHS (dregno) ++;
+ REG_LIVE_LENGTH (dregno)++;
+ }
+ }
+
+ if ((flags & DF_RI_LIFE) && (dregno >= FIRST_PSEUDO_REGISTER))
+ {
+ REG_FREQ (dregno) += REG_FREQ_FROM_BB (bb);
+ if (REG_BASIC_BLOCK (dregno) == REG_BLOCK_UNKNOWN)
+ REG_BASIC_BLOCK (dregno) = bb->index;
+ else if (REG_BASIC_BLOCK (dregno) != bb->index)
+ REG_BASIC_BLOCK (dregno) = REG_BLOCK_GLOBAL;
+ }
+
+ if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER + DF_REF_MAY_CLOBBER)))
+ bitmap_set_bit (do_not_gen, dregno);
+
+ /* Kill this register if it is not a subreg store. */
+ if (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL))
+ bitmap_clear_bit (live, dregno);
}
-/* Compute register info: lifetime, bb, and number of defs and uses
- for basic block BB. */
+
+/* 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_ri_bb_compute (struct dataflow *dflow, unsigned int bb_index,
+ bitmap live, bitmap do_not_gen, bitmap artificial_uses,
+ bitmap local_live, bitmap local_processed, bitmap setjumps_crossed)
{
struct df *df = dflow->df;
- 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;
+ struct df_ref *use;
+ int luid = 0;
- bitmap_copy (live, bb_info->out);
+ bitmap_copy (live, df_get_live_out (df, bb));
+ bitmap_clear (artificial_uses);
+ if (dflow->flags & DF_RI_LIFE)
+ {
+ /* Process the regs live at the end of the block. Mark them as
+ not local to any one basic block. */
+ bitmap_iterator bi;
+ unsigned int regno;
+ EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
+ REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL;
+ }
+
+ /* Process the artificial defs and uses at the bottom of the block
+ to begin processing. */
+ for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref)
+ if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
+ bitmap_clear_bit (live, DF_REF_REGNO (def));
+
+ for (use = df_get_artificial_uses (df, bb_index); use; use = use->next_ref)
+ if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
+ {
+ unsigned int regno = DF_REF_REGNO (use);
+ bitmap_set_bit (live, regno);
+
+ /* Notes are not generated for any of the artificial registers
+ at the bottom of the block. */
+ bitmap_set_bit (artificial_uses, regno);
+ }
+
FOR_BB_INSNS_REVERSE (bb, insn)
{
unsigned int uid = INSN_UID (insn);
unsigned int regno;
bitmap_iterator bi;
- struct df_ref *def;
- struct df_ref *use;
-
- if (! INSN_P (insn))
+ struct df_mw_hardreg *mws;
+
+ if (!INSN_P (insn))
continue;
- for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
+ if (dflow->flags & DF_RI_LIFE)
{
- unsigned int dregno = DF_REF_REGNO (def);
+ /* Increment the live_length for all of the registers that
+ are are referenced in this block and live at this
+ particular point. */
+ bitmap_iterator bi;
+ unsigned int regno;
+ EXECUTE_IF_SET_IN_BITMAP (local_live, 0, regno, bi)
+ {
+ REG_LIVE_LENGTH (regno)++;
+ }
+ luid++;
+ }
+
+ bitmap_clear (do_not_gen);
+ df_kill_notes (insn, dflow->flags);
+
+ /* Process the defs. */
+ if (CALL_P (insn))
+ {
+ if (dflow->flags & DF_RI_LIFE)
+ {
+ bool can_throw = can_throw_internal (insn);
+ bool set_jump = (find_reg_note (insn, REG_SETJMP, NULL) != NULL);
+ EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
+ {
+ REG_N_CALLS_CROSSED (regno)++;
+ if (can_throw)
+ REG_N_THROWING_CALLS_CROSSED (regno)++;
+
+ /* We have a problem with any pseudoreg that lives
+ across the setjmp. ANSI says that if a user
+ variable does not change in value between the
+ setjmp and the longjmp, then the longjmp
+ preserves it. This includes longjmp from a place
+ where the pseudo appears dead. (In principle,
+ the value still exists if it is in scope.) If
+ the pseudo goes in a hard reg, some other value
+ may occupy that hard reg where this pseudo is
+ dead, thus clobbering the pseudo. Conclusion:
+ such a pseudo must not go in a hard reg. */
+ if (set_jump && regno >= FIRST_PSEUDO_REGISTER)
+ bitmap_set_bit (setjumps_crossed, regno);
+ }
+ }
+
+ /* We only care about real sets for calls. Clobbers only
+ may clobber and cannot be depended on. */
+ for (mws = DF_INSN_UID_MWS (df, uid); mws; mws = mws->next)
+ {
+ if ((mws->type == DF_REF_REG_DEF)
+ && !df_ignore_stack_reg (REGNO (mws->mw_reg)))
+ df_set_unused_notes_for_mw (insn, mws, live, do_not_gen,
+ artificial_uses, dflow->flags);
+ }
+
+ /* All of the defs except the return value are some sort of
+ clobber. This code is for the return. */
+ for (def = DF_INSN_UID_DEFS (df, uid); def; def = def->next_ref)
+ if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
+ df_create_unused_note (bb, insn, def, live, do_not_gen,
+ artificial_uses, local_live,
+ local_processed, dflow->flags, luid);
- /* Kill this register. */
- bitmap_clear_bit (live, dregno);
}
+ else
+ {
+ /* Regular insn. */
+ for (mws = DF_INSN_UID_MWS (df, uid); mws; mws = mws->next)
+ {
+ if (mws->type == DF_REF_REG_DEF)
+ df_set_unused_notes_for_mw (insn, mws, live, do_not_gen,
+ artificial_uses, dflow->flags);
+ }
- for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
+ for (def = DF_INSN_UID_DEFS (df, uid); def; def = def->next_ref)
+ df_create_unused_note (bb, insn, def, live, do_not_gen,
+ artificial_uses, local_live,
+ local_processed, dflow->flags, luid);
+ }
+
+ /* Process the uses. */
+ for (mws = DF_INSN_UID_MWS (df, uid); mws; mws = mws->next)
+ {
+ if ((mws->type != DF_REF_REG_DEF)
+ && !df_ignore_stack_reg (REGNO (mws->mw_reg)))
+ df_set_dead_notes_for_mw (insn, mws, live, do_not_gen,
+ artificial_uses, dflow->flags);
+ }
+
+ for (use = DF_INSN_UID_USES (df, uid); use; use = use->next_ref)
{
unsigned int uregno = DF_REF_REGNO (use);
+ if ((dflow->flags & DF_RI_LIFE) && (uregno >= FIRST_PSEUDO_REGISTER))
+ {
+ REG_FREQ (uregno) += REG_FREQ_FROM_BB (bb);
+ if (REG_BASIC_BLOCK (uregno) == REG_BLOCK_UNKNOWN)
+ REG_BASIC_BLOCK (uregno) = bb->index;
+ else if (REG_BASIC_BLOCK (uregno) != bb->index)
+ REG_BASIC_BLOCK (uregno) = REG_BLOCK_GLOBAL;
+ }
+
+#ifdef REG_DEAD_DEBUGGING
+ fprintf (stderr, " regular looking at use ");
+ df_ref_debug (use, stderr);
+#endif
if (!bitmap_bit_p (live, uregno))
{
- use->flags |= DF_REF_DIES_AFTER_THIS_USE;
+ if ( (!(DF_REF_FLAGS (use) & DF_REF_MW_HARDREG))
+ && (!bitmap_bit_p (do_not_gen, uregno))
+ && (!bitmap_bit_p (artificial_uses, uregno))
+ && (!(DF_REF_FLAGS (use) & DF_REF_READ_WRITE))
+ && (!df_ignore_stack_reg (uregno)))
+ {
+ rtx reg = GET_CODE (*DF_REF_LOC (use)) == SUBREG ?
+ SUBREG_REG (*DF_REF_LOC (use)) : *DF_REF_LOC (use);
+ rtx note = alloc_EXPR_LIST (REG_DEAD, reg, REG_NOTES (insn));
+ REG_NOTES (insn) = note;
+ if (dflow->flags & DF_RI_LIFE)
+ REG_N_DEATHS (uregno)++;
+
+#ifdef REG_DEAD_DEBUGGING
+ print_note ("adding 4: ", insn, note);
+#endif
+ }
/* This register is now live. */
bitmap_set_bit (live, uregno);
+
+ if (dflow->flags & DF_RI_LIFE)
+ {
+ /* If we have seen this regno, then it has already
+ been processed correctly with the per insn
+ increment. If we have not seen it we set the bit
+ so that begins to get processed locally. Note
+ that we don't even get here if the variable was
+ live at the end of the block since just a ref
+ inside the block does not effect the
+ calculations. */
+ REG_LIVE_LENGTH (uregno) ++;
+ bitmap_set_bit (local_live, uregno);
+ bitmap_set_bit (local_processed, uregno);
+ }
}
- else
- use->flags &= ~DF_REF_DIES_AFTER_THIS_USE;
}
-
- /* Increment lifetimes of all live registers. */
+ }
+
+ if (dflow->flags & DF_RI_LIFE)
+ {
+ /* Add the length of the block to all of the registers that were
+ not referenced, but still live in this block. */
+ bitmap_iterator bi;
+ unsigned int regno;
+ bitmap_and_compl_into (live, local_processed);
EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
{
- problem_data->lifetime[regno]++;
+ REG_LIVE_LENGTH (regno) += luid;
}
+ bitmap_clear (local_processed);
+ bitmap_clear (local_live);
}
}
{
unsigned int bb_index;
bitmap_iterator bi;
- bitmap live;
+ bitmap live = BITMAP_ALLOC (NULL);
+ bitmap do_not_gen = BITMAP_ALLOC (NULL);
+ bitmap artificial_uses = BITMAP_ALLOC (NULL);
+ bitmap local_live = NULL;
+ bitmap local_processed = NULL;
+ bitmap setjumps_crossed = NULL;
- live = BITMAP_ALLOC (NULL);
+ if (dflow->flags & DF_RI_LIFE)
+ {
+ local_live = BITMAP_ALLOC (NULL);
+ local_processed = BITMAP_ALLOC (NULL);
+ setjumps_crossed = BITMAP_ALLOC (NULL);
+ }
+
+
+#ifdef REG_DEAD_DEBUGGING
+ df_lr_dump (dflow->df->problems_by_index [DF_LR], stderr);
+ print_rtl_with_bb (stderr, get_insns());
+#endif
EXECUTE_IF_SET_IN_BITMAP (blocks_to_scan, 0, bb_index, bi)
{
- df_ri_bb_compute (dflow, bb_index, live);
+ df_ri_bb_compute (dflow, bb_index, live, do_not_gen, artificial_uses,
+ local_live, local_processed, setjumps_crossed);
}
BITMAP_FREE (live);
+ BITMAP_FREE (do_not_gen);
+ BITMAP_FREE (artificial_uses);
+ if (dflow->flags & DF_RI_LIFE)
+ {
+ bitmap_iterator bi;
+ unsigned int regno;
+ /* See the setjump comment in df_ri_bb_compute. */
+ EXECUTE_IF_SET_IN_BITMAP (setjumps_crossed, 0, regno, bi)
+ {
+ REG_BASIC_BLOCK (regno) = REG_BLOCK_UNKNOWN;
+ REG_LIVE_LENGTH (regno) = -1;
+ }
+
+ BITMAP_FREE (local_live);
+ BITMAP_FREE (local_processed);
+ BITMAP_FREE (setjumps_crossed);
+ }
}
static void
df_ri_free (struct dataflow *dflow)
{
- 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);
}
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;
+ print_rtl_with_bb (file, get_insns ());
- fprintf (file, "Register info:\n");
- for (j = 0; j < max_reg_num (); j++)
+ if (dflow->flags & DF_RI_LIFE)
{
- fprintf (file, "reg %d life %d\n", j, problem_data->lifetime[j]);
+ fprintf (file, "Register info:\n");
+ dump_flow_info (file, -1);
}
}
NULL, /* Finalize function. */
df_ri_free, /* Free all of the problem information. */
df_ri_dump, /* Debugging. */
- &problem_UR /* Dependent problem. */
+
+ /* Technically this is only dependent on the live registers problem
+ but it will produce information if built one of uninitialized
+ register problems (UR, UREC) is also run. */
+ df_lr_add_problem, /* Dependent problem. */
+ 0 /* Changeable flags. */
};
solution. */
struct dataflow *
-df_ri_add_problem (struct df *df)
+df_ri_add_problem (struct df *df, int flags)
{
- return df_add_problem (df, &problem_RI);
+ return df_add_problem (df, &problem_RI, flags);
}
-
-
-/* Return total lifetime (in insns) of REG. */
-int
-df_reg_lifetime (struct df *df, rtx reg)
-{
- 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)];
-}
-
-
OSDN Git Service
