From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 14864 invoked by alias); 13 Dec 2003 13:46:04 -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 14848 invoked from network); 13 Dec 2003 13:46:03 -0000 Received: from unknown (HELO mx2.redhat.com) (66.187.237.31) by sources.redhat.com with SMTP; 13 Dec 2003 13:46:03 -0000 Received: from int-mx2.corp.redhat.com (int-mx2.corp.redhat.com [172.16.27.26]) by mx2.redhat.com (8.11.6/8.11.6) with ESMTP id hBDDPlA20962; Sat, 13 Dec 2003 08:25:47 -0500 Received: from potter.sfbay.redhat.com (potter.sfbay.redhat.com [172.16.27.15]) by int-mx2.corp.redhat.com (8.11.6/8.11.6) with ESMTP id hBDDjwb16661; Sat, 13 Dec 2003 08:45:58 -0500 Received: from p4 (vpn50-11.rdu.redhat.com [172.16.50.11]) by potter.sfbay.redhat.com (8.11.6/8.11.6) with ESMTP id hBDDjuO16149; Sat, 13 Dec 2003 05:45:56 -0800 Subject: Re: [tree-ssa] Lazy updating of stmt operands From: Andrew MacLeod To: Chris Lattner Cc: Jeff Law , Zdenek Dvorak , gcc mailing list In-Reply-To: References: Content-Type: text/plain Content-Transfer-Encoding: 7bit Date: Sat, 13 Dec 2003 16:02:00 -0000 Message-Id: <1071323157.3257.138.camel@p4> Mime-Version: 1.0 X-SW-Source: 2003-12/txt/msg00763.txt.bz2 On Fri, 2003-12-12 at 14:57, Chris Lattner wrote: > > > I really can't emphasize enough how important this is. For example, this > > > information allows an efficient implementation of the LLVM > > > Value::replaceAllUsesOf operation (which makes all users of a value use > > > something else, think replacing 'add 2, 4' with '6'). The presence of > > > this operation makes copy operations in the IR completely superfluous, > > > along with "copy-propagation" passes (which either effectively have to be > > > run between all transformations, or be built into all of them). This > > > simplifies transformations, makes code more maintainable, etc... > > > > Its not just maintainability that is at issue. Maintaining immediate > > uses is not difficult. Memory consumption rises dramatically when you > > have a lot ssa names and uses and maintain those links. It was a > > Significant memory win to only calculate immediate uses for the > > ssa_names we cared about in CCP as opposed to all ssa-names. > > How much memory consumption are we talking about here? In LLVM, each > instruction consumes space for itself (to hold the opcode, type, etc.), > and 4 words for each operand. The 4 words includes all use-def and def > use information. SSA can be a very light-weight representation. > Its not the SSA space thats the memory consumption problem. gcc is now unit at a time, so the entire program is read into memory as trees and held there. the tree-ssa branch also uses GIMPLE, which creates more trees. Then you add even a lightweight SSA and this simply magnifies any additional memory that is used. Once the machine starts swapping, its another order of magnitude on timing. So we are trying to watch memory very carefully. That plus we are still working within the existing tree data structures. I beleive our representation of SSA is quite lightweight. It only becomes less so when you try to add a bunch of stuff that isnt needed everywhere. > > We already have memory footprint problems, and maintaining def->use > > links all the time is going to aggravate that situation even more. If > > there are times when it is necessary, it ought not be hard to maintain > > that information within our current framework. I see no reason to have > > it present all the time when only some consumers need it... > > If you're trying to work around the problem with caches and recomputation > of information, I suspect that you are barking up the wrong tree. That > said, I don't know exactly what's going on in the tree-ssa world, so there > may be complicating factors. > The Cache isnt something we're trying to work around. Thats there to prevent us from having to muck around in trees looking for things which are operands. The stmt is in the form of trees, our "cache" is the equivilent of your instruction. It consists of the operands plus looking at the tree code(s) of the stmt. So we have 1 word for each operand. It points to the SSA_NAME in the stmt tree which represents that ssa version. As far as Im concerned, we're not working around anything. Everything works just fine. IF someone wants/needs the def->use inforation, it can be built today. What we dont have is the ability to keep it up to date for some period of time, simply because we've never needed it. If the time comes that we do need it, it is not hard to add. Andrew