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 3/4] Add a new bitmap function


On Mon, Jun 8, 2009 at 1:21 PM, Paolo Bonzini<bonzini@gnu.org> wrote:
> 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?

Ok (there are unrelated changes in the posted patch).

Thanks,
Richard.

> 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;
>
>


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