From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 11774 invoked by alias); 13 Dec 2004 22:56:06 -0000 Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org Received: (qmail 11690 invoked from network); 13 Dec 2004 22:56:00 -0000 Received: from unknown (HELO mx1.redhat.com) (66.187.233.31) by sourceware.org with SMTP; 13 Dec 2004 22:56:00 -0000 Received: from int-mx1.corp.redhat.com (int-mx1.corp.redhat.com [172.16.52.254]) by mx1.redhat.com (8.12.11/8.12.11) with ESMTP id iBDMtxYD019913; Mon, 13 Dec 2004 17:55:59 -0500 Received: from vpn50-67.rdu.redhat.com (vpn50-67.rdu.redhat.com [172.16.50.67]) by int-mx1.corp.redhat.com (8.11.6/8.11.6) with ESMTP id iBDMtwr30983; Mon, 13 Dec 2004 17:55:58 -0500 Subject: Re: Good news about increased jump threading from my PHI merge patch From: Jeffrey A Law Reply-To: law@redhat.com To: Kazu Hirata Cc: gcc@gcc.gnu.org, stevenb@suse.de, dvorakz@suse.cz In-Reply-To: <20041213.125724.34765950.kazu@cs.umass.edu> References: <20041211.022458.119878301.kazu@cs.umass.edu> <1102955877.14666.94.camel@localhost.localdomain> <20041213.125724.34765950.kazu@cs.umass.edu> Content-Type: text/plain Organization: Red Hat, Inc Date: Mon, 13 Dec 2004 22:56:00 -0000 Message-Id: <1102978556.14666.147.camel@localhost.localdomain> Mime-Version: 1.0 Content-Transfer-Encoding: 7bit X-SW-Source: 2004-12/txt/msg00473.txt.bz2 On Mon, 2004-12-13 at 12:57 -0500, Kazu Hirata wrote: > Hi Jeff, > > > Thanks. It's still on my list of things to evaluate for 4.0, mostly > > because of its potential to help compile-times on some of our > > problematical cases without introducing lots of regressions elsewhere. > > If we are just merging PHI nodes and not constant-propagating PHI > nodes (like killing casts), I get about 1% speed up on some test > cases. (For more accurate number, I have to retest.) > > What I am doing is really the same as Zdenek's thread_jumps rewrite, > which you recently approved. The only difference is that I am trying > to remove forwarder blocks with PHI nodes. Zdenek's version tries to > remove those without. Right. It seems like a pretty natural extension to Zdenek's code. > But do note, though, that my pass helps if it is run once or twice, > but if it's part of cleanup_tree_cfg, the compiler measurably slows > down because cleanup_tree_cfg is run so many times. Sigh. That is something on the long term todo list, but I haven't really figured out where/how to start cutting down those calls. > I think my pass > basically requires DCE. We clean up CFG before entering SSA, so we > shouldn't have any PHI merge opportunity unless some dead code between > two PHI nodes are removed. Which almost makes me wonder if removing forwarder blocks is better off as its own pass. We would schedule it to run after the DCE/DSE. We would also call it from cleanup_tree_cfg if and only if we were able to determine the result of a COND_EXPR_COND or SWITCH_COND. > Here is a quick advertisement. :-) Let me mention that I can quickly > determine if I can merge a forwarder block A (and its PHI nodes) into > basic block B most of the time. The only condition I need is: > > if (!dominated_by_p (CDI_DOMINATORS, B, A)) > > because if A does not dominate B, then the only valid place where any > values produced in A can be used is PHI arguments on edge A->B. > Otherwise, we would have a use that is not dominated by its def. In > other words, we don't need to compute immediate uses. > > The reason why I said "most of the time" above is that sometimes A > dominates B even if B has PHI nodes (and thus multiple incoming > edges). This case applies to B being a loop header. I don't know how > aggressive we want to be in this case because we are effectively > undoing create_preheader. Presumably we've already eliminate degenerate PHIs by this point. I see. > > > You mentioned that we can't handle large PHI nodes. Can you comment > > more on that -- that would be my largest individual concern right now. > > The only thing that's technically blocking my PHI merge is PHI-OPT. > IIRC, PHI-OPT looks for a basic block with a single PHI node with > exactly two arguments like so: Oh. That code. I thought you meant there was some time-complexity problem you needed to be solved with large PHI arguments. It would seem to me that the phi-opt code would just make your changes more effective, but the phi-opt code shouldn't be a prerequisite for your code to merge phis. jeff