[PATCH] Assert on invalid bitmap iterations

[PATCH] Assert on invalid bitmap iterations

[Richard Biener]

The following guards against (some) remove-current-bit cases.  It
would have ICEd for PR77855 instead of producing wrong code.

Bootstrap / regtest running on x86_64-unknown-linux-gnu.

Comments?

Thanks,
Richard.

2016-10-06  Richard Biener  <rguenther@suse.de>

	* bitmap.c (bitmap_elem_to_freelist): Set indx to -1.
	* bitmap.h (bmp_iter_set): When advancing to the next element
	check that we didn't remove the current one.
	(bmp_iter_and): Likewise.
	(bmp_iter_and_compl): Likewise.

Index: gcc/bitmap.c
===================================================================
--- gcc/bitmap.c	(revision 240828)
+++ gcc/bitmap.c	(working copy)
@@ -66,6 +66,7 @@ bitmap_elem_to_freelist (bitmap head, bi
   bitmap_obstack *bit_obstack = head->obstack;
 
   elt->next = NULL;
+  elt->indx = -1;
   if (bit_obstack)
     {
       elt->prev = bit_obstack->elements;
Index: gcc/bitmap.h
===================================================================
--- gcc/bitmap.h	(revision 240828)
+++ gcc/bitmap.h	(working copy)
@@ -618,6 +618,9 @@ bmp_iter_set (bitmap_iterator *bi, unsig
 	  bi->word_no++;
 	}
 
+      /* Make sure we didn't remove the element while iterating.  */
+      gcc_checking_assert (bi->elt1->indx != -1);
+
       /* Advance to the next element.  */
       bi->elt1 = bi->elt1->next;
       if (!bi->elt1)
@@ -664,6 +667,9 @@ bmp_iter_and (bitmap_iterator *bi, unsig
       /* Advance to the next identical element.  */
       do
 	{
+	  /* Make sure we didn't remove the element while iterating.  */
+	  gcc_checking_assert (bi->elt1->indx != -1);
+
 	  /* Advance elt1 while it is less than elt2.  We always want
 	     to advance one elt.  */
 	  do
@@ -674,6 +680,9 @@ bmp_iter_and (bitmap_iterator *bi, unsig
 	    }
 	  while (bi->elt1->indx < bi->elt2->indx);
 
+	  /* Make sure we didn't remove the element while iterating.  */
+	  gcc_checking_assert (bi->elt2->indx != -1);
+
 	  /* Advance elt2 to be no less than elt1.  This might not
 	     advance.  */
 	  while (bi->elt2->indx < bi->elt1->indx)
@@ -726,11 +735,17 @@ bmp_iter_and_compl (bitmap_iterator *bi,
 	  bi->word_no++;
 	}
 
+      /* Make sure we didn't remove the element while iterating.  */
+      gcc_checking_assert (bi->elt1->indx != -1);
+
       /* Advance to the next element of elt1.  */
       bi->elt1 = bi->elt1->next;
       if (!bi->elt1)
 	return false;
 
+      /* Make sure we didn't remove the element while iterating.  */
+      gcc_checking_assert (bi->elt2->indx != -1);
+
       /* Advance elt2 until it is no less than elt1.  */
       while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
 	bi->elt2 = bi->elt2->next;

Re: [PATCH] Assert on invalid bitmap iterations

[Richard Biener]

On Thu, 6 Oct 2016, Richard Biener wrote:

> 
> The following guards against (some) remove-current-bit cases.  It
> would have ICEd for PR77855 instead of producing wrong code.
> 
> Bootstrap / regtest running on x86_64-unknown-linux-gnu.
> 
> Comments?

Found one additional issue.

Bootstrapped on x86_64-unknown-linux-gnu, regtest still in progress.

The test is quite conservative (not all "current" bit removed are
detected but only "current and last bit removed" is), still I believe
it's useful to more easily pin-point when it happens that a bitmap
iteration is prematurely terminated due to this.

Richard.

2016-10-06  Richard Biener  <rguenther@suse.de>

	* bitmap.c (bitmap_elem_to_freelist): Set indx to -1.
	* bitmap.h (bmp_iter_set): When advancing to the next element
	check that we didn't remove the current one.
	(bmp_iter_and): Likewise.
	(bmp_iter_and_compl): Likewise.
	* tree-ssa.c (release_defs_bitset): Do not remove worklist bit
	we currently iterate on but keep a one-level queue.

Index: gcc/bitmap.c
===================================================================
*** gcc/bitmap.c	(revision 240829)
--- gcc/bitmap.c	(working copy)
*************** bitmap_elem_to_freelist (bitmap head, bi
*** 66,71 ****
--- 66,72 ----
    bitmap_obstack *bit_obstack = head->obstack;
  
    elt->next = NULL;
+   elt->indx = -1;
    if (bit_obstack)
      {
        elt->prev = bit_obstack->elements;
Index: gcc/bitmap.h
===================================================================
*** gcc/bitmap.h	(revision 240829)
--- gcc/bitmap.h	(working copy)
*************** bmp_iter_set (bitmap_iterator *bi, unsig
*** 618,623 ****
--- 618,626 ----
  	  bi->word_no++;
  	}
  
+       /* Make sure we didn't remove the element while iterating.  */
+       gcc_checking_assert (bi->elt1->indx != -1U);
+ 
        /* Advance to the next element.  */
        bi->elt1 = bi->elt1->next;
        if (!bi->elt1)
*************** bmp_iter_and (bitmap_iterator *bi, unsig
*** 664,669 ****
--- 667,675 ----
        /* Advance to the next identical element.  */
        do
  	{
+ 	  /* Make sure we didn't remove the element while iterating.  */
+ 	  gcc_checking_assert (bi->elt1->indx != -1U);
+ 
  	  /* Advance elt1 while it is less than elt2.  We always want
  	     to advance one elt.  */
  	  do
*************** bmp_iter_and (bitmap_iterator *bi, unsig
*** 674,679 ****
--- 680,688 ----
  	    }
  	  while (bi->elt1->indx < bi->elt2->indx);
  
+ 	  /* Make sure we didn't remove the element while iterating.  */
+ 	  gcc_checking_assert (bi->elt2->indx != -1U);
+ 
  	  /* Advance elt2 to be no less than elt1.  This might not
  	     advance.  */
  	  while (bi->elt2->indx < bi->elt1->indx)
*************** bmp_iter_and_compl (bitmap_iterator *bi,
*** 726,736 ****
--- 735,751 ----
  	  bi->word_no++;
  	}
  
+       /* Make sure we didn't remove the element while iterating.  */
+       gcc_checking_assert (bi->elt1->indx != -1U);
+ 
        /* Advance to the next element of elt1.  */
        bi->elt1 = bi->elt1->next;
        if (!bi->elt1)
  	return false;
  
+       /* Make sure we didn't remove the element while iterating.  */
+       gcc_checking_assert (! bi->elt2 || bi->elt2->indx != -1U);
+ 
        /* Advance elt2 until it is no less than elt1.  */
        while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
  	bi->elt2 = bi->elt2->next;
Index: gcc/tree-ssa.c
===================================================================
*** gcc/tree-ssa.c	(revision 240829)
--- gcc/tree-ssa.c	(working copy)
*************** release_defs_bitset (bitmap toremove)
*** 551,608 ****
       most likely run in slightly superlinear time, rather than the
       pathological quadratic worst case.  */
    while (!bitmap_empty_p (toremove))
!     EXECUTE_IF_SET_IN_BITMAP (toremove, 0, j, bi)
!       {
! 	bool remove_now = true;
! 	tree var = ssa_name (j);
! 	gimple *stmt;
! 	imm_use_iterator uit;
! 
! 	FOR_EACH_IMM_USE_STMT (stmt, uit, var)
! 	  {
! 	    ssa_op_iter dit;
! 	    def_operand_p def_p;
! 
! 	    /* We can't propagate PHI nodes into debug stmts.  */
! 	    if (gimple_code (stmt) == GIMPLE_PHI
! 		|| is_gimple_debug (stmt))
! 	      continue;
! 
! 	    /* If we find another definition to remove that uses
! 	       the one we're looking at, defer the removal of this
! 	       one, so that it can be propagated into debug stmts
! 	       after the other is.  */
! 	    FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, dit, SSA_OP_DEF)
! 	      {
! 		tree odef = DEF_FROM_PTR (def_p);
! 
! 		if (bitmap_bit_p (toremove, SSA_NAME_VERSION (odef)))
! 		  {
! 		    remove_now = false;
! 		    break;
! 		  }
! 	      }
! 
! 	    if (!remove_now)
! 	      BREAK_FROM_IMM_USE_STMT (uit);
! 	  }
! 
! 	if (remove_now)
! 	  {
! 	    gimple *def = SSA_NAME_DEF_STMT (var);
! 	    gimple_stmt_iterator gsi = gsi_for_stmt (def);
! 
! 	    if (gimple_code (def) == GIMPLE_PHI)
! 	      remove_phi_node (&gsi, true);
! 	    else
! 	      {
! 		gsi_remove (&gsi, true);
! 		release_defs (def);
! 	      }
! 
! 	    bitmap_clear_bit (toremove, j);
! 	  }
!       }
  }
  
  /* Verify virtual SSA form.  */
--- 551,620 ----
       most likely run in slightly superlinear time, rather than the
       pathological quadratic worst case.  */
    while (!bitmap_empty_p (toremove))
!     {
!       unsigned to_remove_bit = -1U;
!       EXECUTE_IF_SET_IN_BITMAP (toremove, 0, j, bi)
! 	{
! 	  if (to_remove_bit != -1U)
! 	    {
! 	      bitmap_clear_bit (toremove, to_remove_bit);
! 	      to_remove_bit = -1U;
! 	    }
! 
! 	  bool remove_now = true;
! 	  tree var = ssa_name (j);
! 	  gimple *stmt;
! 	  imm_use_iterator uit;
! 
! 	  FOR_EACH_IMM_USE_STMT (stmt, uit, var)
! 	    {
! 	      ssa_op_iter dit;
! 	      def_operand_p def_p;
! 
! 	      /* We can't propagate PHI nodes into debug stmts.  */
! 	      if (gimple_code (stmt) == GIMPLE_PHI
! 		  || is_gimple_debug (stmt))
! 		continue;
! 
! 	      /* If we find another definition to remove that uses
! 		 the one we're looking at, defer the removal of this
! 		 one, so that it can be propagated into debug stmts
! 		 after the other is.  */
! 	      FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, dit, SSA_OP_DEF)
! 		{
! 		  tree odef = DEF_FROM_PTR (def_p);
! 
! 		  if (bitmap_bit_p (toremove, SSA_NAME_VERSION (odef)))
! 		    {
! 		      remove_now = false;
! 		      break;
! 		    }
! 		}
! 
! 	      if (!remove_now)
! 		BREAK_FROM_IMM_USE_STMT (uit);
! 	    }
! 
! 	  if (remove_now)
! 	    {
! 	      gimple *def = SSA_NAME_DEF_STMT (var);
! 	      gimple_stmt_iterator gsi = gsi_for_stmt (def);
! 
! 	      if (gimple_code (def) == GIMPLE_PHI)
! 		remove_phi_node (&gsi, true);
! 	      else
! 		{
! 		  gsi_remove (&gsi, true);
! 		  release_defs (def);
! 		}
! 
! 	      to_remove_bit = j;
! 	    }
! 	}
!       if (to_remove_bit != -1U)
! 	bitmap_clear_bit (toremove, to_remove_bit);
!     }
! 
  }
  
  /* Verify virtual SSA form.  */

Re: [PATCH] Assert on invalid bitmap iterations

[Jeff Law]

On 10/06/2016 03:15 AM, Richard Biener wrote:
>
> The following guards against (some) remove-current-bit cases.  It
> would have ICEd for PR77855 instead of producing wrong code.
>
> Bootstrap / regtest running on x86_64-unknown-linux-gnu.
>
> Comments?
>
> Thanks,
> Richard.
>
> 2016-10-06  Richard Biener  <rguenther@suse.de>
>
> 	* bitmap.c (bitmap_elem_to_freelist): Set indx to -1.
> 	* bitmap.h (bmp_iter_set): When advancing to the next element
> 	check that we didn't remove the current one.
> 	(bmp_iter_and): Likewise.
> 	(bmp_iter_and_compl): Likewise.
Seems like a good idea to me -- I've been bitten by this during patch 
development in the past and it looks like you're hitting one of the more 
unpleasant cases.

Someone had posted a more robust approach to detecting unsafe 
modification of a bitmap during iteration many years ago, but nobody had 
the time/inclination to take it to proof-of-concept to see how it'd 
perform in the real world.


Jeff

Re: [PATCH] Assert on invalid bitmap iterations

[Richard Biener]

On Thu, 6 Oct 2016, Jeff Law wrote:

> On 10/06/2016 03:15 AM, Richard Biener wrote:
> > 
> > The following guards against (some) remove-current-bit cases.  It
> > would have ICEd for PR77855 instead of producing wrong code.
> > 
> > Bootstrap / regtest running on x86_64-unknown-linux-gnu.
> > 
> > Comments?
> > 
> > Thanks,
> > Richard.
> > 
> > 2016-10-06  Richard Biener  <rguenther@suse.de>
> > 
> > 	* bitmap.c (bitmap_elem_to_freelist): Set indx to -1.
> > 	* bitmap.h (bmp_iter_set): When advancing to the next element
> > 	check that we didn't remove the current one.
> > 	(bmp_iter_and): Likewise.
> > 	(bmp_iter_and_compl): Likewise.
> Seems like a good idea to me -- I've been bitten by this during patch
> development in the past and it looks like you're hitting one of the more
> unpleasant cases.

Yeah - it detects the case where after clearing a bit you'd end up
not iterating over bits you did not clear (I think it doesn't cover
all cases, like if you remove a bit range spanning multiple bitmap
elements).  It does not cover the case where after clearing a bit
you'd not yet iterated on but which is in the same bitmap word
the iterator currently processes you will still iterate over that
cleared bit (in most cases that should be harmless).

> Someone had posted a more robust approach to detecting unsafe modification of
> a bitmap during iteration many years ago, but nobody had the time/inclination
> to take it to proof-of-concept to see how it'd perform in the real world.

My approach was supposed to be very light-weight, only
adding a check at the point we advance to a new bitmap element.

Testing revealed another case in sched-deps.c:remove_from_deps ...

  EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
    {
...
      if (!reg_last->uses && !reg_last->sets && !reg_last->implicit_sets
          && !reg_last->clobbers)
        CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, i);
    }

Will commit after re-testing.  I fully expect more cases to be uncovered
but I think that's good.

Thanks,
Richard.

2016-10-07  Richard Biener  <rguenther@suse.de>

	* bitmap.c (bitmap_elem_to_freelist): Set indx to -1.
	* bitmap.h (bmp_iter_set): When advancing to the next element
	check that we didn't remove the current one.
	(bmp_iter_and): Likewise.
	(bmp_iter_and_compl): Likewise.
	* tree-ssa.c (release_defs_bitset): Do not remove worklist bit
	we currently iterate on but keep a one-level queue.
	* sched-deps.c (remove_from_deps): Do not clear current bit
	but keep a one-level queue.

Index: gcc/bitmap.c
===================================================================
*** gcc/bitmap.c	(revision 240829)
--- gcc/bitmap.c	(working copy)
*************** bitmap_elem_to_freelist (bitmap head, bi
*** 66,71 ****
--- 66,72 ----
    bitmap_obstack *bit_obstack = head->obstack;
  
    elt->next = NULL;
+   elt->indx = -1;
    if (bit_obstack)
      {
        elt->prev = bit_obstack->elements;
Index: gcc/bitmap.h
===================================================================
*** gcc/bitmap.h	(revision 240829)
--- gcc/bitmap.h	(working copy)
*************** bmp_iter_set (bitmap_iterator *bi, unsig
*** 618,623 ****
--- 618,626 ----
  	  bi->word_no++;
  	}
  
+       /* Make sure we didn't remove the element while iterating.  */
+       gcc_checking_assert (bi->elt1->indx != -1U);
+ 
        /* Advance to the next element.  */
        bi->elt1 = bi->elt1->next;
        if (!bi->elt1)
*************** bmp_iter_and (bitmap_iterator *bi, unsig
*** 664,669 ****
--- 667,675 ----
        /* Advance to the next identical element.  */
        do
  	{
+ 	  /* Make sure we didn't remove the element while iterating.  */
+ 	  gcc_checking_assert (bi->elt1->indx != -1U);
+ 
  	  /* Advance elt1 while it is less than elt2.  We always want
  	     to advance one elt.  */
  	  do
*************** bmp_iter_and (bitmap_iterator *bi, unsig
*** 674,679 ****
--- 680,688 ----
  	    }
  	  while (bi->elt1->indx < bi->elt2->indx);
  
+ 	  /* Make sure we didn't remove the element while iterating.  */
+ 	  gcc_checking_assert (bi->elt2->indx != -1U);
+ 
  	  /* Advance elt2 to be no less than elt1.  This might not
  	     advance.  */
  	  while (bi->elt2->indx < bi->elt1->indx)
*************** bmp_iter_and_compl (bitmap_iterator *bi,
*** 726,736 ****
--- 735,751 ----
  	  bi->word_no++;
  	}
  
+       /* Make sure we didn't remove the element while iterating.  */
+       gcc_checking_assert (bi->elt1->indx != -1U);
+ 
        /* Advance to the next element of elt1.  */
        bi->elt1 = bi->elt1->next;
        if (!bi->elt1)
  	return false;
  
+       /* Make sure we didn't remove the element while iterating.  */
+       gcc_checking_assert (! bi->elt2 || bi->elt2->indx != -1U);
+ 
        /* Advance elt2 until it is no less than elt1.  */
        while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
  	bi->elt2 = bi->elt2->next;
Index: gcc/tree-ssa.c
===================================================================
*** gcc/tree-ssa.c	(revision 240829)
--- gcc/tree-ssa.c	(working copy)
*************** release_defs_bitset (bitmap toremove)
*** 551,608 ****
       most likely run in slightly superlinear time, rather than the
       pathological quadratic worst case.  */
    while (!bitmap_empty_p (toremove))
!     EXECUTE_IF_SET_IN_BITMAP (toremove, 0, j, bi)
!       {
! 	bool remove_now = true;
! 	tree var = ssa_name (j);
! 	gimple *stmt;
! 	imm_use_iterator uit;
! 
! 	FOR_EACH_IMM_USE_STMT (stmt, uit, var)
! 	  {
! 	    ssa_op_iter dit;
! 	    def_operand_p def_p;
! 
! 	    /* We can't propagate PHI nodes into debug stmts.  */
! 	    if (gimple_code (stmt) == GIMPLE_PHI
! 		|| is_gimple_debug (stmt))
! 	      continue;
! 
! 	    /* If we find another definition to remove that uses
! 	       the one we're looking at, defer the removal of this
! 	       one, so that it can be propagated into debug stmts
! 	       after the other is.  */
! 	    FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, dit, SSA_OP_DEF)
! 	      {
! 		tree odef = DEF_FROM_PTR (def_p);
! 
! 		if (bitmap_bit_p (toremove, SSA_NAME_VERSION (odef)))
! 		  {
! 		    remove_now = false;
! 		    break;
! 		  }
! 	      }
! 
! 	    if (!remove_now)
! 	      BREAK_FROM_IMM_USE_STMT (uit);
! 	  }
! 
! 	if (remove_now)
! 	  {
! 	    gimple *def = SSA_NAME_DEF_STMT (var);
! 	    gimple_stmt_iterator gsi = gsi_for_stmt (def);
! 
! 	    if (gimple_code (def) == GIMPLE_PHI)
! 	      remove_phi_node (&gsi, true);
! 	    else
! 	      {
! 		gsi_remove (&gsi, true);
! 		release_defs (def);
! 	      }
! 
! 	    bitmap_clear_bit (toremove, j);
! 	  }
!       }
  }
  
  /* Verify virtual SSA form.  */
--- 551,620 ----
       most likely run in slightly superlinear time, rather than the
       pathological quadratic worst case.  */
    while (!bitmap_empty_p (toremove))
!     {
!       unsigned to_remove_bit = -1U;
!       EXECUTE_IF_SET_IN_BITMAP (toremove, 0, j, bi)
! 	{
! 	  if (to_remove_bit != -1U)
! 	    {
! 	      bitmap_clear_bit (toremove, to_remove_bit);
! 	      to_remove_bit = -1U;
! 	    }
! 
! 	  bool remove_now = true;
! 	  tree var = ssa_name (j);
! 	  gimple *stmt;
! 	  imm_use_iterator uit;
! 
! 	  FOR_EACH_IMM_USE_STMT (stmt, uit, var)
! 	    {
! 	      ssa_op_iter dit;
! 	      def_operand_p def_p;
! 
! 	      /* We can't propagate PHI nodes into debug stmts.  */
! 	      if (gimple_code (stmt) == GIMPLE_PHI
! 		  || is_gimple_debug (stmt))
! 		continue;
! 
! 	      /* If we find another definition to remove that uses
! 		 the one we're looking at, defer the removal of this
! 		 one, so that it can be propagated into debug stmts
! 		 after the other is.  */
! 	      FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, dit, SSA_OP_DEF)
! 		{
! 		  tree odef = DEF_FROM_PTR (def_p);
! 
! 		  if (bitmap_bit_p (toremove, SSA_NAME_VERSION (odef)))
! 		    {
! 		      remove_now = false;
! 		      break;
! 		    }
! 		}
! 
! 	      if (!remove_now)
! 		BREAK_FROM_IMM_USE_STMT (uit);
! 	    }
! 
! 	  if (remove_now)
! 	    {
! 	      gimple *def = SSA_NAME_DEF_STMT (var);
! 	      gimple_stmt_iterator gsi = gsi_for_stmt (def);
! 
! 	      if (gimple_code (def) == GIMPLE_PHI)
! 		remove_phi_node (&gsi, true);
! 	      else
! 		{
! 		  gsi_remove (&gsi, true);
! 		  release_defs (def);
! 		}
! 
! 	      to_remove_bit = j;
! 	    }
! 	}
!       if (to_remove_bit != -1U)
! 	bitmap_clear_bit (toremove, to_remove_bit);
!     }
! 
  }
  
  /* Verify virtual SSA form.  */
Index: gcc/sched-deps.c
===================================================================
--- gcc/sched-deps.c	(revision 240829)
+++ gcc/sched-deps.c	(working copy)
@@ -3992,8 +3992,14 @@ remove_from_deps (struct deps_desc *deps
   removed = remove_from_dependence_list (insn, &deps->last_pending_memory_flush);
   deps->pending_flush_length -= removed;
 
+  unsigned to_clear = -1U;
   EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
     {
+      if (to_clear != -1U)
+	{
+	  CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, to_clear);
+	  to_clear = -1U;
+	}
       struct deps_reg *reg_last = &deps->reg_last[i];
       if (reg_last->uses)
 	remove_from_dependence_list (insn, &reg_last->uses);
@@ -4005,8 +4011,10 @@ remove_from_deps (struct deps_desc *deps
 	remove_from_dependence_list (insn, &reg_last->clobbers);
       if (!reg_last->uses && !reg_last->sets && !reg_last->implicit_sets
 	  && !reg_last->clobbers)
-        CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, i);
+	to_clear = i;
     }
+  if (to_clear != -1U)
+    CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, to_clear);
 
   if (CALL_P (insn))
     {

Re: [PATCH] Assert on invalid bitmap iterations

[Bernd Schmidt]

On 10/07/2016 09:20 AM, Richard Biener wrote:
> Index: gcc/sched-deps.c
> ===================================================================
> --- gcc/sched-deps.c	(revision 240829)
> +++ gcc/sched-deps.c	(working copy)
> @@ -3992,8 +3992,14 @@ remove_from_deps (struct deps_desc *deps
>    removed = remove_from_dependence_list (insn, &deps->last_pending_memory_flush);
>    deps->pending_flush_length -= removed;
>
> +  unsigned to_clear = -1U;
>    EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
>      {
> +      if (to_clear != -1U)
> +	{
> +	  CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, to_clear);
> +	  to_clear = -1U;
> +	}
>        struct deps_reg *reg_last = &deps->reg_last[i];
>        if (reg_last->uses)
>  	remove_from_dependence_list (insn, &reg_last->uses);
> @@ -4005,8 +4011,10 @@ remove_from_deps (struct deps_desc *deps
>  	remove_from_dependence_list (insn, &reg_last->clobbers);
>        if (!reg_last->uses && !reg_last->sets && !reg_last->implicit_sets
>  	  && !reg_last->clobbers)
> -        CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, i);
> +	to_clear = i;
>      }
> +  if (to_clear != -1U)
> +    CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, to_clear);

That looks pretty bad. What's the issue, we can't clear the current bit 
while iterating over a bitmap? Is that fixable - it seems like something 
people are likely to want to do?

Here, if necessary I'd prefer we create a to_clear bitmap and perform an 
and_compl operation after the loop.


Bernd

Re: [PATCH] Assert on invalid bitmap iterations

[Richard Biener]

On Fri, 7 Oct 2016, Bernd Schmidt wrote:

> On 10/07/2016 09:20 AM, Richard Biener wrote:
> > Index: gcc/sched-deps.c
> > ===================================================================
> > --- gcc/sched-deps.c	(revision 240829)
> > +++ gcc/sched-deps.c	(working copy)
> > @@ -3992,8 +3992,14 @@ remove_from_deps (struct deps_desc *deps
> >    removed = remove_from_dependence_list (insn,
> > &deps->last_pending_memory_flush);
> >    deps->pending_flush_length -= removed;
> > 
> > +  unsigned to_clear = -1U;
> >    EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
> >      {
> > +      if (to_clear != -1U)
> > +	{
> > +	  CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, to_clear);
> > +	  to_clear = -1U;
> > +	}
> >        struct deps_reg *reg_last = &deps->reg_last[i];
> >        if (reg_last->uses)
> >  	remove_from_dependence_list (insn, &reg_last->uses);
> > @@ -4005,8 +4011,10 @@ remove_from_deps (struct deps_desc *deps
> >  	remove_from_dependence_list (insn, &reg_last->clobbers);
> >        if (!reg_last->uses && !reg_last->sets && !reg_last->implicit_sets
> >  	  && !reg_last->clobbers)
> > -        CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, i);
> > +	to_clear = i;
> >      }
> > +  if (to_clear != -1U)
> > +    CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, to_clear);
> 
> That looks pretty bad. What's the issue, we can't clear the current bit while
> iterating over a bitmap? Is that fixable - it seems like something people are
> likely to want to do?

I think it would be possible if we'd had a bitmap_clear_bit variant
that uses the iterator because it needs to update the iterator which
keeps a pointer to the current bitmap_element plus a cached value
of the current bitmap_word.  Might be harder for the EXECUTE_IF_OP_
variants.

Currently if you remove the current (last bit) in a bitmap_element
it will get unlinked and put onto the freelist by bitmap_clear_bit
which then causes the iteration to immediately terminate (because
that bitmap element ->next pointer is now NULL).

> Here, if necessary I'd prefer we create a to_clear bitmap and perform an
> and_compl operation after the loop.

But that's way more expensive -- you allocate memory and perform an
additional loop over the bitmap.

I think the main issue is that it is not documented what is safe to do
(and what are the results) when you modify a bitmap while you are
iterating over it.

The bitmap iterator is optimized to optimize into a nice loop for
the bits in one bitmap word at least.

Richard.

Re: [PATCH] Assert on invalid bitmap iterations

[Richard Biener]

On Fri, 7 Oct 2016, Richard Biener wrote:

> I think the main issue is that it is not documented what is safe to do
> (and what are the results) when you modify a bitmap while you are
> iterating over it.

Does the following look ok?

Thanks,
Richard.

2016-10-07  Richard Biener  <rguenther@suse.de>

	* bitmap.h: Document constraints on bitmap modification while
	iterating over it.

Index: gcc/bitmap.h
===================================================================
--- gcc/bitmap.h	(revision 240859)
+++ gcc/bitmap.h	(working copy)
@@ -755,6 +755,18 @@ bmp_iter_and_compl (bitmap_iterator *bi,
     }
 }
 
+/* If you are modifying a bitmap you are currently iterating over you
+   have to ensure to
+     - never remove the current bit;
+     - if you set or clear a bit before the current bit this operation
+       will not affect the set of bits you are visiting during the iteration;
+     - if you set or clear a bit after the current bit it is unspecified
+       whether that affects the set of bits you are visiting during the
+       iteration.
+   If you want to remove the current bit you can delay this to the next
+   iteration (and after the iteration in case the last iteration is
+   affected).  */
+
 /* Loop over all bits set in BITMAP, starting with MIN and setting
    BITNUM to the bit number.  ITER is a bitmap iterator.  BITNUM
    should be treated as a read-only variable as it contains loop

Re: [PATCH] Assert on invalid bitmap iterations

[Bernd Schmidt]

On 10/07/2016 01:19 PM, Richard Biener wrote:
> On Fri, 7 Oct 2016, Richard Biener wrote:
>
>> I think the main issue is that it is not documented what is safe to do
>> (and what are the results) when you modify a bitmap while you are
>> iterating over it.
>
> Does the following look ok?

Sure.


Bernd

Re: [PATCH] Assert on invalid bitmap iterations

[Bernd Schmidt]

On 10/07/2016 01:07 PM, Richard Biener wrote:
> On Fri, 7 Oct 2016, Bernd Schmidt wrote:
>
>> Here, if necessary I'd prefer we create a to_clear bitmap and perform an
>> and_compl operation after the loop.
>
> But that's way more expensive -- you allocate memory and perform an
> additional loop over the bitmap.

Yeah. Can we have an additional safer variant of the bitmap iterators 
maybe? We could have an object that gets constructed in the for 
statement and serves as a lock/unlock, where we postpone deletion of 
elements while locked, and flush them on unlock (keeping a flag to say 
if that's necessary).


Bernd

Re: [PATCH] Assert on invalid bitmap iterations

[Richard Biener]

On Fri, 7 Oct 2016, Bernd Schmidt wrote:

> On 10/07/2016 01:07 PM, Richard Biener wrote:
> > On Fri, 7 Oct 2016, Bernd Schmidt wrote:
> > 
> > > Here, if necessary I'd prefer we create a to_clear bitmap and perform an
> > > and_compl operation after the loop.
> > 
> > But that's way more expensive -- you allocate memory and perform an
> > additional loop over the bitmap.
> 
> Yeah. Can we have an additional safer variant of the bitmap iterators maybe?
> We could have an object that gets constructed in the for statement and serves
> as a lock/unlock, where we postpone deletion of elements while locked, and
> flush them on unlock (keeping a flag to say if that's necessary).

I think what might work is implementing that single-depth-queue inside
the iterator, thus have a

  bitmap_clear_bit_at_iterator (bitmap_iterator *, int which = 0);

(which == 1 for when you use EXECUTE_IF_AND_IN_BITMAP and want to
clear a bit in the second bitmap).  The clearing would need to be
done in bmp_iter_set_* in a safe way and the above function would
simply set a flag in the bitmap_iterator.

I think it will be a non-trivial task still.

Any such interface needs to be carried over to other bitmap users
(like the regset case).

Richard.