This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH 3/4] Add a new bitmap function
- From: Paolo Bonzini <bonzini at gnu dot org>
- To: gcc-patches at gcc dot gnu dot org
- Date: Mon, 8 Jun 2009 13:21:01 -0400
- Subject: [PATCH 3/4] Add a new bitmap function
This patch just adds a new function to compute A |= (B & C) on bitmaps.
This is easy to do (it is just a variation on bitmap_ior_into). This does
not appear to be used anywhere in the current GCC code, I'll add a use
in the next patch.
Bootstrapped/regtested with the other patches x86_64-pc-linux-gnu, ok?
2009-06-07 Paolo Bonzini <bonzini@gnu.org>
* bitmap.h (bitmap_ior_and_into): New.
* bitmap.c (bitmap_ior_and_into): New.
Index: gcc/bitmap.h
===================================================================
--- gcc/bitmap.h (branch rebase-fwprop-md)
+++ gcc/bitmap.h (working copy)
@@ -129,6 +129,8 @@ extern bool bitmap_ior_into (bitmap, con
extern void bitmap_xor (bitmap, const_bitmap, const_bitmap);
extern void bitmap_xor_into (bitmap, const_bitmap);
+/* DST = A | (B & C). Return true if DST changes. */
+extern bool bitmap_ior_and_into (bitmap DST, const_bitmap B, const_bitmap C);
/* DST = A | (B & ~C). Return true if DST changes. */
extern bool bitmap_ior_and_compl (bitmap DST, const_bitmap A, const_bitmap B, const_bitmap C);
/* A |= (B & ~C). Return true if A changes. */
Index: gcc/bitmap.c
===================================================================
--- gcc/bitmap.c (branch rebase-fwprop-md)
+++ gcc/bitmap.c (working copy)
@@ -1942,6 +1942,84 @@ bitmap_ior_and_compl_into (bitmap a, con
return changed;
}
+/* A |= (B & C). Return true if A changes. */
+
+bool
+bitmap_ior_and_into (bitmap a, const_bitmap b, const_bitmap c)
+{
+ bitmap_element *a_elt = a->first;
+ const bitmap_element *b_elt = b->first;
+ const bitmap_element *c_elt = c->first;
+ bitmap_element and_elt;
+ bitmap_element *a_prev = NULL;
+ bitmap_element **a_prev_pnext = &a->first;
+ bool changed = false;
+ unsigned ix;
+
+ if (b == c)
+ return bitmap_ior_into (a, b);
+ if (bitmap_empty_p (b) || bitmap_empty_p (c))
+ return false;
+
+ and_elt.indx = -1;
+ while (b_elt && c_elt)
+ {
+ BITMAP_WORD overall;
+
+ /* Find a common item of B and C. */
+ while (b_elt->indx != c_elt->indx)
+ {
+ if (b_elt->indx < c_elt->indx)
+ {
+ b_elt = b_elt->next;
+ if (!b_elt)
+ goto done;
+ }
+ else
+ {
+ c_elt = c_elt->next;
+ if (!c_elt)
+ goto done;
+ }
+ }
+
+ overall = 0;
+ and_elt.indx = b_elt->indx;
+ for (ix = BITMAP_ELEMENT_WORDS; ix--;)
+ {
+ and_elt.bits[ix] = b_elt->bits[ix] & c_elt->bits[ix];
+ overall |= and_elt.bits[ix];
+ }
+
+ b_elt = b_elt->next;
+ c_elt = c_elt->next;
+ if (!overall)
+ continue;
+
+ /* Now find a place to insert AND_ELT. */
+ do
+ {
+ ix = a_elt ? a_elt->indx : and_elt.indx;
+ if (ix == and_elt.indx)
+ changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, &and_elt, changed);
+ else if (ix > and_elt.indx)
+ changed = bitmap_elt_copy (a, NULL, a_prev, &and_elt, changed);
+
+ a_prev = *a_prev_pnext;
+ a_prev_pnext = &a_prev->next;
+ a_elt = *a_prev_pnext;
+
+ /* If A lagged behind B/C, we advanced it so loop once more. */
+ }
+ while (ix < and_elt.indx);
+ }
+
+ done:
+ gcc_assert (!a->current == !a->first);
+ if (a->current)
+ a->indx = a->current->indx;
+ return changed;
+}
/* Debugging function to print out the contents of a bitmap. */
patch 4/4:
trim the MD results to live registers
This patch trims the MD results to live registers. This is important
because call-clobbered registers have an artificial definition after
every call. When a lot of call-clobbered registers are not used by
register allocation, this would cause very dense MD sets to occur.
I did not seek actual testcases, but even x86 may have up to 40
such registers in integer-only functions, when MMX/SSE/x87 registers
are all enabled.
I thought that maybe committing it separately would help with bisection,
just in case.
Bootstrapped/regtested with the other patches x86_64-pc-linux-gnu, ok?
Paolo
2009-06-07 Paolo Bonzini <bonzini@gnu.org>
* df-problems.c (df_set_seen, df_unset_seen): Delete.
(df_rd_local_compute, df_md_local_compute): Inline them.
(df_md_scratch): New.
(df_md_alloc, df_md_free): Allocate/free it.
(df_md_local_compute): Only include live registers in init.
(df_md_transfer_function): Prune the in-set computed by
the confluence function, and the gen-set too.
Index: gcc/df-problems.c
===================================================================
--- gcc/df-problems.c (branch rebase-fwprop-md)
+++ gcc/df-problems.c (working copy)
@@ -157,27 +157,6 @@ df_print_bb_index (basic_block bb, FILE
fprintf (file, ")\n");
}
-
-
-/* Make sure that the seen_in_insn and seen_in_block sbitmaps are set
- up correctly. */
-
-static void
-df_set_seen (void)
-{
- seen_in_block = BITMAP_ALLOC (&df_bitmap_obstack);
- seen_in_insn = BITMAP_ALLOC (&df_bitmap_obstack);
-}
-
-
-static void
-df_unset_seen (void)
-{
- BITMAP_FREE (seen_in_block);
- BITMAP_FREE (seen_in_insn);
-}
-
-
/*----------------------------------------------------------------------------
REACHING DEFINITIONS
@@ -487,7 +466,8 @@ df_rd_local_compute (bitmap all_blocks)
bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
- df_set_seen ();
+ seen_in_block = BITMAP_ALLOC (&df_bitmap_obstack);
+ seen_in_insn = BITMAP_ALLOC (&df_bitmap_obstack);
df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
@@ -506,7 +486,9 @@ df_rd_local_compute (bitmap all_blocks)
DF_DEFS_BEGIN (regno),
DF_DEFS_COUNT (regno));
}
- df_unset_seen ();
+
+ BITMAP_FREE (seen_in_block);
+ BITMAP_FREE (seen_in_insn);
}
@@ -3960,6 +3942,10 @@ df_simulate_finalize_forwards (basic_blo
block.
---------------------------------------------------------------------------*/
+/* Scratch var used by transfer functions. This is used to do md analysis
+ only for live registers. */
+static bitmap df_md_scratch;
+
/* Set basic block info. */
static void
@@ -4003,6 +3989,7 @@ df_md_alloc (bitmap all_blocks)
sizeof (struct df_md_bb_info), 50);
df_grow_bb_info (df_md);
+ df_md_scratch = BITMAP_ALLOC (NULL);
EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
@@ -4157,14 +4144,14 @@ df_md_local_compute (bitmap all_blocks)
basic_block bb;
bitmap *frontiers;
- df_set_seen ();
+ seen_in_insn = BITMAP_ALLOC (NULL);
EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
{
df_md_bb_local_compute (bb_index);
}
- df_unset_seen ();
+ BITMAP_FREE (seen_in_insn);
frontiers = XNEWVEC (bitmap, last_basic_block);
FOR_ALL_BB (bb)
@@ -4178,8 +4165,10 @@ df_md_local_compute (bitmap all_blocks)
bitmap kill = df_md_get_bb_info (bb_index)->kill;
EXECUTE_IF_SET_IN_BITMAP (frontiers[bb_index], 0, df_bb_index, bi2)
{
+ basic_block bb = BASIC_BLOCK (df_bb_index);
if (bitmap_bit_p (all_blocks, df_bb_index))
- bitmap_ior_into (df_md_get_bb_info (df_bb_index)->init, kill);
+ bitmap_ior_and_into (df_md_get_bb_info (df_bb_index)->init, kill,
+ df_get_live_in (bb));
}
}
}
@@ -4205,13 +4194,24 @@ df_md_reset (bitmap all_blocks)
static bool
df_md_transfer_function (int bb_index)
{
+ basic_block bb = BASIC_BLOCK (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);
+ /* We need to use a scratch set here so that the value returned from
+ this function invocation properly reflects if the sets changed in
+ a significant way; i.e. not just because the live set was anded
+ in. */
+ bitmap_and (df_md_scratch, gen, df_get_live_out (bb));
+
+ /* Multiple definitions of a register are not relevant if it is not
+ used. Thus we trim the result to the places where it is live. */
+ bitmap_and_into (in, df_get_live_in (bb));
+
+ return bitmap_ior_and_compl (out, df_md_scratch, in, kill);
}
/* Initialize the solution bit vectors for problem. */
@@ -4274,6 +4274,7 @@ df_md_free (void)
}
}
+ BITMAP_FREE (df_md_scratch);
free_alloc_pool (df_md->block_pool);
df_md->block_info_size = 0;