From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 8110 invoked by alias); 21 Mar 2006 05:09:28 -0000 Received: (qmail 7883 invoked by alias); 21 Mar 2006 05:09:24 -0000 Date: Tue, 21 Mar 2006 05:09:00 -0000 Message-ID: <20060321050924.7882.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-03/txt/msg02012.txt.bz2 List-Id: ------- Comment #6 from law at redhat dot com 2006-03-21 05:09 ------- Subject: Re: [4.1/4.2 Regression] missed jump threading after unroller On Sat, 2006-02-11 at 00:59 +0000, pinskia at gcc dot gnu dot org wrote: > > ------- Comment #5 from pinskia at gcc dot gnu dot org 2006-02-11 00:59 ------- > The problem with this one after Jeff's recent patches is that we have: > :; > D.1402_17 = 0; > if (D.1402_17 == 1) goto ; else goto ; > > :; > x_18 = 1; > > # x_19 = PHI <0(2), 0(3), x_18(4)>; > :; > > Which causes us not to be able to the jump threading as we do a CCP in VRP and > then we get: > : > if (v_8 < 0) goto ; else goto ; > > :; > D.1402_17 = 0; > goto (); > > # x_19 = PHI <0(2)>; > :; > u_20 = 1; > ivtmp.26_21 = 1; > ivtmp.26_3 = 1; > u_14 = 1; > x_13 = 0; > if (v_8 <= 0) goto ; else goto ; > > So we need to be able to do some CCP and some DCE before invoking VRP. As I mentioned earlier, the problem is inherent with non-iterating dominator optimizations -- namely that we can't guarantee that for block BB that we will visit all of BB's predecessors before visiting BB when BB is at a dominance frontier. The net result is that we may still be propagating values into a PHI node for a block which has already been visited. Those propagations may result in the PHI turning into a degenerate too late for the dominator optimizer to discover the degenerate PHI and record the appropriate equivalence for the LHS of the degenerate PHI. I had added support for a stripped down copy-prop to run after DOM to pick up these kind of optimization opportunities rooted at degenerate PHI nodes that were trivial copies. (previously we had been running the full-blown copy-prop pass). However, that code does not catch this case because our PHI looks like x_2 = PHI (0 (BB1), 0 (BB2)) ie, it's a constant initialization, not a PHI-copy. I had played with running a similarly stripped down CCP after DOM, but that's really expensive compile-time wise. I then experimented with speeding up the propagation engine. While I may have found a couple of micro-opts, I wasn't able to find anything which was going to give us a big enough improvement to make running a phi-only CCP a viable option from a compile-time standpoint. I then proceeded to implement a concept that had been floating around in the back of my mind. Namely a specialized PHI const/copy optimizer which used a dominator walk plus a worklist of statements/phis to revisit after the DOM walk (which allows us to detect secondary effects). It turns out this specialized PHI optimization pass is as effective as running copy-prop and CCP on PHI nodes after DOM. Better yet, it is a teeny tiny slowdown compared to just running the stripped down copyprop. ie, for an almost unmeasurable slowdown we can do both constant and copy propagation instead of just copy propagation. Net result is in this PR we're able to clean up the extraneous modulo operation and propagate its result as well. Note that the resulting code could be simplified even more, namely iterating VRP could allow simplification of a relational into an equality test. That's simply not going to happen. We'll have to live with less than 100% optimized code. Bootstrapped and regression tested on i686-pc-linux-gnu. ------- Comment #7 from law at redhat dot com 2006-03-21 05:09 ------- Created an attachment (id=11077) --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=11077&action=view) -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21829