From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 18853 invoked by alias); 15 May 2003 17:09:24 -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 18718 invoked from network); 15 May 2003 17:09:21 -0000 Received: from unknown (HELO piper.synopsys.com) (204.176.21.196) by sources.redhat.com with SMTP; 15 May 2003 17:09:21 -0000 Received: (from jbuck@localhost) by piper.synopsys.com (8.11.6/8.11.6) id h4FH9Em17326; Thu, 15 May 2003 10:09:14 -0700 Date: Thu, 15 May 2003 17:09:00 -0000 From: Joe Buck To: Diego Novillo Cc: "gcc@gcc.gnu.org" Subject: Re: [tree-ssa] copy propagation and the abstraction penalty Message-ID: <20030515100914.B17159@synopsys.com> References: <20030514154455.A12416@synopsys.com> <1053007822.4382.137.camel@frodo.toronto.redhat.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5.1i In-Reply-To: <1053007822.4382.137.camel@frodo.toronto.redhat.com>; from dnovillo@redhat.com on Thu, May 15, 2003 at 10:10:22AM -0400 X-SW-Source: 2003-05/txt/msg01529.txt.bz2 On Thu, May 15, 2003 at 10:10:22AM -0400, Diego Novillo wrote: > There's a few bits still missing, but we should be getting there. In > this particular testcase I see: > > * Structures. We only build enough SSA links to prove liveness. > Two alternatives to dealing with this is using ESSA from the > SSAPRE engine and/or rely on a scalarization pass. Since this is the absolutely most common defect in our current C++ compiler, it seems worth trying to tune optimization to solve it directly, rather than trying to solve a harder, more general problem. If copy propagation can store the content of individual structure fields, then it seems that you don't need the rest of scalarization. > * Aliasing. Our default type-based aliasing mechanism gets all > tangled up (it's really naive): I think that the aliasing problem can be finessed. Again, generalized copy propagation would appear to solve this without solving any aliasing problem: replace pointers to known addresses by the addresses. Even stupid aliasing, that kills everything on the first pointer write, still can win if this is done. Let me step through this to show how it might work. ;; Function complex addone(const complex&) (_Z6addoneRK7complex) complex addone(const complex&) (arg) { struct complex retval.12; struct complex ; struct complex * T.8; struct complex * T.9; struct complex & T.10; struct complex T.11; { T.8_2 = &; { double i; double r; struct complex * const this; this_3 = (struct complex * const)T.8_2; Here this_3 is & (copy prop). r_5 = 1.0e+0; i_6 = 0.0; { this->re = 1.0e+0; This is presumably this_3. Now we know that UVa150.re is 1.0e+0. (That is, we track fields of local structs, as part of copy propagation). this->im = 0.0; Now we know that Uva150.im is 0.0. We do need to care about aliasing, but that means that we might have invalidate the value of these fields if we get a write through a pointer that might alias UVa150. This program has no pointer writes at all, though. I think that even a very simple-minded approach that discards all stored structure field values on the first indirect write would still show huge gains, because these temporary structs are often live for an extremely short distance (they just pass information across an inlined call). } }; T.9_9 = &; T.10_10 = (struct complex &)T.9_9; T.10_10 is &. { struct complex & b; struct complex ; b_11 = T.10_10; b_11 is &. { struct complex * T.1; double T.2; double T.3; double T.4; double T.5; double T.6; double T.7; { T.1_13 = &; T.2_15 = arg->re; T.3_16 = b->re; T.3_16 is (&)->re, or UVa150.re, or 1.0. T.4_17 = T.2_15 + T.3_16; T.5_18 = arg->im; T.5_18 is (&)->im, or UVa150.im, or 1.0. After doing this substitution, UVa150 is dead, and we can kill it. T.6_19 = b->im; T.7_20 = T.5_18 + T.6_19; { double i; double r; struct complex * const this; this_21 = (struct complex * const)T.1_13; r_23 = T.4_17; i_24 = T.7_20; { this->re = T.4_17; this->im = T.7_20; } }; } }; retval.12_27 = }; T.11_28 = retval.12_27; return retval.12_27; } }