This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH] rewrite fwprop's dataflow


Paolo Bonzini wrote:
This patch improves the compile-time of fwprop on the PR33928 testcase
by rewriting its dataflow analysis to not use reaching definitions.
RD is just too complex to work on the Gambit-scheme testcases, which
have a very convoluted and irreducible CFG.  The resulting bitmaps
are expensive to compute and they are very dense so that they take a
lot of memory.

The new problem computes registers that have multiple reaching
definitions (I'll trim it to live registers in a follow-up patch).
I don't think the new problem is anywhere in the literature, so some
explanation is in order.

The gen and kill sets for the problem are obvious.  Together they
include all defined registers in a basic block; The gen set includes
registers where a partial or conditional or may-clobber definition is
last in the BB, while the kill set includes registers with a complete
definition coming last.

The idea behind it comes from SSA form's iterated dominance frontier
criterion for inserting PHI functions.  Just like in that case, we can use
the dominance frontier to find places where multiple definitions meet;
a register X defined in a basic block BB1 has multiple definitions in
basic blocks in BB1's dominance frontier.

So, the in-set of a basic block BB2 is not just the union of the
out-sets of BB2's predecessors, but includes some more bits that come
from the basic blocks of whose dominance frontier BB2 is part (BB1 in
the previous paragraph).  I called this set the init-set of BB2.

  (Note: I actually use the kill-set only to build the init-set.
  gen bits are anyway propagated from BB1 to BB2 by dataflow).

For example, if you have

   BB1 : r10 = 0
         r11 = 0
         if <...> goto BB2 else goto BB3;

   BB2 : r10 = 1
         r12 = 1
         goto BB3;

BB3 :

you have BB3 in BB2's dominance frontier but not in BB1's, so that the
init-set of BB3 includes r10 and r12, but not r11.  Note that we do
not need to iterate the dominance frontier, because we do not insert
anything like PHI functions there!  Instead, dataflow will take care of
propagating the information to BB3's successors.

The information is used in fwprop with a dominator walk.  Again this
is similar to SSA form creation, but instead of creating a PHI function
where multiple definitions meet I just punt and record only singleton
use-def chains, as in current fwprop.

This has a subtle change in that we record only dominating definitions.
However, non-dominating definitions were eliminated anyway later, in
use_killed_between.  I left the code in use_killed_between anyway,
even though I'm not sure it is still useful, in case it is needed when
forward propagations cascade.

This patch does not change the generated code on PR33928 and, on the
really nasty compiler.i file posted there it brings fwprop time down
from 90s on a non-checking compiler (80s in RD, 9s in fwprop) to 3s
on a checking compiler (2s in MD, 1s in fwprop).

Bootstrapped/regtested x86_64-pc-linux-gnu, ok?
This explanation should be part of the body of the code, not something that will be lost in the mail. Given that this is effectively a new and unique problem, this is especially important.

The dataflow code is fine. I am not authorized to approve the changes to fwprop.c

Kenny

Paolo

2009-06-07 Paolo Bonzini <bonzini@gnu.org>

	* timevar.def: Remove TV_DF_RU, add TV_DF_MD.
	* df-problems.c (df_rd_add_problem): Fix comment.
	(df_md_set_bb_info, df_md_free_bb_info, df_md_alloc,
	df_md_simulate_artificial_defs_at_top,
	df_md_simulate_one_insn, df_md_bb_local_compute_process_def,
	df_md_bb_local_compute, df_md_local_compute, df_md_reset,
	df_md_transfer_function, df_md_init, df_md_confluence_0,
	df_md_confluence_n, df_md_free, df_md_top_dump, df_md_bottom_dump,
	problem_MD, df_md_add_problem): New.
	* df.h (DF_MD, DF_MD_BB_INFO, struct df_md_bb_info, df_md,
	df_md_get_bb_info): New.
	DF_LAST_PROBLEM_PLUS1): Adjust.

	* Makefile.in (fwprop.o): Include domwalk.h.
	* fwprop.c: Include domwalk.h.
	(reg_defs, reg_defs_stack): New.
	(bitmap_only_bit_between): Remove.
	(process_defs): New.
	(process_uses): Use reg_defs and local_md instead of
	bitmap_only_bit_between and local_rd.
	(single_def_use_enter_block): New, from build_single_def_use_links.
	(single_def_use_leave_block): New.
	(build_single_def_use_links): Remove code moved to
	single_def_use_enter_block, invoke domwalk.
	(use_killed_between): Adjust comment.

Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in (branch rebase-fwprop-md)
+++ gcc/Makefile.in (working copy)
@@ -2730,7 +2730,7 @@ dse.o : dse.c $(CONFIG_H) $(SYSTEM_H) co
fwprop.o : fwprop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
$(TOPLEV_H) insn-config.h $(RECOG_H) $(FLAGS_H) $(OBSTACK_H) $(BASIC_BLOCK_H) \
output.h $(DF_H) alloc-pool.h $(TIMEVAR_H) $(TREE_PASS_H) $(TARGET_H) \
- $(TM_P_H) $(CFGLOOP_H) $(EMIT_RTL_H)
+ $(TM_P_H) $(CFGLOOP_H) $(EMIT_RTL_H) domwalk.h
web.o : web.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
hard-reg-set.h $(FLAGS_H) $(BASIC_BLOCK_H) $(FUNCTION_H) output.h $(TOPLEV_H) \
$(DF_H) $(OBSTACK_H) $(TIMEVAR_H) $(TREE_PASS_H)
Index: gcc/timevar.def
===================================================================
--- gcc/timevar.def (branch rebase-fwprop-md)
+++ gcc/timevar.def (working copy)
@@ -58,7 +58,7 @@ DEFTIMEVAR (TV_LIFE_UPDATE , "life /* Time spent in dataflow problems. */
DEFTIMEVAR (TV_DF_SCAN , "df scan insns")
-DEFTIMEVAR (TV_DF_RU , "df reaching uses")
+DEFTIMEVAR (TV_DF_MD , "df multiple defs")
DEFTIMEVAR (TV_DF_RD , "df reaching defs")
DEFTIMEVAR (TV_DF_LR , "df live regs")
DEFTIMEVAR (TV_DF_LIVE , "df live&initialized regs")
Index: gcc/df-problems.c
===================================================================
--- gcc/df-problems.c (branch rebase-fwprop-md)
+++ gcc/df-problems.c (working copy)
@@ -726,9 +726,8 @@ static struct df_problem problem_RD =
-/* Create a new DATAFLOW instance and add it to an existing instance
- of DF. The returned structure is what is used to get at the
- solution. */
+/* Create a new RD instance and add it to the existing instance
+ of DF. */
void
df_rd_add_problem (void)
@@ -3950,3 +3949,405 @@ df_simulate_finalize_forwards (basic_blo
bitmap_clear_bit (live, DF_REF_REGNO (def));
}
}
+
+
+
+/*----------------------------------------------------------------------------
+ MULTIPLE DEFINITIONS
+
+ Find the locations in the function reached by multiple definition sites
+ for a pseudo. In and out bitvectors are built for each basic
+ block.
+ ---------------------------------------------------------------------------*/
+
+/* Set basic block info. */
+
+static void
+df_md_set_bb_info (unsigned int index, + struct df_md_bb_info *bb_info)
+{
+ gcc_assert (df_md);
+ gcc_assert (index < df_md->block_info_size);
+ df_md->block_info[index] = bb_info;
+}
+
+
+static void
+df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, + void *vbb_info)
+{
+ struct df_md_bb_info *bb_info = (struct df_md_bb_info *) vbb_info;
+ if (bb_info)
+ {
+ BITMAP_FREE (bb_info->kill);
+ BITMAP_FREE (bb_info->gen);
+ BITMAP_FREE (bb_info->init);
+ BITMAP_FREE (bb_info->in);
+ BITMAP_FREE (bb_info->out);
+ pool_free (df_md->block_pool, bb_info);
+ }
+}
+
+
+/* Allocate or reset bitmaps for DF_MD. The solution bits are
+ not touched unless the block is new. */
+
+static void +df_md_alloc (bitmap all_blocks)
+{
+ unsigned int bb_index;
+ bitmap_iterator bi;
+
+ if (!df_md->block_pool)
+ df_md->block_pool = create_alloc_pool ("df_md_block pool", + sizeof (struct df_md_bb_info), 50);
+
+ df_grow_bb_info (df_md);
+
+ EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+ {
+ struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
+ if (bb_info)
+ { + bitmap_clear (bb_info->init);
+ bitmap_clear (bb_info->gen);
+ bitmap_clear (bb_info->kill);
+ bitmap_clear (bb_info->in);
+ bitmap_clear (bb_info->out);
+ }
+ else
+ { + bb_info = (struct df_md_bb_info *) pool_alloc (df_md->block_pool);
+ df_md_set_bb_info (bb_index, bb_info);
+ bb_info->init = BITMAP_ALLOC (NULL);
+ bb_info->gen = BITMAP_ALLOC (NULL);
+ bb_info->kill = BITMAP_ALLOC (NULL);
+ bb_info->in = BITMAP_ALLOC (NULL);
+ bb_info->out = BITMAP_ALLOC (NULL);
+ }
+ }
+
+ df_md->optional_p = true;
+}
+
+/* Add the effect of the top artificial defs of BB to the multiple definitions
+ bitmap LOCAL_MD. */
+
+void
+df_md_simulate_artificial_defs_at_top (basic_block bb, bitmap local_md)
+{
+ int bb_index = bb->index;
+ df_ref *def_rec;
+ for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
+ {
+ 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 | DF_REF_MAY_CLOBBER))
+ bitmap_set_bit (local_md, dregno);
+ else
+ bitmap_clear_bit (local_md, dregno);
+ }
+ }
+}
+
+
+/* Add the effect of the defs of INSN to the reaching definitions bitmap
+ LOCAL_MD. */
+
+void
+df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx insn,
+ bitmap local_md)
+{
+ unsigned uid = INSN_UID (insn);
+ df_ref *def_rec;
+
+ for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+ {
+ df_ref def = *def_rec;
+ unsigned int dregno = DF_REF_REGNO (def);
+ if ((!(df->changeable_flags & DF_NO_HARD_REGS))
+ || (dregno >= FIRST_PSEUDO_REGISTER))
+ {
+ if (DF_REF_FLAGS (def)
+ & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
+ bitmap_set_bit (local_md, DF_REF_ID (def));
+ else
+ bitmap_clear_bit (local_md, DF_REF_ID (def));
+ }
+ }
+}
+
+static void
+df_md_bb_local_compute_process_def (struct df_md_bb_info *bb_info, + df_ref *def_rec,
+ int top_flag)
+{
+ df_ref def;
+ bitmap_clear (seen_in_insn);
+
+ while ((def = *def_rec++) != NULL)
+ {
+ unsigned int dregno = DF_REF_REGNO (def);
+ if (((!(df->changeable_flags & DF_NO_HARD_REGS))
+ || (dregno >= FIRST_PSEUDO_REGISTER))
+ && top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
+ {
+ if (!bitmap_bit_p (seen_in_insn, dregno))
+ {
+ if (DF_REF_FLAGS (def)
+ & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
+ {
+ bitmap_set_bit (bb_info->gen, dregno);
+ bitmap_clear_bit (bb_info->kill, dregno);
+ }
+ else
+ {
+ /* When we find a clobber and a regular def,
+ make sure the regular def wins. */
+ bitmap_set_bit (seen_in_insn, dregno);
+ bitmap_set_bit (bb_info->kill, dregno);
+ bitmap_clear_bit (bb_info->gen, dregno);
+ }
+ }
+ }
+ }
+}
+
+
+/* Compute local multiple def info for basic block BB. */
+
+static void
+df_md_bb_local_compute (unsigned int bb_index)
+{
+ basic_block bb = BASIC_BLOCK (bb_index);
+ struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
+ rtx insn;
+
+ /* Artificials are only hard regs. */
+ if (!(df->changeable_flags & DF_NO_HARD_REGS))
+ df_md_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))
+ continue;
+
+ df_md_bb_local_compute_process_def (bb_info, DF_INSN_UID_DEFS (uid), 0);
+ }
+
+ if (!(df->changeable_flags & DF_NO_HARD_REGS))
+ df_md_bb_local_compute_process_def (bb_info, + df_get_artificial_defs (bb_index),
+ 0);
+}
+
+/* Compute local reaching def info for each basic block within BLOCKS. */
+
+static void
+df_md_local_compute (bitmap all_blocks)
+{
+ unsigned int bb_index, df_bb_index;
+ bitmap_iterator bi1, bi2;
+ basic_block bb;
+ bitmap *frontiers;
+
+ df_set_seen ();
+
+ EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
+ {
+ df_md_bb_local_compute (bb_index);
+ }
+ + df_unset_seen ();
+
+ frontiers = XNEWVEC (bitmap, last_basic_block);
+ FOR_ALL_BB (bb)
+ frontiers[bb->index] = BITMAP_ALLOC (NULL);
+
+ compute_dominance_frontiers (frontiers);
+
+ /* Add each basic block's kills to the nodes in the frontier of the BB. */
+ EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
+ {
+ bitmap kill = df_md_get_bb_info (bb_index)->kill;
+ EXECUTE_IF_SET_IN_BITMAP (frontiers[bb_index], 0, df_bb_index, bi2)
+ {
+ if (bitmap_bit_p (all_blocks, df_bb_index))
+ bitmap_ior_into (df_md_get_bb_info (df_bb_index)->init, kill);
+ }
+ }
+}
+
+
+/* Reset the global solution for recalculation. */
+
+static void +df_md_reset (bitmap all_blocks)
+{
+ unsigned int bb_index;
+ bitmap_iterator bi;
+
+ EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+ {
+ struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
+ gcc_assert (bb_info);
+ bitmap_clear (bb_info->in);
+ bitmap_clear (bb_info->out);
+ }
+}
+
+static bool
+df_md_transfer_function (int bb_index)
+{
+ struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
+ bitmap in = bb_info->in;
+ bitmap out = bb_info->out;
+ bitmap gen = bb_info->gen;
+ bitmap kill = bb_info->kill;
+
+ return bitmap_ior_and_compl (out, gen, in, kill);
+}
+
+/* Initialize the solution bit vectors for problem. */
+
+static void +df_md_init (bitmap all_blocks)
+{
+ unsigned int bb_index;
+ bitmap_iterator bi;
+
+ EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+ {
+ struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
+ + bitmap_copy (bb_info->in, bb_info->init);
+ df_md_transfer_function (bb_index);
+ }
+}
+
+static void
+df_md_confluence_0 (basic_block bb)
+{
+ struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
+ bitmap_copy (bb_info->in, bb_info->init);
+} +
+/* In of target gets or of out of source. */
+
+static void
+df_md_confluence_n (edge e)
+{
+ bitmap op1 = df_md_get_bb_info (e->dest->index)->in;
+ bitmap op2 = df_md_get_bb_info (e->src->index)->out;
+
+ if (e->flags & EDGE_FAKE) + return;
+
+ if (e->flags & EDGE_EH)
+ bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset);
+ else
+ bitmap_ior_into (op1, op2);
+}
+
+/* Free all storage associated with the problem. */
+
+static void
+df_md_free (void)
+{
+ unsigned int i;
+ for (i = 0; i < df_md->block_info_size; i++)
+ {
+ struct df_md_bb_info *bb_info = df_md_get_bb_info (i);
+ if (bb_info)
+ {
+ BITMAP_FREE (bb_info->kill);
+ BITMAP_FREE (bb_info->gen);
+ BITMAP_FREE (bb_info->init);
+ BITMAP_FREE (bb_info->in);
+ BITMAP_FREE (bb_info->out);
+ }
+ }
+
+ free_alloc_pool (df_md->block_pool);
+
+ df_md->block_info_size = 0;
+ free (df_md->block_info);
+ free (df_md);
+}
+
+
+/* Debugging info at top of bb. */
+
+static void
+df_md_top_dump (basic_block bb, FILE *file)
+{
+ struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
+ if (!bb_info || !bb_info->in)
+ return;
+ + fprintf (file, ";; md in \t");
+ df_print_regset (file, bb_info->in);
+ fprintf (file, ";; md init \t");
+ df_print_regset (file, bb_info->init);
+ fprintf (file, ";; md gen \t");
+ df_print_regset (file, bb_info->gen);
+ fprintf (file, ";; md kill \t");
+ df_print_regset (file, bb_info->kill);
+}
+
+/* Debugging info at bottom of bb. */
+
+static void
+df_md_bottom_dump (basic_block bb, FILE *file)
+{
+ struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
+ if (!bb_info || !bb_info->out)
+ return;
+ + fprintf (file, ";; md out \t");
+ df_print_regset (file, bb_info->out);
+} +
+static struct df_problem problem_MD =
+{
+ DF_MD, /* Problem id. */
+ DF_FORWARD, /* Direction. */
+ df_md_alloc, /* Allocate the problem specific data. */
+ df_md_reset, /* Reset global information. */
+ df_md_free_bb_info, /* Free basic block info. */
+ df_md_local_compute, /* Local compute function. */
+ df_md_init, /* Init the solution specific data. */
+ df_worklist_dataflow, /* Worklist solver. */
+ df_md_confluence_0, /* Confluence operator 0. */ + df_md_confluence_n, /* Confluence operator n. */ + df_md_transfer_function, /* Transfer function. */
+ NULL, /* Finalize function. */
+ df_md_free, /* Free all of the problem information. */
+ df_md_free, /* Remove this problem from the stack of dataflow problems. */
+ NULL, /* Debugging. */
+ df_md_top_dump, /* Debugging start block. */
+ df_md_bottom_dump, /* Debugging end block. */
+ NULL, /* Incremental solution verify start. */
+ NULL, /* Incremental solution verify end. */
+ NULL, /* Dependent problem. */
+ TV_DF_MD, /* Timing variable. */ + false /* Reset blocks on dropping out of blocks_to_analyze. */
+};
+
+/* Create a new MD instance and add it to the existing instance
+ of DF. */
+
+void
+df_md_add_problem (void)
+{
+ df_add_problem (&problem_MD);
+}
+
+
+
Index: gcc/df.h
===================================================================
--- gcc/df.h (branch rebase-fwprop-md)
+++ gcc/df.h (working copy)
@@ -52,8 +52,9 @@ union df_ref_d;
#define DF_CHAIN 4 /* Def-Use and/or Use-Def Chains. */
#define DF_BYTE_LR 5 /* Subreg tracking lr. */
#define DF_NOTE 6 /* REG_DEF and REG_UNUSED notes. */
+#define DF_MD 7 /* Multiple Definitions. */
-#define DF_LAST_PROBLEM_PLUS1 (DF_NOTE + 1)
+#define DF_LAST_PROBLEM_PLUS1 (DF_MD + 1)
/* Dataflow direction. */
enum df_flow_dir
@@ -619,6 +620,7 @@ struct df
#define DF_LR_BB_INFO(BB) (df_lr_get_bb_info((BB)->index))
#define DF_LIVE_BB_INFO(BB) (df_live_get_bb_info((BB)->index))
#define DF_BYTE_LR_BB_INFO(BB) (df_byte_lr_get_bb_info((BB)->index))
+#define DF_MD_BB_INFO(BB) (df_md_get_bb_info((BB)->index))
/* Most transformations that wish to use live register analysis will
use these macros. This info is the and of the lr and live sets. */
@@ -802,6 +804,22 @@ struct df_rd_bb_info };
+/* Multiple reaching definitions. All bitmaps are referenced by the
+ register number. */
+
+struct df_md_bb_info +{
+ /* Local sets to describe the basic blocks. */
+ bitmap gen; /* Partial/conditional definitions live at BB out. */
+ bitmap kill; /* Other definitions that are live at BB out. */
+ bitmap init; /* Definitions coming from dominance frontier edges. */
+
+ /* The results of the dataflow problem. */
+ bitmap in; /* Just before the block itself. */
+ bitmap out; /* At the bottom of the block. */
+};
+
+
/* Live registers, a backwards dataflow problem. All bitmaps are
referenced by the register number. */
@@ -862,6 +880,7 @@ extern struct df *df;
#define df_chain (df->problems_by_index[DF_CHAIN])
#define df_byte_lr (df->problems_by_index[DF_BYTE_LR])
#define df_note (df->problems_by_index[DF_NOTE])
+#define df_md (df->problems_by_index[DF_MD])
/* This symbol turns on checking that each modification of the cfg has
been identified to the appropriate df routines. It is not part of
@@ -955,6 +974,9 @@ extern void df_byte_lr_simulate_uses (rt
extern void df_byte_lr_simulate_artificial_refs_at_top (basic_block, bitmap);
extern void df_byte_lr_simulate_artificial_refs_at_end (basic_block, bitmap);
extern void df_note_add_problem (void);
+extern void df_md_add_problem (void);
+extern void df_md_simulate_artificial_defs_at_top (basic_block, bitmap);
+extern void df_md_simulate_one_insn (basic_block, rtx, bitmap);
extern void df_simulate_find_defs (rtx, bitmap);
extern void df_simulate_defs (rtx, bitmap);
extern void df_simulate_uses (rtx, bitmap);
@@ -1034,6 +1056,15 @@ df_lr_get_bb_info (unsigned int index)
return NULL;
}
+static inline struct df_md_bb_info *
+df_md_get_bb_info (unsigned int index)
+{
+ if (index < df_md->block_info_size)
+ return (struct df_md_bb_info *) df_md->block_info[index];
+ else
+ return NULL;
+}
+
static inline struct df_live_bb_info *
df_live_get_bb_info (unsigned int index)
{
Index: gcc/fwprop.c
===================================================================
--- gcc/fwprop.c (branch rebase-fwprop-md)
+++ gcc/fwprop.c (working copy)
@@ -38,6 +38,7 @@ along with GCC; see the file COPYING3. #include "target.h"
#include "cfgloop.h"
#include "tree-pass.h"
+#include "domwalk.h"
/* This pass does simple forward propagation and simplification when an
@@ -108,6 +109,8 @@ static int num_changes;
DEF_VEC_P(df_ref);
DEF_VEC_ALLOC_P(df_ref,heap);
VEC(df_ref,heap) *use_def_ref;
+VEC(df_ref,heap) *reg_defs;
+VEC(df_ref,heap) *reg_defs_stack;
/* Return the only def in USE's use-def chain, or NULL if there is
@@ -120,96 +123,168 @@ get_def_for_use (df_ref use)
}
-/* Return the only bit between FIRST and LAST that is set in B,
- or -1 if there are zero or more than one such bits. */
+/* Update the reg_defs vector with non-partial definitions in DEF_REC.
+ TOP_FLAG says which artificials uses should be used, when DEF_REC
+ is an artificial def vector. LOCAL_MD is modified as after a
+ df_md_simulate_* function; we do more or less the same processing
+ done there, so we do not use those functions. */
-static inline int
-bitmap_only_bit_between (const_bitmap b, unsigned first, unsigned last)
+#define DF_MD_GEN_FLAGS \
+ (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER)
+
+static void
+process_defs (bitmap local_md, df_ref *def_rec, int top_flag)
{
- bitmap_iterator bi;
- unsigned bit, bit2;
+ df_ref def;
+ while ((def = *def_rec++) != NULL)
+ {
+ df_ref curr_def = VEC_index (df_ref, reg_defs, DF_REF_REGNO (def));
+ unsigned int dregno;
- if (last < first)
- return -1;
+ if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) != top_flag)
+ continue;
- bmp_iter_set_init (&bi, b, first, &bit);
- if (bmp_iter_set (&bi, &bit) && bit <= last)
- {
- bit2 = bit;
- bmp_iter_next (&bi, &bit2);
- if (!bmp_iter_set (&bi, &bit2) || bit2 > last)
- return bit;
+ dregno = DF_REF_REGNO (def);
+ if (curr_def)
+ VEC_safe_push (df_ref, heap, reg_defs_stack, curr_def);
+ else
+ {
+ /* Do not store anything if "transitioning" from NULL to NULL. But
+ otherwise, push a special entry on the stack to tell the
+ leave_block callback that the entry in reg_defs was NULL. */
+ if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS)
+ ;
+ else
+ VEC_safe_push (df_ref, heap, reg_defs_stack, def);
+ }
+
+ if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS)
+ {
+ bitmap_set_bit (local_md, dregno);
+ VEC_replace (df_ref, reg_defs, dregno, NULL);
+ }
+ else
+ {
+ bitmap_clear_bit (local_md, dregno);
+ VEC_replace (df_ref, reg_defs, dregno, def);
+ }
}
- return -1;
}
/* Fill the use_def_ref vector with values for the uses in USE_REC,
- taking reaching definitions info from LOCAL_RD. TOP_FLAG says
- which artificials uses should be used, when USE_REC is an
- artificial use vector. */
+ taking reaching definitions info from LOCAL_MD and REG_DEFS.
+ TOP_FLAG says which artificials uses should be used, when USE_REC
+ is an artificial use vector. */
static void
-process_uses (bitmap local_rd, df_ref *use_rec, int top_flag)
+process_uses (bitmap local_md, df_ref *use_rec, int top_flag)
{
df_ref use;
while ((use = *use_rec++) != NULL)
- if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
+ if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == top_flag)
{
- unsigned int uregno = DF_REF_REGNO (use);
- unsigned int first = DF_DEFS_BEGIN (uregno);
- unsigned int last = first + DF_DEFS_COUNT (uregno) - 1;
- int defno = bitmap_only_bit_between (local_rd, first, last);
- df_ref def = (defno == -1) ? NULL : DF_DEFS_GET (defno);
+ unsigned int uregno = DF_REF_REGNO (use);
+ if (VEC_index (df_ref, reg_defs, uregno)
+ && !bitmap_bit_p (local_md, uregno))
+ VEC_replace (df_ref, use_def_ref, DF_REF_ID (use),
+ VEC_index (df_ref, reg_defs, uregno));
+ }
+}
+
- VEC_replace (df_ref, use_def_ref, DF_REF_ID (use), def);
+static void
+single_def_use_enter_block (struct dom_walk_data *walk_data, basic_block bb)
+{
+ bitmap local_md = (bitmap) walk_data->global_data;
+ int bb_index = bb->index;
+ struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
+ rtx insn;
+
+ bitmap_copy (local_md, bb_info->in);
+
+ /* Push a marker for the leave_block callback. */
+ VEC_safe_push (df_ref, heap, reg_defs_stack, NULL);
+
+ process_uses (local_md, df_get_artificial_uses (bb_index), DF_REF_AT_TOP);
+ process_defs (local_md, df_get_artificial_defs (bb_index), DF_REF_AT_TOP);
+
+ FOR_BB_INSNS (bb, insn)
+ if (INSN_P (insn))
+ {
+ unsigned int uid = INSN_UID (insn);
+ process_uses (local_md, DF_INSN_UID_USES (uid), 0);
+ process_uses (local_md, DF_INSN_UID_EQ_USES (uid), 0);
+ process_defs (local_md, DF_INSN_UID_DEFS (uid), 0);
}
+
+ process_uses (local_md, df_get_artificial_uses (bb_index), 0);
+ process_defs (local_md, df_get_artificial_defs (bb_index), 0);
+}
+
+/* Pop the definitions created in this basic block when leaving its
+ dominated parts. */
+
+static void
+single_def_use_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+ basic_block bb ATTRIBUTE_UNUSED)
+{
+ df_ref saved_def;
+ while ((saved_def = VEC_pop (df_ref, reg_defs_stack)) != NULL)
+ {
+ unsigned int dregno = DF_REF_REGNO (saved_def);
+
+ /* See also process_defs. */
+ if (saved_def == VEC_index (df_ref, reg_defs, dregno))
+ VEC_replace (df_ref, reg_defs, dregno, NULL);
+ else
+ VEC_replace (df_ref, reg_defs, dregno, saved_def);
+ }
}
-/* Do dataflow analysis and use reaching definitions to build
- a vector holding the reaching definitions of uses that have a
- single RD. */
+/* Build a vector holding the reaching definitions of uses reached by a
+ single dominating definition. */
static void
build_single_def_use_links (void)
{
- basic_block bb;
- bitmap local_rd = BITMAP_ALLOC (NULL);
+ struct dom_walk_data walk_data;
+ bitmap local_md;
- /* We use reaching definitions to compute our restricted use-def chains. */
+ /* We use the multiple definitions problem to compute our restricted
+ use-def chains. */
df_set_flags (DF_EQ_NOTES);
- df_rd_add_problem ();
+ df_md_add_problem ();
df_analyze ();
df_maybe_reorganize_use_refs (DF_REF_ORDER_BY_INSN_WITH_NOTES);
use_def_ref = VEC_alloc (df_ref, heap, DF_USES_TABLE_SIZE ());
- VEC_safe_grow (df_ref, heap, use_def_ref, DF_USES_TABLE_SIZE ());
+ VEC_safe_grow_cleared (df_ref, heap, use_def_ref, DF_USES_TABLE_SIZE ());
- FOR_EACH_BB (bb)
- {
- int bb_index = bb->index;
- struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
- rtx insn;
-
- bitmap_copy (local_rd, bb_info->in);
- process_uses (local_rd, df_get_artificial_uses (bb_index), DF_REF_AT_TOP);
-
- df_rd_simulate_artificial_defs_at_top (bb, local_rd);
- FOR_BB_INSNS (bb, insn)
- if (INSN_P (insn))
- {
- unsigned int uid = INSN_UID (insn);
- process_uses (local_rd, DF_INSN_UID_USES (uid), 0);
- process_uses (local_rd, DF_INSN_UID_EQ_USES (uid), 0);
- df_rd_simulate_one_insn (bb, insn, local_rd);
- }
+ reg_defs = VEC_alloc (df_ref, heap, max_reg_num ());
+ VEC_safe_grow_cleared (df_ref, heap, reg_defs, max_reg_num ());
- process_uses (local_rd, df_get_artificial_uses (bb_index), 0);
- }
+ reg_defs_stack = VEC_alloc (df_ref, heap, n_basic_blocks * 10);
+ local_md = BITMAP_ALLOC (NULL);
- BITMAP_FREE (local_rd);
+ /* Walk the dominator tree looking for single reaching definitions
+ dominating the uses. This is similar to how SSA form is built. */
+ walk_data.dom_direction = CDI_DOMINATORS;
+ walk_data.initialize_block_local_data = NULL;
+ walk_data.before_dom_children = single_def_use_enter_block;
+ walk_data.after_dom_children = single_def_use_leave_block;
+ walk_data.global_data = local_md;
+
+ init_walk_dominator_tree (&walk_data);
+ walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
+ fini_walk_dominator_tree (&walk_data);
+
+ BITMAP_FREE (local_md);
+ VEC_free (df_ref, heap, reg_defs);
+ VEC_free (df_ref, heap, reg_defs_stack);
}
+

/* Do not try to replace constant addresses or addresses of local and
argument slots. These MEM expressions are made only once and inserted
@@ -629,12 +704,12 @@ use_killed_between (df_ref use, rtx def_
int regno;
df_ref def;
- /* In some obscure situations we can have a def reaching a use
- that is _before_ the def. In other words the def does not
- dominate the use even though the use and def are in the same
- basic block. This can happen when a register may be used
- uninitialized in a loop. In such cases, we must assume that
- DEF is not available. */
+ /* We used to have a def reaching a use that is _before_ the def,
+ with the def not dominating the use even though the use and def
+ are in the same basic block, when a register may be used
+ uninitialized in a loop. This should not happen anymore since
+ we do not use reaching definitions, but still we test for such
+ cases and assume that DEF is not available. */
if (def_bb == target_bb
? DF_INSN_LUID (def_insn) >= DF_INSN_LUID (target_insn)
: !dominated_by_p (CDI_DOMINATORS, target_bb, def_bb))




Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]