/* Allocation for dataflow support routines.
- Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
- Free Software Foundation, Inc.
+ Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
+ 2008, 2009 Free Software Foundation, Inc.
Originally contributed by Michael P. Hayes
(m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
There are three variations of the live variable problem that are
available whenever dataflow is available. The LR problem finds the
areas that can reach a use of a variable, the UR problems finds the
-areas tha can be reached from a definition of a variable. The LIVE
+areas that can be reached from a definition of a variable. The LIVE
problem finds the intersection of these two areas.
There are several optional problems. These can be enabled when they
section.
In the middle layer, basic blocks are scanned to produce transfer
-functions which describe the effects of that block on the a global
+functions which describe the effects of that block on the global
dataflow solution. The transfer functions are only rebuilt if the
some instruction within the block has changed.
d) If the pass modifies all of the insns, as does register
allocation, it is simply better to rescan the entire function.
- e) If the pass uses either non-standard or ancient techniques to
- modify insns, automatic detection of the insns that need to be
- rescanned may be impractical. Cse and regrename fall into this
- category.
-
2) Deferred rescanning - Calls to df_insn_rescan, df_notes_rescan, and
df_insn_delete do not immediately change the insn but instead make
a note that the insn needs to be rescanned. The next call to
cause all of the pending rescans to be processed.
This is the technique of choice if either 1a, 1b, or 1c are issues
- in the pass. In the case of 1a or 1b, a call to df_remove_problem
- (df_chain) should be made before the next call to df_analyze or
- df_process_deferred_rescans.
+ in the pass. In the case of 1a or 1b, a call to df_finish_pass
+ (either manually or via TODO_df_finish) should be made before the
+ next call to df_analyze or df_process_deferred_rescans.
+
+ This mode is also used by a few passes that still rely on note_uses,
+ note_stores and for_each_rtx instead of using the DF data. This
+ can be said to fall under case 1c.
To enable this mode, call df_set_flags (DF_DEFER_INSN_RESCAN).
(This mode can be cleared by calling df_clear_flags
(DF_DEFER_INSN_RESCAN) but this does not cause the deferred insns to
be rescanned.
- 3) Total rescanning - In this mode the rescanning is disabled.
- However, the df information associated with deleted insn is delete
- at the time the insn is deleted. At the end of the pass, a call
- must be made to df_insn_rescan_all. This method is used by the
- register allocator since it generally changes each insn multiple
- times (once for each ref) and does not need to make use of the
- updated scanning information.
-
- It is also currently used by two older passes (cse, and regrename)
- which change insns in hard to track ways. It is hoped that this
- will be fixed soon since this it is expensive to rescan all of the
- insns when only a small number of them have really changed.
+3) Total rescanning - In this mode the rescanning is disabled.
+ Only when insns are deleted is the df information associated with
+ it also deleted. At the end of the pass, a call must be made to
+ df_insn_rescan_all. This method is used by the register allocator
+ since it generally changes each insn multiple times (once for each ref)
+ and does not need to make use of the updated scanning information.
4) Do it yourself - In this mechanism, the pass updates the insns
itself using the low level df primitives. Currently no pass does
ACCESSING INSNS:
-1) The df insn information is kept in the insns array. This array is
- indexed by insn uid.
-
-2) Each insn has three sets of refs: They are linked into one of three
- lists: the insn's defs list (accessed by the DF_INSN_DEFS or
- DF_INSN_UID_DEFS macros), the insn's uses list (accessed by the
- DF_INSN_USES or DF_INSN_UID_USES macros) or the insn's eq_uses list
- (accessed by the DF_INSN_EQ_USES or DF_INSN_UID_EQ_USES macros).
- The latter list are the list of references in REG_EQUAL or
- REG_EQUIV notes. These macros produce a ref (or NULL), the rest of
- the list can be obtained by traversal of the NEXT_REF field
- (accessed by the DF_REF_NEXT_REF macro.) There is no significance
- to the ordering of the uses or refs in an instruction.
-
-3) Each insn has a logical uid field (LUID). When properly set, this
- is an integer that numbers each insn in the basic block, in order from
- the start of the block. The numbers are only correct after a call to
- df_analyse. They will rot after insns are added deleted or moved
- around.
+1) The df insn information is kept in an array of DF_INSN_INFO objects.
+ The array is indexed by insn uid, and every DF_REF points to the
+ DF_INSN_INFO object of the insn that contains the reference.
+
+2) Each insn has three sets of refs, which are linked into one of three
+ lists: The insn's defs list (accessed by the DF_INSN_INFO_DEFS,
+ DF_INSN_DEFS, or DF_INSN_UID_DEFS macros), the insn's uses list
+ (accessed by the DF_INSN_INFO_USES, DF_INSN_USES, or
+ DF_INSN_UID_USES macros) or the insn's eq_uses list (accessed by the
+ DF_INSN_INFO_EQ_USES, DF_INSN_EQ_USES or DF_INSN_UID_EQ_USES macros).
+ The latter list are the list of references in REG_EQUAL or REG_EQUIV
+ notes. These macros produce a ref (or NULL), the rest of the list
+ can be obtained by traversal of the NEXT_REF field (accessed by the
+ DF_REF_NEXT_REF macro.) There is no significance to the ordering of
+ the uses or refs in an instruction.
+
+3) Each insn has a logical uid field (LUID) which is stored in the
+ DF_INSN_INFO object for the insn. The LUID field is accessed by
+ the DF_INSN_INFO_LUID, DF_INSN_LUID, and DF_INSN_UID_LUID macros.
+ When properly set, the LUID is an integer that numbers each insn in
+ the basic block, in order from the start of the block.
+ The numbers are only correct after a call to df_analyze. They will
+ rot after insns are added deleted or moved round.
ACCESSING REFS:
chains.
4) An array of all of the uses (and an array of all of the defs) can
-
be built. These arrays are indexed by the value in the id
structure. These arrays are only lazily kept up to date, and that
process can be expensive. To have these arrays built, call
A set to a REG inside a ZERO_EXTRACT, or a set to a non-paradoxical SUBREG
for which the number of word_mode units covered by the outer mode is
-smaller than that covered by the inner mode, invokes a read-modify-write.
+smaller than that covered by the inner mode, invokes a read-modify-write
operation. We generate both a use and a def and again mark them
read/write.
/* Set the MASK flags in the DFLOW problem. The old flags are
returned. If a flag is not allowed to be changed this will fail if
checking is enabled. */
-enum df_changeable_flags
-df_set_flags (enum df_changeable_flags changeable_flags)
+int
+df_set_flags (int changeable_flags)
{
- enum df_changeable_flags old_flags = df->changeable_flags;
+ int old_flags = df->changeable_flags;
df->changeable_flags |= changeable_flags;
return old_flags;
}
/* Clear the MASK flags in the DFLOW problem. The old flags are
returned. If a flag is not allowed to be changed this will fail if
checking is enabled. */
-enum df_changeable_flags
-df_clear_flags (enum df_changeable_flags changeable_flags)
+int
+df_clear_flags (int changeable_flags)
{
- enum df_changeable_flags old_flags = df->changeable_flags;
+ int old_flags = df->changeable_flags;
df->changeable_flags &= ~changeable_flags;
return old_flags;
}
int j;
for (j = i + 1; j < df->num_problems_defined; j++)
df->problems_in_order[j-1] = df->problems_in_order[j];
- df->problems_in_order[j] = NULL;
+ df->problems_in_order[j-1] = NULL;
df->num_problems_defined--;
break;
}
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
- 0, /* tv_id */
+ TV_NONE, /* tv_id */
0, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
- 0, /* tv_id */
+ TV_NONE, /* tv_id */
0, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
- 0, /* tv_id */
+ TV_NONE, /* tv_id */
0, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
/* This will free "pending". */
-static void
-df_worklist_dataflow_overeager (struct dataflow *dataflow,
- bitmap pending,
- sbitmap considered,
- int *blocks_in_postorder,
- unsigned *bbindex_to_postorder)
-{
- enum df_flow_dir dir = dataflow->problem->dir;
- int count = 0;
-
- while (!bitmap_empty_p (pending))
- {
- unsigned bb_index;
- int index;
- count++;
-
- index = bitmap_first_set_bit (pending);
- bitmap_clear_bit (pending, index);
-
- bb_index = blocks_in_postorder[index];
-
- if (dir == DF_FORWARD)
- df_worklist_propagate_forward (dataflow, bb_index,
- bbindex_to_postorder,
- pending, considered);
- else
- df_worklist_propagate_backward (dataflow, bb_index,
- bbindex_to_postorder,
- pending, considered);
- }
-
- BITMAP_FREE (pending);
-
- /* Dump statistics. */
- if (dump_file)
- fprintf (dump_file, "df_worklist_dataflow_overeager:"
- "n_basic_blocks %d n_edges %d"
- " count %d (%5.2g)\n",
- n_basic_blocks, n_edges,
- count, count / (float)n_basic_blocks);
-}
static void
df_worklist_dataflow_doublequeue (struct dataflow *dataflow,
/* Worklist-based dataflow solver. It uses sbitmap as a worklist,
with "n"-th bit representing the n-th block in the reverse-postorder order.
- This is so-called over-eager algorithm where it propagates
- changes on demand. This algorithm may visit blocks more than
- iterative method if there are deeply nested loops.
- Worklist algorithm works better than iterative algorithm
- for CFGs with no nested loops.
- In practice, the measurement shows worklist algorithm beats
- iterative algorithm by some margin overall.
- Note that this is slightly different from the traditional textbook worklist solver,
- in that the worklist is effectively sorted by the reverse postorder.
- For CFGs with no nested loops, this is optimal.
-
- The overeager algorithm while works well for typical inputs,
- it could degenerate into excessive iterations given CFGs with high loop nests
- and unstructured loops. To cap the excessive iteration on such case,
- we switch to double-queueing when the original algorithm seems to
- get into such.
- */
+ The solver is a double-queue algorithm similar to the "double stack" solver
+ from Cooper, Harvey and Kennedy, "Iterative data-flow analysis, Revisited".
+ The only significant difference is that the worklist in this implementation
+ is always sorted in RPO of the CFG visiting direction. */
void
df_worklist_dataflow (struct dataflow *dataflow,
if (dataflow->problem->init_fun)
dataflow->problem->init_fun (blocks_to_consider);
- /* Solve it. Determine the solving algorithm
- based on a simple heuristic. */
- if (n_edges > PARAM_VALUE (PARAM_DF_DOUBLE_QUEUE_THRESHOLD_FACTOR)
- * n_basic_blocks)
- {
- /* High average connectivity, meaning dense graph
- with more likely deep nested loops
- or unstructured loops. */
- df_worklist_dataflow_doublequeue (dataflow, pending, considered,
- blocks_in_postorder,
- bbindex_to_postorder);
- }
- else
- {
- /* Most inputs fall into this case
- with relatively flat or structured CFG. */
- df_worklist_dataflow_overeager (dataflow, pending, considered,
- blocks_in_postorder,
- bbindex_to_postorder);
- }
+ /* Solve it. */
+ df_worklist_dataflow_doublequeue (dataflow, pending, considered,
+ blocks_in_postorder,
+ bbindex_to_postorder);
sbitmap_free (considered);
free (bbindex_to_postorder);
void **problem_temps;
int size = last_basic_block * sizeof (void *);
bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
- problem_temps = xmalloc (size);
+ problem_temps = XNEWVAR (void *, size);
for (p = 0; p < df->num_problems_defined; p++)
{
/* Return first def of REGNO within BB. */
-struct df_ref *
+df_ref
df_bb_regno_first_def_find (basic_block bb, unsigned int regno)
{
rtx insn;
- struct df_ref **def_rec;
+ df_ref *def_rec;
unsigned int uid;
FOR_BB_INSNS (bb, insn)
uid = INSN_UID (insn);
for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
{
- struct df_ref *def = *def_rec;
+ df_ref def = *def_rec;
if (DF_REF_REGNO (def) == regno)
return def;
}
/* Return last def of REGNO within BB. */
-struct df_ref *
+df_ref
df_bb_regno_last_def_find (basic_block bb, unsigned int regno)
{
rtx insn;
- struct df_ref **def_rec;
+ df_ref *def_rec;
unsigned int uid;
FOR_BB_INSNS_REVERSE (bb, insn)
uid = INSN_UID (insn);
for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
{
- struct df_ref *def = *def_rec;
+ df_ref def = *def_rec;
if (DF_REF_REGNO (def) == regno)
return def;
}
/* Finds the reference corresponding to the definition of REG in INSN.
DF is the dataflow object. */
-struct df_ref *
+df_ref
df_find_def (rtx insn, rtx reg)
{
unsigned int uid;
- struct df_ref **def_rec;
+ df_ref *def_rec;
if (GET_CODE (reg) == SUBREG)
reg = SUBREG_REG (reg);
uid = INSN_UID (insn);
for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
{
- struct df_ref *def = *def_rec;
+ df_ref def = *def_rec;
if (rtx_equal_p (DF_REF_REAL_REG (def), reg))
return def;
}
/* Finds the reference corresponding to the use of REG in INSN.
DF is the dataflow object. */
-struct df_ref *
+df_ref
df_find_use (rtx insn, rtx reg)
{
unsigned int uid;
- struct df_ref **use_rec;
+ df_ref *use_rec;
if (GET_CODE (reg) == SUBREG)
reg = SUBREG_REG (reg);
uid = INSN_UID (insn);
for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
{
- struct df_ref *use = *use_rec;
+ df_ref use = *use_rec;
if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
return use;
}
if (df->changeable_flags & DF_EQ_NOTES)
for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
{
- struct df_ref *use = *use_rec;
+ df_ref use = *use_rec;
if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
return use;
}
}
+/* Write information about registers and basic blocks into FILE. The
+ bitmap is in the form used by df_byte_lr. This is part of making a
+ debugging dump. */
+
+void
+df_print_byte_regset (FILE *file, bitmap r)
+{
+ unsigned int max_reg = max_reg_num ();
+ bitmap_iterator bi;
+
+ if (r == NULL)
+ fputs (" (nil)", file);
+ else
+ {
+ unsigned int i;
+ for (i = 0; i < max_reg; i++)
+ {
+ unsigned int first = df_byte_lr_get_regno_start (i);
+ unsigned int len = df_byte_lr_get_regno_len (i);
+
+ if (len > 1)
+ {
+ bool found = false;
+ unsigned int j;
+
+ EXECUTE_IF_SET_IN_BITMAP (r, first, j, bi)
+ {
+ found = j < first + len;
+ break;
+ }
+ if (found)
+ {
+ const char * sep = "";
+ fprintf (file, " %d", i);
+ if (i < FIRST_PSEUDO_REGISTER)
+ fprintf (file, " [%s]", reg_names[i]);
+ fprintf (file, "(");
+ EXECUTE_IF_SET_IN_BITMAP (r, first, j, bi)
+ {
+ if (j > first + len - 1)
+ break;
+ fprintf (file, "%s%d", sep, j-first);
+ sep = ", ";
+ }
+ fprintf (file, ")");
+ }
+ }
+ else
+ {
+ if (bitmap_bit_p (r, first))
+ {
+ fprintf (file, " %d", i);
+ if (i < FIRST_PSEUDO_REGISTER)
+ fprintf (file, " [%s]", reg_names[i]);
+ }
+ }
+
+ }
+ }
+ fprintf (file, "\n");
+}
+
+
/* Dump dataflow info. */
void
void
-df_refs_chain_dump (struct df_ref **ref_rec, bool follow_chain, FILE *file)
+df_refs_chain_dump (df_ref *ref_rec, bool follow_chain, FILE *file)
{
fprintf (file, "{ ");
while (*ref_rec)
{
- struct df_ref *ref = *ref_rec;
+ df_ref ref = *ref_rec;
fprintf (file, "%c%d(%d)",
DF_REF_REG_DEF_P (ref) ? 'd' : (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) ? 'e' : 'u',
DF_REF_ID (ref),
/* Dump either a ref-def or reg-use chain. */
void
-df_regs_chain_dump (struct df_ref *ref, FILE *file)
+df_regs_chain_dump (df_ref ref, FILE *file)
{
fprintf (file, "{ ");
while (ref)
DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
DF_REF_ID (ref),
DF_REF_REGNO (ref));
- ref = ref->next_reg;
+ ref = DF_REF_NEXT_REG (ref);
}
fprintf (file, "}");
}
while (*mws)
{
fprintf (file, "mw %c r[%d..%d]\n",
- ((*mws)->type == DF_REF_REG_DEF) ? 'd' : 'u',
+ (DF_MWS_REG_DEF_P (*mws)) ? 'd' : 'u',
(*mws)->start_regno, (*mws)->end_regno);
mws++;
}
void
df_insn_debug_regno (rtx insn, FILE *file)
{
- unsigned int uid = INSN_UID(insn);
+ struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
fprintf (file, "insn %d bb %d luid %d defs ",
- uid, BLOCK_FOR_INSN (insn)->index, DF_INSN_LUID (insn));
- df_refs_chain_dump (DF_INSN_UID_DEFS (uid), false, file);
+ INSN_UID (insn), BLOCK_FOR_INSN (insn)->index,
+ DF_INSN_INFO_LUID (insn_info));
+ df_refs_chain_dump (DF_INSN_INFO_DEFS (insn_info), false, file);
fprintf (file, " uses ");
- df_refs_chain_dump (DF_INSN_UID_USES (uid), false, file);
+ df_refs_chain_dump (DF_INSN_INFO_USES (insn_info), false, file);
fprintf (file, " eq_uses ");
- df_refs_chain_dump (DF_INSN_UID_EQ_USES (uid), false, file);
+ df_refs_chain_dump (DF_INSN_INFO_EQ_USES (insn_info), false, file);
fprintf (file, "\n");
}
void
-df_ref_debug (struct df_ref *ref, FILE *file)
+df_ref_debug (df_ref ref, FILE *file)
{
fprintf (file, "%c%d ",
DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
fprintf (file, "reg %d bb %d insn %d flag 0x%x type 0x%x ",
DF_REF_REGNO (ref),
DF_REF_BBNO (ref),
- DF_REF_INSN (ref) ? INSN_UID (DF_REF_INSN (ref)) : -1,
+ DF_REF_IS_ARTIFICIAL (ref) ? -1 : DF_REF_INSN_UID (ref),
DF_REF_FLAGS (ref),
DF_REF_TYPE (ref));
if (DF_REF_LOC (ref))
- fprintf (file, "loc %p(%p) chain ", (void *)DF_REF_LOC (ref), (void *)*DF_REF_LOC (ref));
+ {
+ if (flag_dump_noaddr)
+ fprintf (file, "loc #(#) chain ");
+ else
+ fprintf (file, "loc %p(%p) chain ", (void *)DF_REF_LOC (ref),
+ (void *)*DF_REF_LOC (ref));
+ }
else
fprintf (file, "chain ");
df_chain_dump (DF_REF_CHAIN (ref), file);
void
-debug_df_ref (struct df_ref *ref)
+debug_df_ref (df_ref ref)
{
df_ref_debug (ref, stderr);
}
OSDN Git Service
