From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 19824 invoked by alias); 9 Feb 2006 03:20:01 -0000 Received: (qmail 19754 invoked by uid 48); 9 Feb 2006 03:19:59 -0000 Date: Thu, 09 Feb 2006 03:20:00 -0000 Message-ID: <20060209031959.19753.qmail@sourceware.org> X-Bugzilla-Reason: CC References: Subject: [Bug tree-optimization/21829] [4.1/4.2 Regression] missed jump threading after unroller In-Reply-To: Reply-To: gcc-bugzilla@gcc.gnu.org To: gcc-bugs@gcc.gnu.org From: "law at redhat dot com" Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-bugs-owner@gcc.gnu.org X-SW-Source: 2006-02/txt/msg00881.txt.bz2 List-Id: ------- Comment #4 from law at redhat dot com 2006-02-09 03:19 ------- I'll note this really isn't a jump threading issue. This is a fundamental weakness in a dominator based optimizer vs a truly global optimizer. What we've got is a block which looks something like this: # u_18 = PHI ; :; D.1528_10 = u_18 % 2; if (D.1528_10 == 1) goto ; else goto ; Note carefully that this block is at a dominance frontier (thus the PHI node). At a dominance frontier, a dominator walk does _not_ guarantee that the CFG parents are visited before the node itself. ie, we may visit this block before its CFG parents. That is in fact precisely what happens. Thus we do not discover that u_13 and u_26 both have the value 1 until after we have processed this block. Possible solutions: 1. Iterating DOM. I don't want to do that. 2. Run CCP before DOM. It's something I've pondered, mostly because I want to remove constant propagation from DOM. Compile-time issues worry me. 3. Simple constant/copy propagation in the renaming phase. I've always been a fan of this to avoid clutter in the IL, but I've been overruled on this as a design decision. 4. Somehow arrange to sort the et-tree dominance information so that we visit immediate descendants of a CFG node which are dominated by the node before visiting more distant CFG descendants. This could be horribly ugly. 5. Somehow get really really smart in the block duplication code and arrange for it to propagate constants. I've pondered this, but I don't think it's really that feasible both from a design and implementation standpoint. 6. Post-dom cleanup phase using worklists seeded by degenerate PHI nodes to identify statements that can be simplified as a result of discovery of the degenerate PHI. [Would replace the mini-copyprop pass we do after DOM. ] I suspect #2 or #6 are the most likely long term solutions. jeff -- law at redhat dot com changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |law at redhat dot com http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21829