Re: [PATCH] Improve PR91257, specialize bitmap_ior_and_compl_into
On Tue, 30 Jul 2019, Jakub Jelinek wrote: > On Tue, Jul 30, 2019 at 12:20:00PM +0200, Richard Biener wrote: > > + if (compl_p) > > + for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) > > + { > > + and_elt.bits[ix] = b_elt->bits[ix] & ~c_elt->bits[ix]; > > + overall |= and_elt.bits[ix]; > > + } > > + else > > + for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) > > + { > > + and_elt.bits[ix] = b_elt->bits[ix] & c_elt->bits[ix]; > > + overall |= and_elt.bits[ix]; > > + } > > Might be more readable by moving the if (compl_p) into the loop, > just guarding the single statement that is different or even use a > BITMAP_WORD temporary to load c_elt->bits[ix] into it, then conditionally > complement and then use unconditionally in &. As said in the followup the patch didn't acutally work. So here's the open-coded variant. Bootstrapped and tested on x86_64-unknown-linux-gnu, will commit shortly. Richard. 2019-07-30 Richard Biener PR tree-optimization/91257 * bitmap.c (bitmap_ior_and_compl_into): Open-code. Index: gcc/bitmap.c === --- gcc/bitmap.c(revision 273906) +++ gcc/bitmap.c(working copy) @@ -2367,16 +2367,75 @@ bitmap_ior_and_compl (bitmap dst, const_ bool bitmap_ior_and_compl_into (bitmap a, const_bitmap b, const_bitmap c) { - bitmap_head tmp; - bool changed; + 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; gcc_checking_assert (!a->tree_form && !b->tree_form && !c->tree_form); - bitmap_initialize (&tmp, &bitmap_default_obstack); - bitmap_and_compl (&tmp, b, c); - changed = bitmap_ior_into (a, &tmp); - bitmap_clear (&tmp); + if (a == b) +return false; + if (bitmap_empty_p (c)) +return bitmap_ior_into (a, b); + else if (bitmap_empty_p (a)) +return bitmap_and_compl (a, b, c); + and_elt.indx = -1; + while (b_elt) +{ + /* Advance C. */ + while (c_elt && c_elt->indx < b_elt->indx) + c_elt = c_elt->next; + + const bitmap_element *and_elt_ptr; + if (c_elt && c_elt->indx == b_elt->indx) + { + BITMAP_WORD overall = 0; + and_elt_ptr = &and_elt; + and_elt.indx = b_elt->indx; + for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) + { + and_elt.bits[ix] = b_elt->bits[ix] & ~c_elt->bits[ix]; + overall |= and_elt.bits[ix]; + } + if (!overall) + { + b_elt = b_elt->next; + continue; + } + } + else + and_elt_ptr = b_elt; + + b_elt = b_elt->next; + + /* Now find a place to insert AND_ELT. */ + do + { + ix = a_elt ? a_elt->indx : and_elt_ptr->indx; + if (ix == and_elt_ptr->indx) + changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, + and_elt_ptr, changed); + else if (ix > and_elt_ptr->indx) + changed = bitmap_elt_copy (a, NULL, a_prev, and_elt_ptr, 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_ptr->indx); +} + + gcc_checking_assert (!a->current == !a->first); + if (a->current) +a->indx = a->current->indx; return changed; }
Re: [PATCH] Improve PR91257, specialize bitmap_ior_and_compl_into
On Tue, Jul 30, 2019 at 12:20:00PM +0200, Richard Biener wrote: > + if (compl_p) > + for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) > + { > + and_elt.bits[ix] = b_elt->bits[ix] & ~c_elt->bits[ix]; > + overall |= and_elt.bits[ix]; > + } > + else > + for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) > + { > + and_elt.bits[ix] = b_elt->bits[ix] & c_elt->bits[ix]; > + overall |= and_elt.bits[ix]; > + } Might be more readable by moving the if (compl_p) into the loop, just guarding the single statement that is different or even use a BITMAP_WORD temporary to load c_elt->bits[ix] into it, then conditionally complement and then use unconditionally in &. Jakub
Re: [PATCH] Improve PR91257, specialize bitmap_ior_and_compl_into
On Tue, 30 Jul 2019, Richard Biener wrote: > > bitmap_ior_and_compl_into is currently doing bitmap_and_compl into > a temporary bitmap and then bitmap_ior_into. The following uses > the existing implementation of bitmap_ior_and_into and exchanges > the core worker based on a template parameter. > > This results in a slight savings in out-of-SSA time (it also avoids > using the default obstack for the temporary while all operands for > out-of-SSA and the result live in different obstacks). > > Bootstrap and regtest running on x86_64-unknown-linux-gnu. Hmm, I realize I cannot reuse the implementations this way since for non-existing C element I have to assume 1s... Richard. > Richard. > > 2019-07-30 Richard Biener > > PR tree-optimization/91257 > * bitmap.c (bitmap_ior_and_maybe_compl): New templated function > based on bitmap_ior_and_into. > (bitmap_ior_and_into): Wrap around bitmap_ior_and_maybe_compl. > (bitmap_ior_and_compl_into): Likewise. > > Index: gcc/bitmap.c > === > --- gcc/bitmap.c (revision 273795) > +++ gcc/bitmap.c (working copy) > @@ -2345,28 +2399,11 @@ bitmap_ior_and_compl (bitmap dst, const_ >return changed; > } > > -/* A |= (B & ~C). Return true if A changes. */ > +/* Helper for A |= (B & ~C) and A |= (B & C). Return true if A changes. */ > > -bool > -bitmap_ior_and_compl_into (bitmap a, const_bitmap b, const_bitmap c) > -{ > - bitmap_head tmp; > - bool changed; > - > - gcc_checking_assert (!a->tree_form && !b->tree_form && !c->tree_form); > - > - bitmap_initialize (&tmp, &bitmap_default_obstack); > - bitmap_and_compl (&tmp, b, c); > - changed = bitmap_ior_into (a, &tmp); > - bitmap_clear (&tmp); > - > - return changed; > -} > - > -/* A |= (B & C). Return true if A changes. */ > - > -bool > -bitmap_ior_and_into (bitmap a, const_bitmap b, const_bitmap c) > +template > +static bool > +bitmap_ior_and_maybe_compl_into (bitmap a, const_bitmap b, const_bitmap c) > { >bitmap_element *a_elt = a->first; >const bitmap_element *b_elt = b->first; > @@ -2408,11 +2445,18 @@ bitmap_ior_and_into (bitmap a, const_bit > >overall = 0; >and_elt.indx = b_elt->indx; > - for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) > - { > - and_elt.bits[ix] = b_elt->bits[ix] & c_elt->bits[ix]; > - overall |= and_elt.bits[ix]; > - } > + if (compl_p) > + for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) > + { > + and_elt.bits[ix] = b_elt->bits[ix] & ~c_elt->bits[ix]; > + overall |= and_elt.bits[ix]; > + } > + else > + for (ix = 0; 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; > @@ -2444,6 +2488,22 @@ bitmap_ior_and_into (bitmap a, const_bit >return changed; > } > > +/* A |= (B & ~C). Return true if A changes. */ > + > +bool > +bitmap_ior_and_compl_into (bitmap a, const_bitmap b, const_bitmap c) > +{ > + return bitmap_ior_and_maybe_compl_into (a, b, c); > +} > + > +/* A |= (B & C). Return true if A changes. */ > + > +bool > +bitmap_ior_and_into (bitmap a, const_bitmap b, const_bitmap c) > +{ > + return bitmap_ior_and_maybe_compl_into (a, b, c); > +} > + > /* Compute hash of bitmap (for purposes of hashing). */ > > hashval_t > -- Richard Biener SUSE Linux GmbH, Maxfeldstrasse 5, 90409 Nuernberg, Germany; GF: Felix Imendörffer, Mary Higgins, Sri Rasiah; HRB 21284 (AG Nürnberg)