public inbox for gcc-bugs@sourceware.org help / color / mirror / Atom feed
From: "rguenther at suse dot de" <gcc-bugzilla@gcc.gnu.org> To: gcc-bugs@gcc.gnu.org Subject: [Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos Date: Thu, 23 Aug 2012 07:29:00 -0000 [thread overview] Message-ID: <bug-53695-4-KfVzu51Wdb@http.gcc.gnu.org/bugzilla/> (raw) In-Reply-To: <bug-53695-4@http.gcc.gnu.org/bugzilla/> 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.
next prev parent reply other threads:[~2012-08-23 7:29 UTC|newest] Thread overview: 26+ messages / expand[flat|nested] mbox.gz Atom feed top 2012-06-16 11:23 [Bug middle-end/53695] New: " 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 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 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 [this message] 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 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 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 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 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
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=bug-53695-4-KfVzu51Wdb@http.gcc.gnu.org/bugzilla/ \ --to=gcc-bugzilla@gcc.gnu.org \ --cc=gcc-bugs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).