* [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
2012-06-16 11:23 [Bug middle-end/53695] New: [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos zsojka at seznam dot cz
@ 2012-06-16 16:01 ` hjl.tools at gmail dot com
2012-06-18 9:03 ` rguenth at gcc dot gnu.org
` (23 subsequent siblings)
24 siblings, 0 replies; 26+ messages in thread
From: hjl.tools at gmail dot com @ 2012-06-16 16:01 UTC (permalink / raw)
To: gcc-bugs
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
^ permalink raw reply [flat|nested] 26+ messages in thread* [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
2012-06-16 11:23 [Bug middle-end/53695] New: [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos zsojka at seznam dot cz
2012-06-16 16:01 ` [Bug middle-end/53695] " hjl.tools at gmail dot com
@ 2012-06-18 9:03 ` rguenth at gcc dot gnu.org
2012-06-19 14:13 ` rguenth at gcc dot gnu.org
` (22 subsequent siblings)
24 siblings, 0 replies; 26+ messages in thread
From: rguenth at gcc dot gnu.org @ 2012-06-18 9:03 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 26+ messages in thread* [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
2012-06-16 11:23 [Bug middle-end/53695] New: [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos zsojka at seznam dot cz
2012-06-16 16:01 ` [Bug middle-end/53695] " hjl.tools at gmail dot com
2012-06-18 9:03 ` rguenth at gcc dot gnu.org
@ 2012-06-19 14:13 ` rguenth at gcc dot gnu.org
2012-06-27 10:33 ` rguenth at gcc dot gnu.org
` (21 subsequent siblings)
24 siblings, 0 replies; 26+ messages in thread
From: rguenth at gcc dot gnu.org @ 2012-06-19 14:13 UTC (permalink / raw)
To: gcc-bugs
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 ...
^ permalink raw reply [flat|nested] 26+ messages in thread* [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
2012-06-16 11:23 [Bug middle-end/53695] New: [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos zsojka at seznam dot cz
` (2 preceding siblings ...)
2012-06-19 14:13 ` rguenth at gcc dot gnu.org
@ 2012-06-27 10:33 ` rguenth at gcc dot gnu.org
2012-08-22 9:37 ` rguenth at gcc dot gnu.org
` (20 subsequent siblings)
24 siblings, 0 replies; 26+ messages in thread
From: rguenth at gcc dot gnu.org @ 2012-06-27 10:33 UTC (permalink / raw)
To: gcc-bugs
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);
^ permalink raw reply [flat|nested] 26+ messages in thread* [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
2012-06-16 11:23 [Bug middle-end/53695] New: [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos zsojka at seznam dot cz
` (3 preceding siblings ...)
2012-06-27 10:33 ` rguenth at gcc dot gnu.org
@ 2012-08-22 9:37 ` rguenth at gcc dot gnu.org
2012-08-22 19:26 ` steven at gcc dot gnu.org
` (19 subsequent siblings)
24 siblings, 0 replies; 26+ messages in thread
From: rguenth at gcc dot gnu.org @ 2012-08-22 9:37 UTC (permalink / raw)
To: gcc-bugs
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
^ permalink raw reply [flat|nested] 26+ messages in thread* [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
2012-06-16 11:23 [Bug middle-end/53695] New: [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos zsojka at seznam dot cz
` (4 preceding siblings ...)
2012-08-22 9:37 ` rguenth at gcc dot gnu.org
@ 2012-08-22 19:26 ` steven at gcc dot gnu.org
2012-08-22 20:14 ` steven at gcc dot gnu.org
` (18 subsequent siblings)
24 siblings, 0 replies; 26+ messages in thread
From: steven at gcc dot gnu.org @ 2012-08-22 19:26 UTC (permalink / raw)
To: gcc-bugs
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 3333, 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 10000, 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 3333, 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 3333, 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.
^ permalink raw reply [flat|nested] 26+ messages in thread* [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
2012-06-16 11:23 [Bug middle-end/53695] New: [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos zsojka at seznam dot cz
` (5 preceding siblings ...)
2012-08-22 19:26 ` steven at gcc dot gnu.org
@ 2012-08-22 20:14 ` steven at gcc dot gnu.org
2012-08-22 20:20 ` steven at gcc dot gnu.org
` (17 subsequent siblings)
24 siblings, 0 replies; 26+ messages in thread
From: steven at gcc dot gnu.org @ 2012-08-22 20:14 UTC (permalink / raw)
To: gcc-bugs
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 [10000],4 [10000],3 [6667] forward 2 [6667],3 [6667],4 [10000]
Duplicated 3 as 7 [6667]
covered now 66.7
Trace seed 6 [3333] forward 6 [3333]
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
^ permalink raw reply [flat|nested] 26+ messages in thread* [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
2012-06-16 11:23 [Bug middle-end/53695] New: [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos zsojka at seznam dot cz
` (6 preceding siblings ...)
2012-08-22 20:14 ` steven at gcc dot gnu.org
@ 2012-08-22 20:20 ` steven at gcc dot gnu.org
2012-08-22 21:33 ` steven at gcc dot gnu.org
` (16 subsequent siblings)
24 siblings, 0 replies; 26+ messages in thread
From: steven at gcc dot gnu.org @ 2012-08-22 20:20 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 26+ messages in thread* [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
2012-06-16 11:23 [Bug middle-end/53695] New: [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos zsojka at seznam dot cz
` (7 preceding siblings ...)
2012-08-22 20:20 ` steven at gcc dot gnu.org
@ 2012-08-22 21:33 ` steven at gcc dot gnu.org
2012-08-23 7:29 ` rguenther at suse dot de
` (15 subsequent siblings)
24 siblings, 0 replies; 26+ messages in thread
From: steven at gcc dot gnu.org @ 2012-08-22 21:33 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 26+ messages in thread* [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
2012-06-16 11:23 [Bug middle-end/53695] New: [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos zsojka at seznam dot cz
` (8 preceding siblings ...)
2012-08-22 21:33 ` steven at gcc dot gnu.org
@ 2012-08-23 7:29 ` rguenther at suse dot de
2012-08-23 7:37 ` rguenther at suse dot de
` (14 subsequent siblings)
24 siblings, 0 replies; 26+ messages in thread
From: rguenther at suse dot de @ 2012-08-23 7:29 UTC (permalink / raw)
To: gcc-bugs
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 3333, 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 10000, 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 3333, 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 3333, 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.
The patch is of couse a "big hammer" because it has a cost, but IMHO
it still makes sense.
^ permalink raw reply [flat|nested] 26+ messages in thread* [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
2012-06-16 11:23 [Bug middle-end/53695] New: [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos zsojka at seznam dot cz
` (9 preceding siblings ...)
2012-08-23 7:29 ` rguenther at suse dot de
@ 2012-08-23 7:37 ` rguenther at suse dot de
2012-08-23 7:56 ` stevenb.gcc at gmail dot com
` (13 subsequent siblings)
24 siblings, 0 replies; 26+ messages in thread
From: rguenther at suse dot de @ 2012-08-23 7:37 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 26+ messages in thread* [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
2012-06-16 11:23 [Bug middle-end/53695] New: [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos zsojka at seznam dot cz
` (10 preceding siblings ...)
2012-08-23 7:37 ` rguenther at suse dot de
@ 2012-08-23 7:56 ` stevenb.gcc at gmail dot com
2012-08-23 8:07 ` rguenther at suse dot de
` (12 subsequent siblings)
24 siblings, 0 replies; 26+ messages in thread
From: stevenb.gcc at gmail dot com @ 2012-08-23 7:56 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 26+ messages in thread* [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
2012-06-16 11:23 [Bug middle-end/53695] New: [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos zsojka at seznam dot cz
` (11 preceding siblings ...)
2012-08-23 7:56 ` stevenb.gcc at gmail dot com
@ 2012-08-23 8:07 ` rguenther at suse dot de
2012-08-23 8:10 ` rguenther at suse dot de
` (11 subsequent siblings)
24 siblings, 0 replies; 26+ messages in thread
From: rguenther at suse dot de @ 2012-08-23 8:07 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 26+ messages in thread* [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
2012-06-16 11:23 [Bug middle-end/53695] New: [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos zsojka at seznam dot cz
` (12 preceding siblings ...)
2012-08-23 8:07 ` rguenther at suse dot de
@ 2012-08-23 8:10 ` rguenther at suse dot de
2012-08-23 8:49 ` stevenb.gcc at gmail dot com
` (10 subsequent siblings)
24 siblings, 0 replies; 26+ messages in thread
From: rguenther at suse dot de @ 2012-08-23 8:10 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 26+ messages in thread* [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
2012-06-16 11:23 [Bug middle-end/53695] New: [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos zsojka at seznam dot cz
` (13 preceding siblings ...)
2012-08-23 8:10 ` rguenther at suse dot de
@ 2012-08-23 8:49 ` stevenb.gcc at gmail dot com
2012-08-23 8:53 ` steven at gcc dot gnu.org
` (9 subsequent siblings)
24 siblings, 0 replies; 26+ messages in thread
From: stevenb.gcc at gmail dot com @ 2012-08-23 8:49 UTC (permalink / raw)
To: gcc-bugs
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-bugzilla@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...
^ permalink raw reply [flat|nested] 26+ messages in thread* [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
2012-06-16 11:23 [Bug middle-end/53695] New: [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos zsojka at seznam dot cz
` (14 preceding siblings ...)
2012-08-23 8:49 ` stevenb.gcc at gmail dot com
@ 2012-08-23 8:53 ` steven at gcc dot gnu.org
2012-08-23 9:19 ` rguenther at suse dot de
` (8 subsequent siblings)
24 siblings, 0 replies; 26+ messages in thread
From: steven at gcc dot gnu.org @ 2012-08-23 8:53 UTC (permalink / raw)
To: gcc-bugs
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! :-)
^ permalink raw reply [flat|nested] 26+ messages in thread* [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
2012-06-16 11:23 [Bug middle-end/53695] New: [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos zsojka at seznam dot cz
` (15 preceding siblings ...)
2012-08-23 8:53 ` steven at gcc dot gnu.org
@ 2012-08-23 9:19 ` rguenther at suse dot de
2012-08-23 9:23 ` rguenther at suse dot de
` (7 subsequent siblings)
24 siblings, 0 replies; 26+ messages in thread
From: rguenther at suse dot de @ 2012-08-23 9:19 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 26+ messages in thread* [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
2012-06-16 11:23 [Bug middle-end/53695] New: [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos zsojka at seznam dot cz
` (16 preceding siblings ...)
2012-08-23 9:19 ` rguenther at suse dot de
@ 2012-08-23 9:23 ` rguenther at suse dot de
2012-08-23 9:44 ` steven at gcc dot gnu.org
` (6 subsequent siblings)
24 siblings, 0 replies; 26+ messages in thread
From: rguenther at suse dot de @ 2012-08-23 9:23 UTC (permalink / raw)
To: gcc-bugs
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?
^ permalink raw reply [flat|nested] 26+ messages in thread* [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
2012-06-16 11:23 [Bug middle-end/53695] New: [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos zsojka at seznam dot cz
` (17 preceding siblings ...)
2012-08-23 9:23 ` rguenther at suse dot de
@ 2012-08-23 9:44 ` steven at gcc dot gnu.org
2012-08-23 11:00 ` rguenther at suse dot de
` (5 subsequent siblings)
24 siblings, 0 replies; 26+ messages in thread
From: steven at gcc dot gnu.org @ 2012-08-23 9:44 UTC (permalink / raw)
To: gcc-bugs
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 }
^ permalink raw reply [flat|nested] 26+ messages in thread* [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
2012-06-16 11:23 [Bug middle-end/53695] New: [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos zsojka at seznam dot cz
` (18 preceding siblings ...)
2012-08-23 9:44 ` steven at gcc dot gnu.org
@ 2012-08-23 11:00 ` rguenther at suse dot de
2012-08-23 11:22 ` rguenther at suse dot de
` (4 subsequent siblings)
24 siblings, 0 replies; 26+ messages in thread
From: rguenther at suse dot de @ 2012-08-23 11:00 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 26+ messages in thread* [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
2012-06-16 11:23 [Bug middle-end/53695] New: [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos zsojka at seznam dot cz
` (19 preceding siblings ...)
2012-08-23 11:00 ` rguenther at suse dot de
@ 2012-08-23 11:22 ` rguenther at suse dot de
2012-09-19 13:31 ` rguenth at gcc dot gnu.org
` (3 subsequent siblings)
24 siblings, 0 replies; 26+ messages in thread
From: rguenther at suse dot de @ 2012-08-23 11:22 UTC (permalink / raw)
To: gcc-bugs
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;
^ permalink raw reply [flat|nested] 26+ messages in thread* [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
2012-06-16 11:23 [Bug middle-end/53695] New: [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos zsojka at seznam dot cz
` (20 preceding siblings ...)
2012-08-23 11:22 ` rguenther at suse dot de
@ 2012-09-19 13:31 ` rguenth at gcc dot gnu.org
2012-10-26 11:58 ` rguenth at gcc dot gnu.org
` (2 subsequent siblings)
24 siblings, 0 replies; 26+ messages in thread
From: rguenth at gcc dot gnu.org @ 2012-09-19 13:31 UTC (permalink / raw)
To: gcc-bugs
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
^ permalink raw reply [flat|nested] 26+ messages in thread* [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
2012-06-16 11:23 [Bug middle-end/53695] New: [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos zsojka at seznam dot cz
` (21 preceding siblings ...)
2012-09-19 13:31 ` rguenth at gcc dot gnu.org
@ 2012-10-26 11:58 ` rguenth at gcc dot gnu.org
2012-10-29 14:25 ` rguenth at gcc dot gnu.org
2012-10-29 14:33 ` rguenth at gcc dot gnu.org
24 siblings, 0 replies; 26+ messages in thread
From: rguenth at gcc dot gnu.org @ 2012-10-26 11:58 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 26+ messages in thread* [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
2012-06-16 11:23 [Bug middle-end/53695] New: [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos zsojka at seznam dot cz
` (22 preceding siblings ...)
2012-10-26 11:58 ` rguenth at gcc dot gnu.org
@ 2012-10-29 14:25 ` rguenth at gcc dot gnu.org
2012-10-29 14:33 ` rguenth at gcc dot gnu.org
24 siblings, 0 replies; 26+ messages in thread
From: rguenth at gcc dot gnu.org @ 2012-10-29 14:25 UTC (permalink / raw)
To: gcc-bugs
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=gcc&view=rev&rev=192943
Log:
2012-10-29 Richard Guenther <rguenther@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
^ permalink raw reply [flat|nested] 26+ messages in thread* [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos
2012-06-16 11:23 [Bug middle-end/53695] New: [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos zsojka at seznam dot cz
` (23 preceding siblings ...)
2012-10-29 14:25 ` rguenth at gcc dot gnu.org
@ 2012-10-29 14:33 ` rguenth at gcc dot gnu.org
24 siblings, 0 replies; 26+ messages in thread
From: rguenth at gcc dot gnu.org @ 2012-10-29 14:33 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 26+ messages in thread