From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 19332 invoked by alias); 23 Aug 2012 07:29:29 -0000 Received: (qmail 19321 invoked by uid 22791); 23 Aug 2012 07:29:27 -0000 X-SWARE-Spam-Status: No, hits=-4.3 required=5.0 tests=ALL_TRUSTED,AWL,BAYES_00,KHOP_THREADED X-Spam-Check-By: sourceware.org Received: from localhost (HELO gcc.gnu.org) (127.0.0.1) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 23 Aug 2012 07:29:07 +0000 From: "rguenther at suse dot de" 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 X-Bugzilla-Reason: CC X-Bugzilla-Type: changed X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: gcc X-Bugzilla-Component: middle-end X-Bugzilla-Keywords: ice-on-valid-code X-Bugzilla-Severity: normal X-Bugzilla-Who: rguenther at suse dot de X-Bugzilla-Status: ASSIGNED X-Bugzilla-Priority: P3 X-Bugzilla-Assigned-To: rguenth at gcc dot gnu.org X-Bugzilla-Target-Milestone: 4.8.0 X-Bugzilla-Changed-Fields: Message-ID: In-Reply-To: References: X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/ Auto-Submitted: auto-generated Content-Type: text/plain; charset="UTF-8" MIME-Version: 1.0 Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-bugs-owner@gcc.gnu.org X-SW-Source: 2012-08/txt/msg01586.txt.bz2 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53695 --- Comment #10 from 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 changed: > > What |Removed |Added > ---------------------------------------------------------------------------- > CC| |steven at gcc dot gnu.org > > --- Comment #6 from Steven Bosscher 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.