| Message ID | 20121217002156.GE2432@redhat.com |
|---|---|
| State | New |
| Headers | show |
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
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
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
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
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
--- 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