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 <rguent...@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 <rguent...@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, ®_last->uses);
@@ -4005,8 +4011,10 @@ remove_from_deps (struct deps_desc *deps
remove_from_dependence_list (insn, ®_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))
{
