/* 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 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.
Here is an example of using the dataflow routines.
- df_[ru,rd,urec,ri,chain]_add_problem (flags);
+ df_[chain,live,note,rd]_add_problem (flags);
df_set_blocks (blocks);
df_dump (stderr);
- df_finish_pass ();
+ df_finish_pass (false);
-DF_[ru,rd,urec,ri,chain]_ADD_PROBLEM adds a problem, defined by an
+DF_[chain,live,note,rd]_ADD_PROBLEM adds a problem, defined by an
instance to struct df_problem, to the set of problems solved in this
instance of df. All calls to add a problem for a given instance of df
must occur before the first call to DF_ANALYZE.
For most modern rtl passes, this is certainly the easiest way to
manage rescanning the insns. This technique also has the advantage
that the scanning information is always correct and can be relied
- apon even after changes have been made to the instructions. This
+ upon even after changes have been made to the instructions. This
technique is contra indicated in several cases:
a) If def-use chains OR use-def chains (but not both) are built,
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.
#include "timevar.h"
#include "df.h"
#include "tree-pass.h"
+#include "params.h"
static void *df_get_bb_info (struct dataflow *, unsigned int);
static void df_set_bb_info (struct dataflow *, unsigned int, void *);
}
-/* Remove all of the problems that are not permanent. Scanning, lr,
- ur and live are permanent, the rest are removable. Also clear all
- of the changeable_flags. */
+/* Remove all of the problems that are not permanent. Scanning, LR
+ and (at -O2 or higher) LIVE are permanent, the rest are removable.
+ Also clear all of the changeable_flags. */
void
-df_finish_pass (void)
+df_finish_pass (bool verify ATTRIBUTE_UNUSED)
{
int i;
int removed = 0;
df_set_clean_cfg ();
#endif
#endif
+
+#ifdef ENABLE_CHECKING
+ if (verify)
+ df->changeable_flags |= DF_VERIFY_SCHEDULED;
+#endif
}
}
-struct tree_opt_pass pass_df_initialize_opt =
+struct rtl_opt_pass pass_df_initialize_opt =
{
+ {
+ RTL_PASS,
"dfinit", /* name */
gate_opt, /* gate */
rest_of_handle_df_initialize, /* execute */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- 0, /* todo_flags_finish */
- 'z' /* letter */
+ 0 /* todo_flags_finish */
+ }
};
}
-struct tree_opt_pass pass_df_initialize_no_opt =
+struct rtl_opt_pass pass_df_initialize_no_opt =
{
+ {
+ RTL_PASS,
"dfinit", /* name */
gate_no_opt, /* gate */
rest_of_handle_df_initialize, /* execute */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- 0, /* todo_flags_finish */
- 'z' /* letter */
+ 0 /* todo_flags_finish */
+ }
};
}
-struct tree_opt_pass pass_df_finish =
+struct rtl_opt_pass pass_df_finish =
{
+ {
+ RTL_PASS,
"dfinish", /* name */
NULL, /* gate */
rest_of_handle_df_finish, /* execute */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- 0, /* todo_flags_finish */
- 'z' /* letter */
+ 0 /* todo_flags_finish */
+ }
};
}
+
+/* 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,
+ bitmap pending,
+ sbitmap considered,
+ int *blocks_in_postorder,
+ unsigned *bbindex_to_postorder)
+{
+ enum df_flow_dir dir = dataflow->problem->dir;
+ int dcount = 0;
+ bitmap worklist = BITMAP_ALLOC (&df_bitmap_obstack);
+
+ /* Double-queueing. Worklist is for the current iteration,
+ and pending is for the next. */
+ while (!bitmap_empty_p (pending))
+ {
+ /* Swap pending and worklist. */
+ bitmap temp = worklist;
+ worklist = pending;
+ pending = temp;
+
+ do
+ {
+ int index;
+ unsigned bb_index;
+ dcount++;
+
+ index = bitmap_first_set_bit (worklist);
+ bitmap_clear_bit (worklist, 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);
+ }
+ while (!bitmap_empty_p (worklist));
+ }
+
+ BITMAP_FREE (worklist);
+ BITMAP_FREE (pending);
+
+ /* Dump statistics. */
+ if (dump_file)
+ fprintf (dump_file, "df_worklist_dataflow_doublequeue:"
+ "n_basic_blocks %d n_edges %d"
+ " count %d (%5.2g)\n",
+ n_basic_blocks, n_edges,
+ dcount, dcount / (float)n_basic_blocks);
+}
+
/* 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
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. */
+ 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.
+ */
void
df_worklist_dataflow (struct dataflow *dataflow,
bitmap_set_bit (pending, i);
}
+ /* Initialize the problem. */
if (dataflow->problem->init_fun)
dataflow->problem->init_fun (blocks_to_consider);
- while (!bitmap_empty_p (pending))
+ /* 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)
{
- unsigned bb_index;
-
- 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);
+ /* 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);
}
- BITMAP_FREE (pending);
sbitmap_free (considered);
free (bbindex_to_postorder);
}
if (dump_file)
fprintf (dump_file, "df_analyze called\n");
-#ifdef ENABLE_DF_CHECKING
- df_verify ();
-#endif
+#ifndef ENABLE_DF_CHECKING
+ if (df->changeable_flags & DF_VERIFY_SCHEDULED)
+#endif
+ df_verify ();
for (i = 0; i < df->n_blocks; i++)
bitmap_set_bit (current_all_blocks, df->postorder[i]);
df_verify (void)
{
df_scan_verify ();
+#ifdef ENABLE_DF_CHECKING
df_lr_verify_transfer_functions ();
if (df_live)
df_live_verify_transfer_functions ();
+#endif
}
#ifdef DF_DEBUG_CFG
}
+/* 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
df_dump (FILE *file)
{
}
+/* Dump dataflow info for df->blocks_to_analyze. */
+
+void
+df_dump_region (FILE *file)
+{
+ if (df->blocks_to_analyze)
+ {
+ bitmap_iterator bi;
+ unsigned int bb_index;
+
+ fprintf (file, "\n\nstarting region dump\n");
+ df_dump_start (file);
+
+ EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
+ {
+ basic_block bb = BASIC_BLOCK (bb_index);
+
+ df_print_bb_index (bb, file);
+ df_dump_top (bb, file);
+ df_dump_bottom (bb, file);
+ }
+ fprintf (file, "\n");
+ }
+ else
+ df_dump (file);
+}
+
+
/* Dump the introductory information for each problem defined. */
void
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");
}
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_INSN_INFO (ref) ? INSN_UID (DF_REF_INSN (ref)) : -1,
DF_REF_FLAGS (ref),
DF_REF_TYPE (ref));
if (DF_REF_LOC (ref))
OSDN Git Service
