This fixes PR54838 by teaching fix_loop_structure to discover
that all latch edges disappeared and thus a loop is gone.
Conveniently we re-discover latch edges already, so simply move
that earlier and extend it.
The patch also properly honors LOOPS_HAVE_FALLTHRU_PREHEADERS
in fix_loop_structure and sets LOOPS_MAY_HAVE_MULTIPLE_LATCHES
in loop_optimizer_finalize to avoid excessive CFG manipulations
from fix_loop_structure calls.
Bootstrapped and tested on x86_64-unknown-linux-gnu,
profilebootstrapped with release checking on x86_64-unknown-linux-gnu.
Applied to trunk.
Richard.
2012-12-18 Richard Biener <rguent...@suse.de>
PR middle-end/54838
* cfgloopmanip.c (fix_loop_structure): Re-discover latch
edges first and mark loops for removal if no latch edges remain.
Properly re-create LOOPS_HAVE_FALLTHRU_PREHEADERS.
* loop-init.c (loop_optimizer_finalize): Set
LOOPS_MAY_HAVE_MULTIPLE_LATCHES.
* g++.dg/torture/pr54838.C: New testcase.
Index: gcc/cfgloopmanip.c
===================================================================
*** gcc/cfgloopmanip.c (revision 194552)
--- gcc/cfgloopmanip.c (working copy)
*************** fix_loop_structure (bitmap changed_bbs)
*** 1793,1798 ****
--- 1793,1832 ----
record_exits = true;
}
+ /* First re-compute loop latches. */
+ FOR_EACH_LOOP (li, loop, 0)
+ {
+ edge_iterator ei;
+ edge e, first_latch = NULL, latch = NULL;
+
+ if (!loop->header)
+ continue;
+
+ FOR_EACH_EDGE (e, ei, loop->header->preds)
+ if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header))
+ {
+ if (!first_latch)
+ first_latch = latch = e;
+ else
+ {
+ latch = NULL;
+ break;
+ }
+ }
+ /* If there was no latch, schedule the loop for removal. */
+ if (!first_latch)
+ loop->header = NULL;
+ /* If there was a single latch and it belongs to the loop of the
+ header, record it. */
+ else if (latch
+ && latch->src->loop_father == loop)
+ loop->latch = latch->src;
+ /* Otherwise there are multiple latches which are eventually
+ disambiguated below. */
+ else
+ loop->latch = NULL;
+ }
+
/* Remove the dead loops from structures. We start from the innermost
loops, so that when we remove the loops, we know that the loops inside
are preserved, and do not waste time relinking loops that will be
*************** fix_loop_structure (bitmap changed_bbs)
*** 1849,1882 ****
}
}
- /* Then re-compute the single latch if there is one. */
- FOR_EACH_LOOP (li, loop, 0)
- {
- edge_iterator ei;
- edge e, latch = NULL;
- FOR_EACH_EDGE (e, ei, loop->header->preds)
- if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header))
- {
- if (!latch)
- latch = e;
- else
- {
- latch = NULL;
- break;
- }
- }
- if (latch
- && latch->src->loop_father == loop)
- loop->latch = latch->src;
- else
- loop->latch = NULL;
- }
-
if (!loops_state_satisfies_p (LOOPS_MAY_HAVE_MULTIPLE_LATCHES))
disambiguate_loops_with_multiple_latches ();
if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS))
! create_preheaders (CP_SIMPLE_PREHEADERS);
if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
force_single_succ_latches ();
--- 1883,1900 ----
}
}
if (!loops_state_satisfies_p (LOOPS_MAY_HAVE_MULTIPLE_LATCHES))
disambiguate_loops_with_multiple_latches ();
if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS))
! {
! int cp_flags = CP_SIMPLE_PREHEADERS;
!
! if (loops_state_satisfies_p (LOOPS_HAVE_FALLTHRU_PREHEADERS))
! cp_flags |= CP_FALLTHRU_PREHEADERS;
!
! create_preheaders (cp_flags);
! }
if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
force_single_succ_latches ();
Index: gcc/loop-init.c
===================================================================
*** gcc/loop-init.c (revision 194552)
--- gcc/loop-init.c (working copy)
*************** loop_optimizer_finalize (void)
*** 133,138 ****
--- 133,139 ----
| LOOPS_HAVE_PREHEADERS
| LOOPS_HAVE_SIMPLE_LATCHES
| LOOPS_HAVE_FALLTHRU_PREHEADERS);
+ loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
goto loop_fini_done;
}
Index: gcc/testsuite/g++.dg/torture/pr54838.C
===================================================================
*** gcc/testsuite/g++.dg/torture/pr54838.C (revision 0)
--- gcc/testsuite/g++.dg/torture/pr54838.C (working copy)
***************
*** 0 ****
--- 1,102 ----
+ // { dg-do compile }
+ // { dg-options "-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;
+ }
+ }
