From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 3638 invoked by alias); 22 Jul 2002 01:04:49 -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 3625 invoked from network); 22 Jul 2002 01:04:43 -0000 Received: from unknown (HELO executor.cambridge.redhat.com) (195.224.55.237) by sources.redhat.com with SMTP; 22 Jul 2002 01:04:43 -0000 Received: from prospero.cambridge.redhat.com (dell-paw-2.cambridge.redhat.com [195.224.55.226]) by executor.cambridge.redhat.com (Postfix) with ESMTP id 52424ABB1B; Mon, 22 Jul 2002 02:04:42 +0100 (BST) Received: by prospero.cambridge.redhat.com (Postfix, from userid 4046) id DE64CF83C1; Mon, 22 Jul 2002 02:01:10 +0100 (BST) To: Mark Mitchell Cc: Richard Henderson , Per Bothner , Diego Novillo , "gcc@gcc.gnu.org" , Jason Merrill Subject: Re: Language-independent functions-as-trees representation References: <68260000.1027297038@warlock.codesourcery.com> From: Jason Merrill In-Reply-To: <68260000.1027297038@warlock.codesourcery.com> (Mark Mitchell's message of "Sun, 21 Jul 2002 17:17:18 -0700") Date: Mon, 22 Jul 2002 00:13:00 -0000 Message-ID: User-Agent: Gnus/5.090007 (Oort Gnus v0.07) Emacs/21.1 (i686-pc-linux-gnu) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-SW-Source: 2002-07/txt/msg00994.txt.bz2 >>>>> "Mark" == Mark Mitchell writes: >>> I was implicitly (sorry!) in SSA form. >> >> I remain unenlightened. Can you give an example of where such sharing >> would be useful? > You mean, I assume, other than the obvious memory savings. (In practice, > those savings can be rather substantial, and since we are trying to > avoid making compile-time any worse than it already is, something that > substantially reduces memory use may be worthwhile for that reason if > for no other.) Yep. > Consider that you want to do value-numbering to find places where you > compute the same value multiple times. [snip] Sure, any time you need to compare things it's faster if you can use pointer comparison. I was actually hoping for a small testcase, so we could talk about the tradeoffs. > However, with sharing, you must do work as you build the structure so that > you make sure that you really are sharing. But that is not so hard; you > just keep tables of the things built from nodes you already have and check > to see if the node you are building uses the same operation to combine > the arguments as the one you already have. The tricky part, as I mentioned before, is maintaining proper semantics when simplifying shared trees, or indeed when making any modifications. Sharing makes copying and comparison fast, but makes modification slow. Simplification generally involves the recursive replacement of expressions with temporary variables. If the expressions are shared, this will change semantics unless you somehow arrange to unshare them on modification, which could imply an arbitrary amount of backtracking. If I have a+b+c+d+e+f+g and I want to replace a+b with a temp, I have to make a new copy of the whole expression everywhere it appears, or suddenly all instances will use the same temp, which is wrong if 'a' changes in the interim. Or are you suggesting that we start sharing trees after simplification? Given that we only do GC between functions, I don't think that would provide any memory savings. And I still don't see how this relates to the statement/expression distinction. Jason