[PATCH] Improve PR91257, specialize bitmap_ior_and_compl_into

[PATCH] Improve PR91257, specialize bitmap_ior_and_compl_into

[Richard Biener]

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.

Richard.

2019-07-30  Richard Biener  <rguenther@suse.de>

	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 <bool compl_p>
+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<true> (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<false> (a, b, c);
+}
+
 /* Compute hash of bitmap (for purposes of hashing).  */
 
 hashval_t

Re: [PATCH] Improve PR91257, specialize bitmap_ior_and_compl_into

[Richard Biener]

[-- Attachment #1: Type: text/plain, Size: 3625 bytes --]

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  <rguenther@suse.de>
> 
> 	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 <bool compl_p>
> +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<true> (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<false> (a, b, c);
> +}
> +
>  /* Compute hash of bitmap (for purposes of hashing).  */
>  
>  hashval_t
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE Linux GmbH, Maxfeldstrasse 5, 90409 Nuernberg, Germany;
GF: Felix Imendörffer, Mary Higgins, Sri Rasiah; HRB 21284 (AG NÌrnberg)

Re: [PATCH] Improve PR91257, specialize bitmap_ior_and_compl_into

[Jakub Jelinek]

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

[Richard Biener]

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  <rguenther@suse.de>

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