Patchwork Another fix for PR54838

login
register
mail settings
Submitter Marek Polacek
Date Dec. 17, 2012, 12:21 a.m.
Message ID <20121217002156.GE2432@redhat.com>
Download mbox | patch
Permalink /patch/206756/
State New
Headers show

Comments

Marek Polacek - Dec. 17, 2012, 12:21 a.m.
Here's a fix for the C++ TC part of this PR.  The issue was
that we had a loop with header and two latches, and via delete_basic_block
we deleted both latches, but we weren't removing the loop properly.
This ICEd later on because in merge_latch_edges  there's an assert:
gcc_assert (latches.length () > 0);

[Unfortunately this still not fixes profiledbootstrap with ada
mentioned in the PR (it seems to be a different issue, namely something
in cleanup_cfg in .into_cfglayout: we have a loop consisting of one
BB--its outcoming edge is at the same time its incoming edge--and we
remove this edge, but this "loop" is not removed).  The interim
workaround is to filter-out -fprofile-generate switch on targparm.o
in gcc/ada/gcc-interface/Make-lang.in.  I hope I will fix this one
during this week.]

Fixed thusly, bootstrapped/regtested on x86_64-linux, ok for trunk?

2012-12-15  Marek Polacek  <polacek@redhat.com>

	PR middle-end/54838
	* cfghooks.c (delete_basic_block): Remove loop if all the
	latches are gone.
	* cfgcleanup.c (delete_unreachable_blocks): Call
	mark_dfs_back_edges.

	* g++.dg/pr54838.C: New test.


	Marek
Richard Guenther - Dec. 17, 2012, 9:27 a.m.
On Mon, Dec 17, 2012 at 1:21 AM, Marek Polacek <polacek@redhat.com> wrote:
> Here's a fix for the C++ TC part of this PR.  The issue was
> that we had a loop with header and two latches, and via delete_basic_block
> we deleted both latches, but we weren't removing the loop properly.
> This ICEd later on because in merge_latch_edges  there's an assert:
> gcc_assert (latches.length () > 0);
>
> [Unfortunately this still not fixes profiledbootstrap with ada
> mentioned in the PR (it seems to be a different issue, namely something
> in cleanup_cfg in .into_cfglayout: we have a loop consisting of one
> BB--its outcoming edge is at the same time its incoming edge--and we
> remove this edge, but this "loop" is not removed).  The interim
> workaround is to filter-out -fprofile-generate switch on targparm.o
> in gcc/ada/gcc-interface/Make-lang.in.  I hope I will fix this one
> during this week.]
>
> Fixed thusly, bootstrapped/regtested on x86_64-linux, ok for trunk?

This looks like the wrong place to fix (the delete-basic-block cfghook
tryings to fixup loops are incredibly fragile, because usually
delete_basic_block
is called because of another cfg manipulation takes place).  That is,
the right cfghook place would be where the latch edge is deleted (of course
you cannot know whether it'll be just redirected - thus the fragility of cfghook
fixes for loops).

Which pass does this deletion?  The correct fix is to fix that pass to
correctly care about the high-level CFG transform it performs.

Thanks,
Richard.

> 2012-12-15  Marek Polacek  <polacek@redhat.com>
>
>         PR middle-end/54838
>         * cfghooks.c (delete_basic_block): Remove loop if all the
>         latches are gone.
>         * cfgcleanup.c (delete_unreachable_blocks): Call
>         mark_dfs_back_edges.
>
>         * g++.dg/pr54838.C: New test.
>
> --- gcc/cfghooks.c.mp   2012-12-15 04:03:18.388050403 +0100
> +++ gcc/cfghooks.c      2012-12-15 04:03:35.313102810 +0100
> @@ -541,11 +541,31 @@ delete_basic_block (basic_block bb)
>    if (current_loops != NULL)
>      {
>        struct loop *loop = bb->loop_father;
> +      bool is_last_latch = false;
> +
> +      /* We can get into situation where we have multiple latches.  We
> +        have to cancel the loop, if we remove all the latches--then
> +        the header won't have any incoming back edges.  */
> +      if (loop->header
> +         && bb->loop_father != current_loops->tree_root)
> +       {
> +         edge e;
> +         edge_iterator ei;
> +         unsigned int n_back_edges = 0;
> +         /* Check whether there's only one latch edge...  */
> +         FOR_EACH_EDGE (e, ei, loop->header->preds)
> +           if (e->flags & EDGE_DFS_BACK)
> +             n_back_edges++;
> +         /* ... and whether we're deleting its latch.  */
> +         is_last_latch = n_back_edges == 1
> +                         && find_edge (bb, loop->header);
> +       }
>
>        /* If we remove the header or the latch of a loop, mark the loop for
>          removal by setting its header and latch to NULL.  */
>        if (loop->latch == bb
> -         || loop->header == bb)
> +         || loop->header == bb
> +         || is_last_latch)
>         {
>           loop->header = NULL;
>           loop->latch = NULL;
> --- gcc/testsuite/g++.dg/pr54838.C.mp   2012-12-15 03:52:52.436371725 +0100
> +++ gcc/testsuite/g++.dg/pr54838.C      2012-12-15 03:52:36.962330626 +0100
> @@ -0,0 +1,117 @@
> +// PR middle-end/54838
> +// { dg-do compile }
> +// { dg-options "-O2 -ftracer -fno-tree-dce -fno-tree-sra" }
> +
> +  struct bidirectional_iterator_tag
> +  {};
> +  struct random_access_iterator_tag:bidirectional_iterator_tag
> +  {};
> +  template < typename _Category, typename, typename _Distance, typename > struct iterator
> +  {
> +    typedef _Distance difference_type;
> +  };
> +  template < typename _Iterator > struct iterator_traits
> +  {
> +    typedef typename _Iterator::difference_type difference_type;
> +  };
> +  template < typename _Tp > struct iterator_traits <_Tp * >
> +  {
> +    typedef random_access_iterator_tag iterator_category;
> +    typedef _Tp value_type;
> +    typedef int difference_type;
> +    typedef _Tp reference;
> +  };
> +template < typename _Iterator > class reverse_iterator:
> +  public
> +    iterator
> +    <
> +    typename
> +    iterator_traits
> +    <
> +    _Iterator
> +    >::iterator_category,
> +    typename
> +    iterator_traits
> +    <
> +    _Iterator
> +    >::value_type,
> +    typename
> +    iterator_traits
> +    <
> +    _Iterator
> +    >::difference_type, typename iterator_traits < _Iterator >::reference >
> +  {
> +    _Iterator current;
> +  public:
> +    typedef _Iterator iterator_type;
> +    reverse_iterator (const reverse_iterator & __x):current (__x.current)
> +    {}
> +    iterator_type base ()
> +    {
> +      return current;
> +    }
> +    reverse_iterator operator++ ()
> +    {
> +      --current;
> +    }
> +  };
> +  template
> +    <
> +    typename
> +    _Iterator
> +    >
> +    bool
> +    operator
> +    ==
> +    (reverse_iterator < _Iterator > __x, reverse_iterator < _Iterator > __y)
> +  {
> +    return __x.base () == __y.base ();
> +  }
> +
> +  template
> +    <
> +    typename
> +    _Iterator
> +    >
> +    typename
> +    reverse_iterator
> +    <
> +    _Iterator
> +    >::difference_type
> +    operator
> +    - (reverse_iterator < _Iterator >, reverse_iterator < _Iterator >)
> +  {}
> +  template
> +    <
> +    typename
> +    _RandomAccessIterator
> +    >
> +    _RandomAccessIterator
> +    __find
> +    (_RandomAccessIterator
> +     __first, _RandomAccessIterator __last)
> +  {
> +    typename
> +      iterator_traits
> +      <
> +      _RandomAccessIterator
> +      >::difference_type __trip_count (__last - __first);
> +    for (; __trip_count; --__trip_count)
> +++__first;
> +       return __last;
> +  }
> +    typedef reverse_iterator < int* > _ForwardIterator1;
> +    _ForwardIterator1
> +    search
> +    (_ForwardIterator1
> +     __first1,
> +     _ForwardIterator1
> +     __last1)
> +  {
> +    for (;;)
> +      {
> +       __first1 = __find (__first1, __last1);
> +       if (__first1 == __last1)
> +         return __last1;
> +      }
> +  }
> --- gcc/cfgcleanup.c.mp 2012-12-15 04:03:24.144068226 +0100
> +++ gcc/cfgcleanup.c    2012-12-15 04:03:35.313102810 +0100
> @@ -2836,6 +2836,7 @@ delete_unreachable_blocks (void)
>    bool changed = false;
>    basic_block b, prev_bb;
>
> +  mark_dfs_back_edges ();
>    find_unreachable_blocks ();
>
>    /* When we're in GIMPLE mode and there may be debug insns, we should
>
>         Marek
Marek Polacek - Dec. 17, 2012, 10:16 a.m.
On Mon, Dec 17, 2012 at 10:27:54AM +0100, Richard Biener wrote:
> This looks like the wrong place to fix (the delete-basic-block cfghook
> tryings to fixup loops are incredibly fragile, because usually
> delete_basic_block
> is called because of another cfg manipulation takes place).  That is,
> the right cfghook place would be where the latch edge is deleted (of course
> you cannot know whether it'll be just redirected - thus the fragility of cfghook
> fixes for loops).
> 
> Which pass does this deletion?  The correct fix is to fix that pass to
> correctly care about the high-level CFG transform it performs.

It's cse1.  I didn't see any place in there where I could fix things up,
since it looks we aren't directly manipulating the CFG there (it
rather find paths, stores them in ebb data, then walks the insns in BBs,
and calls cse_insn on each of them, but it's so big 
and complex that I'm very likely wrong here), only
via cleanup_cfg at the end of the pass, which is what calls
delete_unreachable_blocks->delete_basic_block, here we delete two
latch nodes.  It seems legal to delete them, because at the end of BBs
before these latches is an unconditional jump at (label_ref 67).
I don't know how could we teach the CSE beast to care about high-level
CFG transformations.  Thanks,

	Marek
Richard Guenther - Dec. 17, 2012, 10:26 a.m.
On Mon, Dec 17, 2012 at 11:16 AM, Marek Polacek <polacek@redhat.com> wrote:
> On Mon, Dec 17, 2012 at 10:27:54AM +0100, Richard Biener wrote:
>> This looks like the wrong place to fix (the delete-basic-block cfghook
>> tryings to fixup loops are incredibly fragile, because usually
>> delete_basic_block
>> is called because of another cfg manipulation takes place).  That is,
>> the right cfghook place would be where the latch edge is deleted (of course
>> you cannot know whether it'll be just redirected - thus the fragility of cfghook
>> fixes for loops).
>>
>> Which pass does this deletion?  The correct fix is to fix that pass to
>> correctly care about the high-level CFG transform it performs.
>
> It's cse1.  I didn't see any place in there where I could fix things up,
> since it looks we aren't directly manipulating the CFG there (it
> rather find paths, stores them in ebb data, then walks the insns in BBs,
> and calls cse_insn on each of them, but it's so big
> and complex that I'm very likely wrong here), only
> via cleanup_cfg at the end of the pass, which is what calls
> delete_unreachable_blocks->delete_basic_block, here we delete two
> latch nodes.  It seems legal to delete them, because at the end of BBs
> before these latches is an unconditional jump at (label_ref 67).
> I don't know how could we teach the CSE beast to care about high-level
> CFG transformations.  Thanks,

Hmm, I think I remember this case ... (and I fixed it up in
cfg_cleanup I think).

So I suppose cse turns a conditional jump into an unconditional one (but
maybe only cfg_cleanup realizes that)?

I think that whoever figures out the latch edge is never taken ought to fixup
loop structure.  Btw, what also could be done is trying to teach
fix_loop_structure
of this case (but only as a last resort I think).

Richard.

>         Marek
Richard Guenther - Dec. 17, 2012, 2:17 p.m.
On Mon, Dec 17, 2012 at 11:26 AM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Mon, Dec 17, 2012 at 11:16 AM, Marek Polacek <polacek@redhat.com> wrote:
>> On Mon, Dec 17, 2012 at 10:27:54AM +0100, Richard Biener wrote:
>>> This looks like the wrong place to fix (the delete-basic-block cfghook
>>> tryings to fixup loops are incredibly fragile, because usually
>>> delete_basic_block
>>> is called because of another cfg manipulation takes place).  That is,
>>> the right cfghook place would be where the latch edge is deleted (of course
>>> you cannot know whether it'll be just redirected - thus the fragility of cfghook
>>> fixes for loops).
>>>
>>> Which pass does this deletion?  The correct fix is to fix that pass to
>>> correctly care about the high-level CFG transform it performs.
>>
>> It's cse1.  I didn't see any place in there where I could fix things up,
>> since it looks we aren't directly manipulating the CFG there (it
>> rather find paths, stores them in ebb data, then walks the insns in BBs,
>> and calls cse_insn on each of them, but it's so big
>> and complex that I'm very likely wrong here), only
>> via cleanup_cfg at the end of the pass, which is what calls
>> delete_unreachable_blocks->delete_basic_block, here we delete two
>> latch nodes.  It seems legal to delete them, because at the end of BBs
>> before these latches is an unconditional jump at (label_ref 67).
>> I don't know how could we teach the CSE beast to care about high-level
>> CFG transformations.  Thanks,
>
> Hmm, I think I remember this case ... (and I fixed it up in
> cfg_cleanup I think).
>
> So I suppose cse turns a conditional jump into an unconditional one (but
> maybe only cfg_cleanup realizes that)?
>
> I think that whoever figures out the latch edge is never taken ought to fixup
> loop structure.  Btw, what also could be done is trying to teach
> fix_loop_structure
> of this case (but only as a last resort I think).

That said, ISTR playing with removing the loop if remove_edge would remove
the last latch from it.  Note that the only reliable thing with preserved loops
but not loop_optimizer_init called is the loop->header field and the only
basic-block with reliable ->loop_father is the header block itself.

Richard.

> Richard.
>
>>         Marek
Marek Polacek - Dec. 17, 2012, 2:24 p.m.
On Mon, Dec 17, 2012 at 11:26:23AM +0100, Richard Biener wrote:
> On Mon, Dec 17, 2012 at 11:16 AM, Marek Polacek <polacek@redhat.com> wrote:
> > On Mon, Dec 17, 2012 at 10:27:54AM +0100, Richard Biener wrote:
> >> This looks like the wrong place to fix (the delete-basic-block cfghook
> >> tryings to fixup loops are incredibly fragile, because usually
> >> delete_basic_block
> >> is called because of another cfg manipulation takes place).  That is,
> >> the right cfghook place would be where the latch edge is deleted (of course
> >> you cannot know whether it'll be just redirected - thus the fragility of cfghook
> >> fixes for loops).
> >>
> >> Which pass does this deletion?  The correct fix is to fix that pass to
> >> correctly care about the high-level CFG transform it performs.
> >
> > It's cse1.  I didn't see any place in there where I could fix things up,
> > since it looks we aren't directly manipulating the CFG there (it
> > rather find paths, stores them in ebb data, then walks the insns in BBs,
> > and calls cse_insn on each of them, but it's so big
> > and complex that I'm very likely wrong here), only
> > via cleanup_cfg at the end of the pass, which is what calls
> > delete_unreachable_blocks->delete_basic_block, here we delete two
> > latch nodes.  It seems legal to delete them, because at the end of BBs
> > before these latches is an unconditional jump at (label_ref 67).
> > I don't know how could we teach the CSE beast to care about high-level
> > CFG transformations.  Thanks,
> 
> Hmm, I think I remember this case ... (and I fixed it up in
> cfg_cleanup I think).
> 
> So I suppose cse turns a conditional jump into an unconditional one (but
> maybe only cfg_cleanup realizes that)?

Yeah, this is my understanding.
We had:
flags:CCZ=cmp(r66:DI,r67:DI)
, but CSE noticed that r66:DI is in fact r67:DI, so it produces:
flags:CCZ=cmp(r66:DI,r67:DI)
thus we always take one edge and the another one is not needed.

> I think that whoever figures out the latch edge is never taken ought to fixup
> loop structure.  Btw, what also could be done is trying to teach
> fix_loop_structure
> of this case (but only as a last resort I think).

I'll try hack something up in remove_edge, as you suggested on IRC.
Thanks,

	Marek

Patch

--- gcc/cfghooks.c.mp	2012-12-15 04:03:18.388050403 +0100
+++ gcc/cfghooks.c	2012-12-15 04:03:35.313102810 +0100
@@ -541,11 +541,31 @@  delete_basic_block (basic_block bb)
   if (current_loops != NULL)
     {
       struct loop *loop = bb->loop_father;
+      bool is_last_latch = false;
+
+      /* We can get into situation where we have multiple latches.  We
+	 have to cancel the loop, if we remove all the latches--then
+	 the header won't have any incoming back edges.  */
+      if (loop->header
+	  && bb->loop_father != current_loops->tree_root)
+	{
+	  edge e;
+	  edge_iterator ei;
+	  unsigned int n_back_edges = 0;
+	  /* Check whether there's only one latch edge...  */
+	  FOR_EACH_EDGE (e, ei, loop->header->preds)
+	    if (e->flags & EDGE_DFS_BACK)
+	      n_back_edges++;
+	  /* ... and whether we're deleting its latch.  */
+	  is_last_latch = n_back_edges == 1
+			  && find_edge (bb, loop->header);
+	}
 
       /* If we remove the header or the latch of a loop, mark the loop for
 	 removal by setting its header and latch to NULL.  */
       if (loop->latch == bb
-	  || loop->header == bb)
+	  || loop->header == bb
+	  || is_last_latch)
 	{
 	  loop->header = NULL;
 	  loop->latch = NULL;
--- gcc/testsuite/g++.dg/pr54838.C.mp	2012-12-15 03:52:52.436371725 +0100
+++ gcc/testsuite/g++.dg/pr54838.C	2012-12-15 03:52:36.962330626 +0100
@@ -0,0 +1,117 @@ 
+// PR middle-end/54838
+// { dg-do compile }
+// { dg-options "-O2 -ftracer -fno-tree-dce -fno-tree-sra" }
+
+  struct bidirectional_iterator_tag
+  {};
+  struct random_access_iterator_tag:bidirectional_iterator_tag
+  {};
+  template < typename _Category, typename, typename _Distance, typename > struct iterator
+  {
+    typedef _Distance difference_type;
+  };
+  template < typename _Iterator > struct iterator_traits
+  {
+    typedef typename _Iterator::difference_type difference_type;
+  };
+  template < typename _Tp > struct iterator_traits <_Tp * >
+  {
+    typedef random_access_iterator_tag iterator_category;
+    typedef _Tp value_type;
+    typedef int difference_type;
+    typedef _Tp reference;
+  };
+template < typename _Iterator > class reverse_iterator:
+  public
+    iterator
+    <
+    typename
+    iterator_traits
+    <
+    _Iterator
+    >::iterator_category,
+    typename
+    iterator_traits
+    <
+    _Iterator
+    >::value_type,
+    typename
+    iterator_traits
+    <
+    _Iterator
+    >::difference_type, typename iterator_traits < _Iterator >::reference >
+  {
+    _Iterator current;
+  public:
+    typedef _Iterator iterator_type;
+    reverse_iterator (const reverse_iterator & __x):current (__x.current)
+    {}
+    iterator_type base ()
+    {
+      return current;
+    }
+    reverse_iterator operator++ ()
+    {
+      --current;
+    }
+  };
+  template
+    <
+    typename
+    _Iterator
+    >
+    bool
+    operator
+    ==
+    (reverse_iterator < _Iterator > __x, reverse_iterator < _Iterator > __y)
+  {
+    return __x.base () == __y.base ();
+  }
+
+  template
+    <
+    typename
+    _Iterator
+    >
+    typename
+    reverse_iterator
+    <
+    _Iterator
+    >::difference_type
+    operator
+    - (reverse_iterator < _Iterator >, reverse_iterator < _Iterator >)
+  {}
+  template
+    <
+    typename
+    _RandomAccessIterator
+    >
+    _RandomAccessIterator
+    __find
+    (_RandomAccessIterator
+     __first, _RandomAccessIterator __last)
+  {
+    typename
+      iterator_traits
+      <
+      _RandomAccessIterator
+      >::difference_type __trip_count (__last - __first);
+    for (; __trip_count; --__trip_count)
+++__first;
+	return __last;
+  }
+    typedef reverse_iterator < int* > _ForwardIterator1;
+    _ForwardIterator1
+    search
+    (_ForwardIterator1
+     __first1,
+     _ForwardIterator1
+     __last1)
+  {
+    for (;;)
+      {
+	__first1 = __find (__first1, __last1);
+	if (__first1 == __last1)
+	  return __last1;
+      }
+  }
--- gcc/cfgcleanup.c.mp	2012-12-15 04:03:24.144068226 +0100
+++ gcc/cfgcleanup.c	2012-12-15 04:03:35.313102810 +0100
@@ -2836,6 +2836,7 @@  delete_unreachable_blocks (void)
   bool changed = false;
   basic_block b, prev_bb;
 
+  mark_dfs_back_edges ();
   find_unreachable_blocks ();
 
   /* When we're in GIMPLE mode and there may be debug insns, we should