This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[dataflow]: PATCH COMMITTED to add df insn flow routines.
- From: Kenneth Zadeck <zadeck at naturalbridge dot com>
- To: Andrey Belevantsev <abel at ispras dot ru>, gcc-patches <gcc-patches at gcc dot gnu dot org>, "Park, Seongbae" <seongbae dot park at gmail dot com>, Steven Bosscher <stevenb dot gcc at gmail dot com>, "Zadeck, Kenneth" <zadeck at naturalbridge dot com>
- Date: Thu, 17 May 2007 08:50:04 -0400
- Subject: [dataflow]: PATCH COMMITTED to add df insn flow routines.
This patch adds new rountines to compute live information on a statement
by statement basis. These functions provide much of the functionality
of propagate_one_insn. There are versions for either going forwards or
backwards in a block and you can start with either the live or lr sets.
The rest of the patch deals with replacing uses of older, less general
versions of this and in the case of ifcvt, just regular code that did
some of the same things.
These functions had been requested by several people.
This patch has been bootstrapped and regression tested on x86-64,
x86-32, ppc and ia-64.
kenny
2007-05-17 Kenneth Zadeck <zadeck@naturalbridge.com>
* ifcvt.c (dead_or_predictable): Replaced insn dfa with new df
routines.
* recog.c (peephole2_optimize): Replaced
df_lr_simulate_artificial_refs_at_end and df_lr_simulate_one_insn
with df_simulate_artificial_refs_at_end and
df_simulate_one_insn_backwards.
* rtl-factoring.c (collect_pattern_seqs, clear_regs_live_in_seq):
Ditto.
* df.h (df_lr_simulate_artificial_refs_at_end,
df_lr_simulate_one_insn): Removed.
(df_simulate_find_defs, df_simulate_artificial_refs_at_top,
df_simulate_one_insn_forwards, df_simulate_artificial_refs_at_end,
df_simulate_one_insn_backwards): Added.
* df-problems.c (df_lr_bb_local_compute): Removed unnecessary
tests.
(df_lr_simulate_artificial_refs_at_end, df_lr_simulate_one_insn):
Removed.
(df_simulate_find_defs, df_simulate_defs, df_simulate_uses,
df_simulate_fixup_sets, df_simulate_artificial_refs_at_top,
df_simulate_one_insn_forwards, df_simulate_artificial_refs_at_end,
df_simulate_one_insn_backwards): Added.
Index: ifcvt.c
===================================================================
--- ifcvt.c (revision 124770)
+++ ifcvt.c (working copy)
@@ -3837,23 +3837,13 @@ dead_or_predicable (basic_block test_bb,
/* The loop below takes the set of live registers
after JUMP, and calculates the live set before EARLIEST. */
bitmap_copy (test_live, DF_LIVE_IN (other_bb));
+ df_simulate_artificial_refs_at_end (test_bb, test_live);
for (insn = jump; ; insn = prev)
{
if (INSN_P (insn))
{
- unsigned int uid = INSN_UID (insn);
- struct df_ref **rec;
- for (rec = DF_INSN_UID_DEFS (uid); *rec; rec++)
- {
- struct df_ref *def = *rec;
- bitmap_set_bit (test_set, DF_REF_REGNO (def));
- bitmap_clear_bit (test_live, DF_REF_REGNO (def));
- }
- for (rec = DF_INSN_UID_USES (uid); *rec; rec++)
- {
- struct df_ref *def = *rec;
- bitmap_set_bit (test_live, DF_REF_REGNO (def));
- }
+ df_simulate_find_defs (insn, test_set);
+ df_simulate_one_insn_backwards (test_bb, insn, test_live);
}
prev = PREV_INSN (insn);
if (insn == earliest)
Index: recog.c
===================================================================
--- recog.c (revision 124770)
+++ recog.c (working copy)
@@ -2925,7 +2925,8 @@ peephole2_optimize (void)
peep2_current = MAX_INSNS_PER_PEEP2;
/* Start up propagation. */
- df_lr_simulate_artificial_refs_at_end (bb, live);
+ bitmap_copy (live, DF_LR_OUT (bb));
+ df_simulate_artificial_refs_at_end (bb, live);
bitmap_copy (peep2_insn_data[MAX_INSNS_PER_PEEP2].live_before, live);
for (insn = BB_END (bb); ; insn = prev)
@@ -2945,7 +2946,7 @@ peephole2_optimize (void)
&& peep2_insn_data[peep2_current].insn == NULL_RTX)
peep2_current_count++;
peep2_insn_data[peep2_current].insn = insn;
- df_lr_simulate_one_insn (bb, insn, live);
+ df_simulate_one_insn_backwards (bb, insn, live);
COPY_REG_SET (peep2_insn_data[peep2_current].live_before, live);
if (RTX_FRAME_RELATED_P (insn))
@@ -3107,7 +3108,7 @@ peephole2_optimize (void)
peep2_current_count++;
peep2_insn_data[i].insn = x;
df_insn_rescan (x);
- df_lr_simulate_one_insn (bb, x, live);
+ df_simulate_one_insn_backwards (bb, x, live);
bitmap_copy (peep2_insn_data[i].live_before, live);
}
x = PREV_INSN (x);
Index: rtl-factoring.c
===================================================================
--- rtl-factoring.c (revision 124770)
+++ rtl-factoring.c (working copy)
@@ -460,7 +460,8 @@ collect_pattern_seqs (void)
/* Initialize liveness propagation. */
INIT_REG_SET (&live);
- df_lr_simulate_artificial_refs_at_end (bb, &live);
+ bitmap_copy (&live, DF_LR_OUT (bb));
+ df_simulate_artificial_refs_at_end (bb, &live);
/* Propagate liveness info and mark insns where a stack reg is live. */
insn = BB_END (bb);
@@ -482,7 +483,7 @@ collect_pattern_seqs (void)
}
if (insn == BB_HEAD (bb))
break;
- df_lr_simulate_one_insn (bb, insn, &live);
+ df_simulate_one_insn_backwards (bb, insn, &live);
insn = prev;
}
@@ -545,11 +546,12 @@ clear_regs_live_in_seq (HARD_REG_SET * r
/* Initialize liveness propagation. */
bb = BLOCK_FOR_INSN (insn);
INIT_REG_SET (&live);
- df_lr_simulate_artificial_refs_at_end (bb, &live);
+ bitmap_copy (&live, DF_LR_OUT (bb));
+ df_simulate_artificial_refs_at_end (bb, &live);
/* Propagate until INSN if found. */
for (x = BB_END (bb); x != insn;)
- df_lr_simulate_one_insn (bb, insn, &live);
+ df_simulate_one_insn_backwards (bb, insn, &live);
/* Clear registers live after INSN. */
renumbered_reg_set_to_hard_reg_set (&hlive, &live);
@@ -559,7 +561,7 @@ clear_regs_live_in_seq (HARD_REG_SET * r
for (i = 0; i < length;)
{
rtx prev = PREV_INSN (x);
- df_lr_simulate_one_insn (bb, insn, &live);
+ df_simulate_one_insn_backwards (bb, insn, &live);
if (INSN_P (x))
{
Index: df.h
===================================================================
--- df.h (revision 124770)
+++ df.h (working copy)
@@ -879,8 +879,6 @@ extern void df_chain_dump (struct df_lin
extern void df_print_bb_index (basic_block bb, FILE *file);
extern void df_ru_add_problem (void);
extern void df_rd_add_problem (void);
-extern void df_lr_simulate_artificial_refs_at_end (basic_block, bitmap);
-extern void df_lr_simulate_one_insn (basic_block, rtx, bitmap);
extern void df_lr_add_problem (void);
extern void df_lr_verify_transfer_functions (void);
extern void df_live_verify_transfer_functions (void);
@@ -888,6 +886,11 @@ extern void df_live_add_problem (void);
extern void df_urec_add_problem (void);
extern void df_chain_add_problem (enum df_chain_flags);
extern void df_note_add_problem (void);
+extern void df_simulate_find_defs (rtx, bitmap);
+extern void df_simulate_artificial_refs_at_top (basic_block, bitmap);
+extern void df_simulate_one_insn_forwards (basic_block, rtx, bitmap);
+extern void df_simulate_artificial_refs_at_end (basic_block, bitmap);
+extern void df_simulate_one_insn_backwards (basic_block, rtx, bitmap);
/* Functions defined in df-scan.c. */
Index: df-problems.c
===================================================================
--- df-problems.c (revision 124770)
+++ df-problems.c (working copy)
@@ -1357,8 +1357,7 @@ df_lr_bb_local_compute (unsigned int bb_
for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
{
struct df_ref *def = *def_rec;
- if (((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
- && (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))))
+ if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
{
unsigned int dregno = DF_REF_REGNO (def);
bitmap_set_bit (bb_info->def, dregno);
@@ -1673,105 +1672,6 @@ df_lr_free (void)
}
-/* Public auxillary functions. */
-
-/* Get the variables live at the end of BB and apply the artifical
- uses and defs at the end of BB. */
-
-void
-df_lr_simulate_artificial_refs_at_end (basic_block bb, bitmap live)
-{
- struct df_ref **def_rec;
- struct df_ref **use_rec;
- int bb_index = bb->index;
-
- bitmap_copy (live, DF_LR_OUT (bb));
- for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
- {
- struct df_ref *def = *def_rec;
- if (((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
- && (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))))
- bitmap_clear_bit (live, DF_REF_REGNO (def));
- }
-
- for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
- {
- struct df_ref *use = *use_rec;
- if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
- bitmap_set_bit (live, DF_REF_REGNO (use));
- }
-}
-
-
-/* Simulate the effects of INSN on the bitmap LIVE. */
-void
-df_lr_simulate_one_insn (basic_block bb, rtx insn, bitmap live)
-{
- struct df_ref **def_rec;
- struct df_ref **use_rec;
- unsigned int uid = INSN_UID (insn);
-
- if (! INSN_P (insn))
- return;
-
- if (CALL_P (insn))
- {
- for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
- {
- struct df_ref *def = *def_rec;
- unsigned int dregno = DF_REF_REGNO (def);
-
- if (DF_REF_FLAGS (def) & DF_REF_MUST_CLOBBER)
- {
- if (dregno >= FIRST_PSEUDO_REGISTER
- || !(SIBLING_CALL_P (insn)
- && bitmap_bit_p (df->exit_block_uses, dregno)
- && !refers_to_regno_p (dregno, dregno+1,
- current_function_return_rtx,
- (rtx *)0)))
- {
- /* If the def is to only part of the reg, it does
- not kill the other defs that reach here. */
- if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
- bitmap_clear_bit (live, dregno);
- }
- }
- else
- /* This is the return value. */
- if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
- bitmap_clear_bit (live, dregno);
- }
- }
- else
- {
- for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
- {
- struct df_ref *def = *def_rec;
- unsigned int dregno = DF_REF_REGNO (def);
-
- /* If the def is to only part of the reg, it does
- not kill the other defs that reach here. */
- if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
- bitmap_clear_bit (live, dregno);
- }
- }
-
- for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
- {
- struct df_ref *use = *use_rec;
- /* Add use to set of uses in this BB. */
- bitmap_set_bit (live, DF_REF_REGNO (use));
- }
-
- /* These regs are considered always live so if they end up dying
- because of some def, we need to bring the back again. */
- if (df_has_eh_preds (bb))
- bitmap_ior_into (live, df->eh_block_artificial_uses);
- else
- bitmap_ior_into (live, df->regular_block_artificial_uses);
-}
-
-
/* Debugging info at top of bb. */
static void
@@ -4217,3 +4117,235 @@ df_note_add_problem (void)
}
+
+
+/*----------------------------------------------------------------------------
+ Functions for simulating the effects of single insns.
+
+ You can either simulate in the forwards direction, starting from
+ the top of a block or the backwards direction from the end of the
+ block. The main difference is that if you go forwards, the uses
+ are examined first then the defs, and if you go backwards, the defs
+ are examined first then the uses.
+
+ If you start at the top of the block, use one of DF_LIVE_IN or
+ DF_LR_IN. If you start at the bottom of the block use one of
+ DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS,
+ THEY WILL BE DESTROYED.
+
+----------------------------------------------------------------------------*/
+
+
+/* Find the set of DEFs for INSN. */
+
+void
+df_simulate_find_defs (rtx insn, bitmap defs)
+{
+ struct df_ref **def_rec;
+ unsigned int uid = INSN_UID (insn);
+
+ if (CALL_P (insn))
+ {
+ for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+ {
+ struct df_ref *def = *def_rec;
+ unsigned int dregno = DF_REF_REGNO (def);
+
+ if (DF_REF_FLAGS (def) & DF_REF_MUST_CLOBBER)
+ {
+ if (dregno >= FIRST_PSEUDO_REGISTER
+ || !(SIBLING_CALL_P (insn)
+ && bitmap_bit_p (df->exit_block_uses, dregno)
+ && !refers_to_regno_p (dregno, dregno+1,
+ current_function_return_rtx,
+ (rtx *)0)))
+ {
+ /* If the def is to only part of the reg, it does
+ not kill the other defs that reach here. */
+ if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
+ bitmap_set_bit (defs, dregno);
+ }
+ }
+ else
+ /* This is the return value. */
+ if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
+ bitmap_set_bit (defs, dregno);
+ }
+ }
+ else
+ {
+ for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+ {
+ struct df_ref *def = *def_rec;
+ /* If the def is to only part of the reg, it does
+ not kill the other defs that reach here. */
+ if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
+ bitmap_set_bit (defs, DF_REF_REGNO (def));
+ }
+ }
+}
+
+
+/* Simulate the effects of the defs of INSN on LIVE. */
+
+static inline void
+df_simulate_defs (rtx insn, bitmap live)
+{
+ struct df_ref **def_rec;
+ unsigned int uid = INSN_UID (insn);
+
+ if (CALL_P (insn))
+ {
+ for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+ {
+ struct df_ref *def = *def_rec;
+ unsigned int dregno = DF_REF_REGNO (def);
+
+ if (DF_REF_FLAGS (def) & DF_REF_MUST_CLOBBER)
+ {
+ if (dregno >= FIRST_PSEUDO_REGISTER
+ || !(SIBLING_CALL_P (insn)
+ && bitmap_bit_p (df->exit_block_uses, dregno)
+ && !refers_to_regno_p (dregno, dregno+1,
+ current_function_return_rtx,
+ (rtx *)0)))
+ {
+ /* If the def is to only part of the reg, it does
+ not kill the other defs that reach here. */
+ if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
+ bitmap_clear_bit (live, dregno);
+ }
+ }
+ else
+ /* This is the return value. */
+ if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
+ bitmap_clear_bit (live, dregno);
+ }
+ }
+ else
+ {
+ for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+ {
+ struct df_ref *def = *def_rec;
+ unsigned int dregno = DF_REF_REGNO (def);
+
+ /* If the def is to only part of the reg, it does
+ not kill the other defs that reach here. */
+ if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
+ bitmap_clear_bit (live, dregno);
+ }
+ }
+}
+
+
+/* Simulate the effects of the uses of INSN on LIVE. */
+
+static inline void
+df_simulate_uses (rtx insn, bitmap live)
+{
+ struct df_ref **use_rec;
+ unsigned int uid = INSN_UID (insn);
+
+ for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
+ {
+ struct df_ref *use = *use_rec;
+ /* Add use to set of uses in this BB. */
+ bitmap_set_bit (live, DF_REF_REGNO (use));
+ }
+}
+
+
+/* Add back the always live regs in BB to LIVE. */
+
+static inline void
+df_simulate_fixup_sets (basic_block bb, bitmap live)
+{
+ /* These regs are considered always live so if they end up dying
+ because of some def, we need to bring the back again. */
+ if (df_has_eh_preds (bb))
+ bitmap_ior_into (live, df->eh_block_artificial_uses);
+ else
+ bitmap_ior_into (live, df->regular_block_artificial_uses);
+}
+
+
+/* Apply the artifical uses and defs at the top of BB in a forwards
+ direction. */
+
+void
+df_simulate_artificial_refs_at_top (basic_block bb, bitmap live)
+{
+ struct df_ref **def_rec;
+ struct df_ref **use_rec;
+ int bb_index = bb->index;
+
+ for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
+ {
+ struct df_ref *use = *use_rec;
+ if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
+ bitmap_set_bit (live, DF_REF_REGNO (use));
+ }
+
+ for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
+ {
+ struct df_ref *def = *def_rec;
+ if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
+ bitmap_clear_bit (live, DF_REF_REGNO (def));
+ }
+}
+
+
+/* Simulate the forwards effects of INSN on the bitmap LIVE. */
+
+void
+df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live)
+{
+ if (! INSN_P (insn))
+ return;
+
+ df_simulate_uses (insn, live);
+ df_simulate_defs (insn, live);
+ df_simulate_fixup_sets (bb, live);
+}
+
+
+/* Apply the artifical uses and defs at the end of BB in a backwards
+ direction. */
+
+void
+df_simulate_artificial_refs_at_end (basic_block bb, bitmap live)
+{
+ struct df_ref **def_rec;
+ struct df_ref **use_rec;
+ int bb_index = bb->index;
+
+ for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
+ {
+ struct df_ref *def = *def_rec;
+ if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
+ bitmap_clear_bit (live, DF_REF_REGNO (def));
+ }
+
+ for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
+ {
+ struct df_ref *use = *use_rec;
+ if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
+ bitmap_set_bit (live, DF_REF_REGNO (use));
+ }
+}
+
+
+/* Simulate the backwards effects of INSN on the bitmap LIVE. */
+
+void
+df_simulate_one_insn_backwards (basic_block bb, rtx insn, bitmap live)
+{
+ if (! INSN_P (insn))
+ return;
+
+ df_simulate_defs (insn, live);
+ df_simulate_uses (insn, live);
+ df_simulate_fixup_sets (bb, live);
+}
+
+