[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695 --- Comment #23 from Richard Biener rguenth at gcc dot gnu.org 2012-10-29 14:25:32 UTC --- Author: rguenth Date: Mon Oct 29 14:25:22 2012 New Revision: 192943 URL: http://gcc.gnu.org/viewcvs?root=gccview=revrev=192943 Log: 2012-10-29 Richard Guenther rguent...@suse.de PR middle-end/53695 * tracer.c (tracer): Fixup loop structure. * cfgloopmanip.c (force_single_succ_latches): Add assert. (fix_loop_structure): Re-compute loop latches and disambiguate loops with multiple latches if required. * gcc.dg/torture/pr53695.c: New testcase. Added: trunk/gcc/testsuite/gcc.dg/torture/pr53695.c Modified: trunk/gcc/ChangeLog trunk/gcc/cfgloopmanip.c trunk/gcc/testsuite/ChangeLog trunk/gcc/tracer.c
[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695 Richard Biener rguenth at gcc dot gnu.org changed: What|Removed |Added Status|ASSIGNED|RESOLVED Resolution||FIXED --- Comment #24 from Richard Biener rguenth at gcc dot gnu.org 2012-10-29 14:33:08 UTC --- Fixed.
[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695 Richard Biener rguenth at gcc dot gnu.org changed: What|Removed |Added Priority|P1 |P3 --- Comment #22 from Richard Biener rguenth at gcc dot gnu.org 2012-10-26 11:57:19 UTC --- Ok, first of all we need to call fix_loop_structure from tracer. That properly associates blocks with loops. The issue that remains is that disambiguate_loops_with_multiple_latches doesn't disambiguate the loop because we keep loop-latch as non-NULL Later local-pure-const asks for LOOPS_NORMAL and create_preheaders cannot deal with the situation, breaking loop structure. Thus, first of all fix_loop_structure needs to re-compute latches properly. I have a patch.
[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695 Richard Guenther rguenth at gcc dot gnu.org changed: What|Removed |Added Priority|P3 |P1
[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695
--- Comment #10 from rguenther at suse dot de rguenther at suse dot de
2012-08-23 07:29:04 UTC ---
On Wed, 22 Aug 2012, steven at gcc dot gnu.org wrote:
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695
Steven Bosscher steven at gcc dot gnu.org changed:
What|Removed |Added
CC||steven at gcc dot gnu.org
--- Comment #6 from Steven Bosscher steven at gcc dot gnu.org 2012-08-22
19:26:03 UTC ---
(In reply to comment #4)
Wouldn't this patch disable all loop detection for loops with exceptions and
so
on in them? That seems a rather big hammer to this problem. It should be
enough
to check only for EH_ABNORMAL.
Well, yes - the patch isn't really a fix for the issue but addresses
something I noticed in the loop detection code. Namely that it happily
detects a loop like (1)
header
| \
(ab) |
| /
latch
thus, a loop where there isn't a single path in the CFG that is
non-abnormal/EH. That isn't a useful loop. Loops with EH are still
handled as they look like (2)
header ---
| \
BB \
/ \ \
(eh) (fallthru)|
/ | |
latch
thus, EH edges should also not form loops but always act as loop
exits.
That patch masks the underlying issue of course, but I still think
loops of the form (1) are not useful (we cannot perform a reasonable
loop transform on it - we can handle abnormal / eh exits and entries
but not loop paths).
What caused the ICE to appear anyway? There is a problem I can see in
dfs_enumerate_from that could cause it to ICE.
At the point of the ICE, we have the following CFG (cc1 -O2 -ftracer):
(gdb) p current_pass-name
$5 = 0x13195b0 local-pure-const
(gdb) p brief_dump_cfg(stderr,-1)
;; basic block 2, loop depth 0, count 0, freq 6667, maybe hot
;; prev block 0, next block 3, flags: (NEW, REACHABLE)
;; pred: ENTRY [100.0%] (FALLTHRU,EXECUTABLE)
;; succ: 3 [100.0%] (FALLTHRU,EXECUTABLE)
;; basic block 3, loop depth 0, count 0, freq 6667, maybe hot
;; prev block 2, next block 4, flags: (NEW, REACHABLE, IRREDUCIBLE_LOOP)
;; pred: 2 [100.0%] (FALLTHRU,EXECUTABLE)
;; succ: 5 [100.0%] (FALLTHRU,IRREDUCIBLE_LOOP,EXECUTABLE)
;; basic block 4, loop depth 0, count 0, freq 0
;; Invalid sum of incoming frequencies , should be 0
;; prev block 3, next block 5, flags: (NEW, REACHABLE, IRREDUCIBLE_LOOP)
;; pred: 5 [33.3%] (ABNORMAL,IRREDUCIBLE_LOOP,EXECUTABLE)
;; succ: 5 [100.0%] (FALLTHRU,DFS_BACK,IRREDUCIBLE_LOOP,EXECUTABLE)
;; basic block 5, loop depth 1, count 0, freq 1, maybe hot
;; prev block 4, next block 6, flags: (NEW, REACHABLE)
;; pred: 4 [100.0%] (FALLTHRU,DFS_BACK,IRREDUCIBLE_LOOP,EXECUTABLE)
;; 6 [100.0%] (FALLTHRU,DFS_BACK,EXECUTABLE)
;; 3 [100.0%] (FALLTHRU,IRREDUCIBLE_LOOP,EXECUTABLE)
;; succ: 4 [33.3%] (ABNORMAL,IRREDUCIBLE_LOOP,EXECUTABLE)
;; 6 [33.3%] (ABNORMAL,EXECUTABLE)
;; 7 [33.3%] (ABNORMAL,EXECUTABLE)
;; basic block 6, loop depth 1, count 0, freq , maybe hot
;; prev block 5, next block 7, flags: (NEW, REACHABLE)
;; pred: 5 [33.3%] (ABNORMAL,EXECUTABLE)
;; succ: 5 [100.0%] (FALLTHRU,DFS_BACK,EXECUTABLE)
;; basic block 7, loop depth 0, count 0, freq , maybe hot
;; prev block 6, next block 1, flags: (NEW, REACHABLE)
;; pred: 5 [33.3%] (ABNORMAL,EXECUTABLE)
;; succ: EXIT [100.0%]
Or in human-readable form:
ENTRY
|
V
|
2(0)
|
|
V
|
3(0)
|
\
\
\
\
\
\
++ | +-+
| \ V / |
| \ | /|
+-4(1)--5(1)--6(1)-+
(a) | (a)
|
|(a)
|
7(0)
|
EXIT
where (a) denotes abnormal edge, of course, and (0) or (1) is the loop depth
at this point.
The loop detected here is the region with the abnormal edges, for blocks 4, 5,
and 6. The detected loop has header bb 5 and latch bb 6, which is not
clearly
wrong: this is just two loops with the same header. But this confuses
dfs_enumerate_from, which does a reverse DFS from basic block 5 with predicate
glb_enum_p. The DFS visits block 5, 4, and 6, but dfs_enumerate_from is told
to
expect to visit only 2 basic blocks, not 3. The reason it sees 3 is that
glb_enum_p is this:
/* Enumeration predicate for get_loop_body_with_size. */
static bool
glb_enum_p (const_basic_block bb, const void *glb_loop)
{
const struct loop *const loop = (const struct loop *) glb_loop;
return (bb != loop-header
dominated_by_p (CDI_DOMINATORS, bb, loop-header));
}
called with loop-header == bb5, and called with bb==4 and bb==6. And
[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695 --- Comment #11 from rguenther at suse dot de rguenther at suse dot de 2012-08-23 07:36:46 UTC --- On Wed, 22 Aug 2012, steven at gcc dot gnu.org wrote: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695 --- Comment #9 from Steven Bosscher steven at gcc dot gnu.org 2012-08-22 21:33:18 UTC --- I think the right fix for this bug is to use disambiguate_multiple_latches in the loop updating code (fix_loop_structure), but I'm not sure where to put it. Not sure - we can handle multiple latches just fine (loop-latch will be NULL). But I see the loop state does not reflect that. Maybe Index: gcc/cfgloopmanip.c === --- gcc/cfgloopmanip.c (revision 190613) +++ gcc/cfgloopmanip.c (working copy) @@ -1715,6 +1716,9 @@ fix_loop_structure (bitmap changed_bbs) } } + if (!loop_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); which matches the order in which loop_optimizer_init calls it. Richard.
[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695 --- Comment #12 from stevenb.gcc at gmail dot com stevenb.gcc at gmail dot com 2012-08-23 07:56:13 UTC --- The patch is of couse a big hammer because it has a cost, but IMHO it still makes sense. I'm not convinced. GCC has always detected this kind of loop (even the old non-cfg loop code recognizes this kind of loop) and it has never caused any problems before your patch to keep the loop structure up-to-date. To me, this means that the fix should be in the loop updating, not in abandoning a decades-old behavior of the compiler.
[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695 --- Comment #13 from rguenther at suse dot de rguenther at suse dot de 2012-08-23 08:07:18 UTC --- On Thu, 23 Aug 2012, rguenther at suse dot de wrote: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695 --- Comment #11 from rguenther at suse dot de rguenther at suse dot de 2012-08-23 07:36:46 UTC --- On Wed, 22 Aug 2012, steven at gcc dot gnu.org wrote: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695 --- Comment #9 from Steven Bosscher steven at gcc dot gnu.org 2012-08-22 21:33:18 UTC --- I think the right fix for this bug is to use disambiguate_multiple_latches in the loop updating code (fix_loop_structure), but I'm not sure where to put it. Not sure - we can handle multiple latches just fine (loop-latch will be NULL). But I see the loop state does not reflect that. Maybe Index: gcc/cfgloopmanip.c === --- gcc/cfgloopmanip.c (revision 190613) +++ gcc/cfgloopmanip.c (working copy) @@ -1715,6 +1716,9 @@ fix_loop_structure (bitmap changed_bbs) } } + if (!loop_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); which matches the order in which loop_optimizer_init calls it. Doesn't fix the testcase. We fail during verify_loop_structure and the loop state _does_ have LOOPS_MAY_HAVE_MULTIPLE_LATCHES set. Now, for the testcase we at this point just have a single loop left (we don't recognize the loop with the abnormal path from header to latch). Btw, I'm looking at the reduced testcase in the patch (yes, that's a slightly different situation but simpler to analyze and fails the same way). So what's wrong here is indeed loop-num_nodes (we don't account the other loop to loop 1 and we do not properly mark the loop as having multiple latches). Already the input to tracer is wrong in that we have lost a loop, the one with abnormal path from latch to header (which we _do_ reject during loop discovery!). So what happens is that we turn this loop into one that would have been recognized, swap header and latch and thus get the abnormal edge to a tolerated place (header to latch). That inconsistency is what my patch tries to address (another way would be to simply allow EH/abnormal latch - header edges as well). So, tracer transforms bb2 | bb3 | ^ | |(ab) v | bb4 (loop1 header) | | \ bb5 (loop1 latch)v BB6 - BB1 by duplicating bb3 to bb2 | bb7 (duplicate of bb3) | ---bb4 (loop1 header) (ab) | / \ \ | | bb5 (loop1 latch) bb3 but it does not add bb3 to loop1, nor zero out its latch and setting may-have-multiple-latches. The cfghook only takes care of updating the loop structure with respect to the _new_ basic block but does not consider that the old one magically becomes part of a loop. But IMHO the bug is either that we don't consider it part of the loop before this transform or that we do consider it part of the loop after the transform! Which is what my patch tries to address. Richard.
[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695 --- Comment #14 from rguenther at suse dot de rguenther at suse dot de 2012-08-23 08:10:15 UTC --- On Thu, 23 Aug 2012, stevenb.gcc at gmail dot com wrote: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695 --- Comment #12 from stevenb.gcc at gmail dot com stevenb.gcc at gmail dot com 2012-08-23 07:56:13 UTC --- The patch is of couse a big hammer because it has a cost, but IMHO it still makes sense. I'm not convinced. GCC has always detected this kind of loop (even the old non-cfg loop code recognizes this kind of loop) and it has never caused any problems before your patch to keep the loop structure up-to-date. To me, this means that the fix should be in the loop updating, not in abandoning a decades-old behavior of the compiler. It's inconsistent in that it considers header | ^ (ab) | v | latch a loop but not header | ^ | (ab) v | latch and tracer rotates this loop by swapping dominance relationship between header and latch but not makes the non-loop magically a loop. My patch makes both not a loop.
[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695
--- Comment #15 from stevenb.gcc at gmail dot com stevenb.gcc at gmail dot
com 2012-08-23 08:49:32 UTC ---
On Thu, Aug 23, 2012 at 10:07 AM, rguenther at suse dot de
gcc-bugzi...@gcc.gnu.org wrote:
Already the input to tracer is wrong in that we have lost
a loop, the one with abnormal path from latch to header (which
we _do_ reject during loop discovery!).
But this isn't a natural loop. It's an irreducible loop with loop
entries in basic block 3 and basic block 4 (in the pre-tracer CFG from
comment #7) and loop discovery doesn't record irreducible loop.
What tracer does here is known as node splitting to make an
irreducible region reducible. I don't think it's a
intentional/conscious node splitting but tracer does have the effect
of node splitting. After tracer, the loop with bbs {4,5,3} is a
natural loop and the CFG is reducible.
So what happens is
that we turn this loop into one that would have been recognized,
swap header and latch and thus get the abnormal edge to a tolerated
place (header to latch). That inconsistency is what my patch tries
to address (another way would be to simply allow EH/abnormal
latch - header edges as well).
But with your patch we'd also reject all already reducible loops if
there are only paths with one or more abnormal edges from the loop
header to the latch. That is more conservative than necessary. Also,
AFAIU, with your patch we'd reduce loops with a finally block
(something like
for(;;){try{...maybe_throw;...;if(...)break;}finally{...}}) because
all paths to the loop latch would go through the finally block via EH
edges.
but it does not add bb3 to loop1, nor zero out its latch
and setting may-have-multiple-latches.
That, to me, is the bug we should try to solve here.
The cfghook
only takes care of updating the loop structure with
respect to the _new_ basic block but does not consider
that the old one magically becomes part of a loop.
I think it may be possible to construct a test case just like this one
with an initially irreducible CFG that tracer makes reducible.
Anyway, consider this test case, which is the pre-tracer CFG but
without abnormal edges:
void do_something_1 (void);
void do_something_2 (void);
int some_cond (void);
void make_bb_non_empty ();
void
foo (void)
{
bb2:
make_bb_non_empty ();
goto bb3;
bb4:
switch (some_cond ())
{
case 1:
goto bb3;
case 2:
goto bb5;
default:
goto bb6;
}
bb3:
do_something_1 ();
goto bb4;
bb5:
do_something_2 ();
goto bb4;
bb6:
return;
}
This gives the following CFG in the .129t.cddce2 dump:
; 3 loops found
;;
;; Loop 0
;; header 0, latch 1
;; depth 0, outer -1
;; nodes: 0 1 2 3 4 5 6 7
;;
;; Loop 1
;; header 5, latch 4
;; depth 1, outer 0
;; nodes: 5 4 3 6
;;
;; Loop 2
;; header 3, latch 6
;; depth 2, outer 1
;; nodes: 3 6
ENTRY
|
V
|
2(0)
|
|
V
|
| +--4(1)-+
| | |
| V ^
| | |
| | +
| + /
| | /
5(1)--3(2)--6(2)-+
/\ |
/ +-+
/
|
V
|
7(0)
|
EXIT
So now the loop {5,4,3,6} is detected, even though the CFG is
basically the same as the pre-tracer one from comment #7 (only
difference is that the critical edge 3,5 in the above CFG is split
to give basic block 4.
Makes me wonder why the loop isn't recognized in the original test case...
[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695 --- Comment #16 from Steven Bosscher steven at gcc dot gnu.org 2012-08-23 08:53:04 UTC --- (In reply to comment #15) Makes me wonder why the loop isn't recognized in the original test case... Ah, maybe because bb3 has an abnormal predecessor and is therefore ignored as a potential loop header? /* If we have an abnormal predecessor, do not consider the loop (not worth the problems). */ if (bb_has_abnormal_pred (header)) continue; Which brings things back to my question why this kind of loop header is rejected! :-)
[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695
--- Comment #17 from rguenther at suse dot de rguenther at suse dot de
2012-08-23 09:19:04 UTC ---
On Thu, 23 Aug 2012, steven at gcc dot gnu.org wrote:
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695
--- Comment #16 from Steven Bosscher steven at gcc dot gnu.org 2012-08-23
08:53:04 UTC ---
(In reply to comment #15)
Makes me wonder why the loop isn't recognized in the original test case...
Ah, maybe because bb3 has an abnormal predecessor and is therefore ignored as
a
potential loop header?
/* If we have an abnormal predecessor, do not consider the
loop (not worth the problems). */
if (bb_has_abnormal_pred (header))
continue;
Which brings things back to my question why this kind of loop header is
rejected! :-)
Because gimple_split_edge doesn't like to split abnormal edges,
called via force_single_succ_latches (). So we do definitely
not allow abnormal latch - header edges. Still abnormal loop entries
should be fine. So,
Index: gcc/cfgloop.c
===
--- gcc/cfgloop.c (revision 190613)
+++ gcc/cfgloop.c (working copy)
@@ -400,24 +400,21 @@ flow_loops_find (struct loops *loops)
{
edge_iterator ei;
- /* If we have an abnormal predecessor, do not consider the
-loop (not worth the problems). */
- if (bb_has_abnormal_pred (header))
- continue;
-
FOR_EACH_EDGE (e, ei, header-preds)
{
basic_block latch = e-src;
- gcc_assert (!(e-flags EDGE_ABNORMAL));
-
/* Look for back edges where a predecessor is dominated
by this block. A natural loop has a single entry
node (header) that dominates all the nodes in the
loop. It also has single back edge to the header
from a latch node. */
if (latch != ENTRY_BLOCK_PTR
- dominated_by_p (CDI_DOMINATORS, latch, header))
+ dominated_by_p (CDI_DOMINATORS, latch, header)
+ /* We cannot make latches simple by splitting the
+latch - header edge if the latch edge is abnormal. */
+ (single_succ_p (latch)
+ || !(e-flags EDGE_ABNORMAL)))
{
/* Shared headers should be eliminated by now. */
SET_BIT (headers, header-index);
should work. But doesn't fix the testcase (of course).
Richard.
[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695 --- Comment #18 from rguenther at suse dot de rguenther at suse dot de 2012-08-23 09:22:54 UTC --- On Thu, 23 Aug 2012, rguenther at suse dot de wrote: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695 --- Comment #17 from rguenther at suse dot de rguenther at suse dot de 2012-08-23 09:19:04 UTC --- On Thu, 23 Aug 2012, steven at gcc dot gnu.org wrote: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695 --- Comment #16 from Steven Bosscher steven at gcc dot gnu.org 2012-08-23 08:53:04 UTC --- (In reply to comment #15) Makes me wonder why the loop isn't recognized in the original test case... Ah, maybe because bb3 has an abnormal predecessor and is therefore ignored as a potential loop header? /* If we have an abnormal predecessor, do not consider the loop (not worth the problems). */ if (bb_has_abnormal_pred (header)) continue; Which brings things back to my question why this kind of loop header is rejected! :-) Because gimple_split_edge doesn't like to split abnormal edges, called via force_single_succ_latches (). So we do definitely not allow abnormal latch - header edges. Still abnormal loop entries should be fine. So, But we can't create pre-headers then, too. So optimizers that want pre-headers would be confused (well, or ICE). Why can we not split abnormal edges?
[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695
--- Comment #19 from Steven Bosscher steven at gcc dot gnu.org 2012-08-23
09:44:18 UTC ---
FWIW, applying the transformation tracer performs on the test case by hand:
void
foo (const void * * p)
{
void *labs[] = { l1, l2, l3 };
void *gotovar;
long unsigned int p0;
long unsigned int t7;
long unsigned int t13;
gotovar = p;
p0 = (long unsigned int) gotovar;
t13 = p0 + 8;
p = (const void **) t13;
goto bb5;
l1:
gotovar = p;
p0 = (long unsigned int) gotovar;
t7 = p0 + 8;
p = (const void **) t7;
goto bb5;
bb5:
goto *gotovar;
l2:
gotovar = p;
goto bb5;
l3:
return;
}
This compiles without problem. Gives:
Disambiguating loop 1 with multiple latches
Merged latch edges of loop 1
;; 2 loops found
;;
;; Loop 0
;; header 0, latch 1
;; depth 0, outer -1
;; nodes: 0 1 2 3 4 7 5 6
;;
;; Loop 1
;; header 7, latch 4
;; depth 1, outer 0
;; nodes: 7 4 5 3
;; 2 succs { 7 }
;; 3 succs { 4 }
;; 4 succs { 7 }
;; 7 succs { 3 5 6 }
;; 5 succs { 4 }
;; 6 succs { 1 }
[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695
--- Comment #20 from rguenther at suse dot de rguenther at suse dot de
2012-08-23 11:00:29 UTC ---
On Thu, 23 Aug 2012, rguenther at suse dot de wrote:
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695
--- Comment #17 from rguenther at suse dot de rguenther at suse dot de
2012-08-23 09:19:04 UTC ---
On Thu, 23 Aug 2012, steven at gcc dot gnu.org wrote:
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695
--- Comment #16 from Steven Bosscher steven at gcc dot gnu.org 2012-08-23
08:53:04 UTC ---
(In reply to comment #15)
Makes me wonder why the loop isn't recognized in the original test case...
Ah, maybe because bb3 has an abnormal predecessor and is therefore ignored
as a
potential loop header?
/* If we have an abnormal predecessor, do not consider the
loop (not worth the problems). */
if (bb_has_abnormal_pred (header))
continue;
Which brings things back to my question why this kind of loop header is
rejected! :-)
Because gimple_split_edge doesn't like to split abnormal edges,
called via force_single_succ_latches (). So we do definitely
not allow abnormal latch - header edges. Still abnormal loop entries
should be fine. So,
Index: gcc/cfgloop.c
===
--- gcc/cfgloop.c (revision 190613)
+++ gcc/cfgloop.c (working copy)
@@ -400,24 +400,21 @@ flow_loops_find (struct loops *loops)
{
edge_iterator ei;
- /* If we have an abnormal predecessor, do not consider the
-loop (not worth the problems). */
- if (bb_has_abnormal_pred (header))
- continue;
-
FOR_EACH_EDGE (e, ei, header-preds)
{
basic_block latch = e-src;
- gcc_assert (!(e-flags EDGE_ABNORMAL));
-
/* Look for back edges where a predecessor is dominated
by this block. A natural loop has a single entry
node (header) that dominates all the nodes in the
loop. It also has single back edge to the header
from a latch node. */
if (latch != ENTRY_BLOCK_PTR
- dominated_by_p (CDI_DOMINATORS, latch, header))
+ dominated_by_p (CDI_DOMINATORS, latch, header)
+ /* We cannot make latches simple by splitting the
+latch - header edge if the latch edge is abnormal. */
+ (single_succ_p (latch)
+ || !(e-flags EDGE_ABNORMAL)))
{
/* Shared headers should be eliminated by now. */
SET_BIT (headers, header-index);
should work. But doesn't fix the testcase (of course).
Btw, another idea would be to make labels that are target of
abnormal edges end a basic-block. That way you'd have the
edges pre-split.
Richard.
[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695
--- Comment #21 from rguenther at suse dot de rguenther at suse dot de
2012-08-23 11:22:19 UTC ---
On Thu, 23 Aug 2012, rguenther at suse dot de wrote:
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695
Btw, another idea would be to make labels that are target of
abnormal edges end a basic-block. That way you'd have the
edges pre-split.
Like so, doesn't help this testcase but maybe the Fortran issues.
Richard.
Index: gcc/tree-cfg.c
===
--- gcc/tree-cfg.c(revision 190613)
+++ gcc/tree-cfg.c(working copy)
@@ -670,6 +674,10 @@ make_edges (void)
}
break;
+case GIMPLE_LABEL:
+ fallthru = true;
+ break;
+
default:
gcc_assert (!stmt_ends_bb_p (last));
fallthru = true;
@@ -2440,7 +2527,9 @@ stmt_starts_bb_p (gimple stmt, gimple pr
bool
stmt_ends_bb_p (gimple t)
{
- return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
+ return (is_ctrl_stmt (t) || is_ctrl_altering_stmt (t)
+ || (gimple_code (t) == GIMPLE_LABEL
+ FORCED_LABEL (gimple_label_label (t;
}
/* Remove block annotations and other data structures. */
Index: gcc/tree-cfgcleanup.c
===
--- gcc/tree-cfgcleanup.c(revision 190613)
+++ gcc/tree-cfgcleanup.c(working copy)
@@ -300,7 +300,8 @@ tree_forwarder_block_p (basic_block bb,
switch (gimple_code (stmt))
{
case GIMPLE_LABEL:
- if (DECL_NONLOCAL (gimple_label_label (stmt)))
+ if (DECL_NONLOCAL (gimple_label_label (stmt))
+ || FORCED_LABEL (gimple_label_label (stmt)))
return false;
if (optimize == 0 gimple_location (stmt) != locus)
return false;
[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695 --- Comment #5 from Richard Guenther rguenth at gcc dot gnu.org 2012-08-22 09:36:10 UTC --- Patch that was posted (no comments yet): http://gcc.gnu.org/ml/gcc-patches/2012-06/msg01754.html
[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695
Steven Bosscher steven at gcc dot gnu.org changed:
What|Removed |Added
CC||steven at gcc dot gnu.org
--- Comment #6 from Steven Bosscher steven at gcc dot gnu.org 2012-08-22
19:26:03 UTC ---
(In reply to comment #4)
Wouldn't this patch disable all loop detection for loops with exceptions and so
on in them? That seems a rather big hammer to this problem. It should be enough
to check only for EH_ABNORMAL.
What caused the ICE to appear anyway? There is a problem I can see in
dfs_enumerate_from that could cause it to ICE.
At the point of the ICE, we have the following CFG (cc1 -O2 -ftracer):
(gdb) p current_pass-name
$5 = 0x13195b0 local-pure-const
(gdb) p brief_dump_cfg(stderr,-1)
;; basic block 2, loop depth 0, count 0, freq 6667, maybe hot
;; prev block 0, next block 3, flags: (NEW, REACHABLE)
;; pred: ENTRY [100.0%] (FALLTHRU,EXECUTABLE)
;; succ: 3 [100.0%] (FALLTHRU,EXECUTABLE)
;; basic block 3, loop depth 0, count 0, freq 6667, maybe hot
;; prev block 2, next block 4, flags: (NEW, REACHABLE, IRREDUCIBLE_LOOP)
;; pred: 2 [100.0%] (FALLTHRU,EXECUTABLE)
;; succ: 5 [100.0%] (FALLTHRU,IRREDUCIBLE_LOOP,EXECUTABLE)
;; basic block 4, loop depth 0, count 0, freq 0
;; Invalid sum of incoming frequencies , should be 0
;; prev block 3, next block 5, flags: (NEW, REACHABLE, IRREDUCIBLE_LOOP)
;; pred: 5 [33.3%] (ABNORMAL,IRREDUCIBLE_LOOP,EXECUTABLE)
;; succ: 5 [100.0%] (FALLTHRU,DFS_BACK,IRREDUCIBLE_LOOP,EXECUTABLE)
;; basic block 5, loop depth 1, count 0, freq 1, maybe hot
;; prev block 4, next block 6, flags: (NEW, REACHABLE)
;; pred: 4 [100.0%] (FALLTHRU,DFS_BACK,IRREDUCIBLE_LOOP,EXECUTABLE)
;; 6 [100.0%] (FALLTHRU,DFS_BACK,EXECUTABLE)
;; 3 [100.0%] (FALLTHRU,IRREDUCIBLE_LOOP,EXECUTABLE)
;; succ: 4 [33.3%] (ABNORMAL,IRREDUCIBLE_LOOP,EXECUTABLE)
;; 6 [33.3%] (ABNORMAL,EXECUTABLE)
;; 7 [33.3%] (ABNORMAL,EXECUTABLE)
;; basic block 6, loop depth 1, count 0, freq , maybe hot
;; prev block 5, next block 7, flags: (NEW, REACHABLE)
;; pred: 5 [33.3%] (ABNORMAL,EXECUTABLE)
;; succ: 5 [100.0%] (FALLTHRU,DFS_BACK,EXECUTABLE)
;; basic block 7, loop depth 0, count 0, freq , maybe hot
;; prev block 6, next block 1, flags: (NEW, REACHABLE)
;; pred: 5 [33.3%] (ABNORMAL,EXECUTABLE)
;; succ: EXIT [100.0%]
Or in human-readable form:
ENTRY
|
V
|
2(0)
|
|
V
|
3(0)
|
\
\
\
\
\
\
++ | +-+
| \ V / |
| \ | /|
+-4(1)--5(1)--6(1)-+
(a) | (a)
|
|(a)
|
7(0)
|
EXIT
where (a) denotes abnormal edge, of course, and (0) or (1) is the loop depth
at this point.
The loop detected here is the region with the abnormal edges, for blocks 4, 5,
and 6. The detected loop has header bb 5 and latch bb 6, which is not clearly
wrong: this is just two loops with the same header. But this confuses
dfs_enumerate_from, which does a reverse DFS from basic block 5 with predicate
glb_enum_p. The DFS visits block 5, 4, and 6, but dfs_enumerate_from is told to
expect to visit only 2 basic blocks, not 3. The reason it sees 3 is that
glb_enum_p is this:
/* Enumeration predicate for get_loop_body_with_size. */
static bool
glb_enum_p (const_basic_block bb, const void *glb_loop)
{
const struct loop *const loop = (const struct loop *) glb_loop;
return (bb != loop-header
dominated_by_p (CDI_DOMINATORS, bb, loop-header));
}
called with loop-header == bb5, and called with bb==4 and bb==6. And since bb5
dominates both bb4 and bb6, the predicate returns true for both, and
dfs_enumerate_from ends up visiting 3 basic blocks. So why is it told to expect
two blocks in the first place, instead of 3?
dfs_enumerate_from is called, via get_loop_body_with_size, from get_loop_body:
tv = get_loop_body_with_size (loop, body, loop-num_nodes);
The natural loop 1 has only two nodes, namely bb5 and bb6. So where does bb4
come from? That's tracer at work.
So the root cause here, is that tracer should either update the loop tree or
refrain from duplicating blocks if it results in a single loop header
dominating two separate loops.
Irreducibility and updating the loop tree are the key to fixing this bug, not
the big hammer patch of comment #4.
[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695 --- Comment #7 from Steven Bosscher steven at gcc dot gnu.org 2012-08-22 20:13:32 UTC --- Before tracer we have this CFG: ENTRY | V | 2(0) | | V |(a) | +--+ V /| | / / (a) 3(1)--4(1)5(1)-+ /\ | / +---+ / | V(a) | 6(0) | EXIT and (BASIC_BLOCK(3)-flags IRREDUCIBLE_LOOP) is true. The IRREDUCIBLE_LOOP flags appear to be out-of-date because the flag is not set on BASIC_BLOCK(4) but it's set on all edges out of it so that's good enough. Tracer goes to work on this and finds the following traces: Trace seed 4 [1],4 [1],3 [6667] forward 2 [6667],3 [6667],4 [1] Duplicated 3 as 7 [6667] covered now 66.7 Trace seed 6 [] forward 6 [] covered now 100.0 The resulting flow graph was already shown in comment #6, but now with the basic block numbers before the CFG is cleaned up: ENTRY | V | 2(0) | | V | 7(0) | \ \ \ \ \ \ ++ | +-+ | \ V / | | \ | /| +-3(1)--4(1)--5(1)-+ (a) | (a) | |(a) | 6(0) | EXIT
[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695
--- Comment #8 from Steven Bosscher steven at gcc dot gnu.org 2012-08-22
20:20:22 UTC ---
FWIW, GCC handles loops with one header and multiple latches just fine:
void do_something_1 (void);
void do_something_2 (void);
int some_cond (void);
void
foo (void)
{
while (1)
{
switch (some_cond ())
{
case 1:
do_something_1 ();
continue;
case 2:
do_something_2 ();
continue;
default:
return;
}
}
}
;; 2 loops found
;;
;; Loop 0
;; header 0, latch 1
;; depth 0, outer -1
;; nodes: 0 1 2 3 4 5 6 7
;;
;; Loop 1
;; header 4, latch 3
;; depth 1, outer 0
;; nodes: 4 3 6 5
;; 2 succs { 4 }
;; 3 succs { 4 }
;; 4 succs { 7 5 6 }
;; 5 succs { 3 }
;; 6 succs { 3 }
;; 7 succs { 1 }
foo ()
{
int _4;
bb 2:
goto bb 4;
bb 3:
bb 4:
_4 = some_cond ();
switch (_4) default: L6, case 1: L1, case 2: L2
L1:
do_something_1 ();
goto bb 3;
L2:
do_something_2 ();
goto bb 3;
L6:
return;
}
Note the single latch.
[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695 --- Comment #9 from Steven Bosscher steven at gcc dot gnu.org 2012-08-22 21:33:18 UTC --- I think the right fix for this bug is to use disambiguate_multiple_latches in the loop updating code (fix_loop_structure), but I'm not sure where to put it.
[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695
--- Comment #4 from Richard Guenther rguenth at gcc dot gnu.org 2012-06-27
10:32:53 UTC ---
I am testing
Index: gcc/cfgloop.c
===
*** gcc/cfgloop.c (revision 188987)
--- gcc/cfgloop.c (working copy)
*** init_loops_structure (struct loops *loop
*** 365,370
--- 365,406
loops-tree_root = root;
}
+ /* Return true if there is a path from FROM to the dominated TO where no
+edge on that path contains FLAGS. */
+
+ static bool
+ path_without_edge_flags (basic_block from, basic_block to, int flags)
+ {
+ do
+ {
+ /* At least one such path to the immediate dominator. */
+ if (single_pred_p (to))
+ {
+ edge e = single_pred_edge (to);
+ if (e-flags flags)
+ return false;
+ to = e-src;
+ }
+ else
+ {
+ basic_block dom = get_immediate_dominator (CDI_DOMINATORS, to);
+ edge_iterator ei;
+ edge e;
+
+ FOR_EACH_EDGE(e, ei, to-preds)
+ if (!(e-flags flags)
+(e-src == dom
+ || path_without_edge_flags (dom, e-src, flags)))
+ break;
+
+ to = dom;
+ }
+ }
+ while (to != from);
+
+ return true;
+ }
+
/* Find all the natural loops in the function and save in LOOPS structure and
recalculate loop_depth information in basic block structures.
Return the number of natural loops found. */
*** flow_loops_find (struct loops *loops)
*** 422,430
by this block. A natural loop has a single entry
node (header) that dominates all the nodes in the
loop. It also has single back edge to the header
!from a latch node. */
if (latch != ENTRY_BLOCK_PTR
! dominated_by_p (CDI_DOMINATORS, latch, header))
{
/* Shared headers should be eliminated by now. */
SET_BIT (headers, header-index);
--- 458,470
by this block. A natural loop has a single entry
node (header) that dominates all the nodes in the
loop. It also has single back edge to the header
!from a latch node.
!If there is no regular path from the header to the
!latch do not consider this latch (not worth the
!problems). */
if (latch != ENTRY_BLOCK_PTR
! dominated_by_p (CDI_DOMINATORS, latch, header)
! path_without_edge_flags (header, latch, EDGE_COMPLEX))
{
/* Shared headers should be eliminated by now. */
SET_BIT (headers, header-index);
[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695 Richard Guenther rguenth at gcc dot gnu.org changed: What|Removed |Added CC||rakdver at gcc dot gnu.org Known to work|4.7.2 |4.8.0 Known to fail|4.8.0 |4.7.2 --- Comment #3 from Richard Guenther rguenth at gcc dot gnu.org 2012-06-19 14:12:46 UTC --- I think the bug is that we detect a loop just over abnormal goto edges (can be first seen in 031t.cddce1). Not sure if we do that on purpose ...
[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695 Richard Guenther rguenth at gcc dot gnu.org changed: What|Removed |Added Status|NEW |ASSIGNED AssignedTo|unassigned at gcc dot |rguenth at gcc dot gnu.org |gnu.org | --- Comment #2 from Richard Guenther rguenth at gcc dot gnu.org 2012-06-18 09:03:22 UTC --- Mine.
[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695 H.J. Lu hjl.tools at gmail dot com changed: What|Removed |Added Status|UNCONFIRMED |NEW Last reconfirmed||2012-06-16 CC||rguenth at gcc dot gnu.org Target Milestone|--- |4.8.0 Ever Confirmed|0 |1 --- Comment #1 from H.J. Lu hjl.tools at gmail dot com 2012-06-16 16:00:54 UTC --- This is caused by revision 185913: http://gcc.gnu.org/ml/gcc-cvs/2012-03/msg01244.html
