From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 21906 invoked by alias); 15 Dec 2003 21:03:03 -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 21899 invoked from network); 15 Dec 2003 21:03:02 -0000 Received: from unknown (HELO atrey.karlin.mff.cuni.cz) (195.113.31.123) by sources.redhat.com with SMTP; 15 Dec 2003 21:03:02 -0000 Received: by atrey.karlin.mff.cuni.cz (Postfix, from userid 29025) id BD86D4C029E; Mon, 15 Dec 2003 22:03:01 +0100 (CET) Date: Mon, 15 Dec 2003 21:06:00 -0000 From: Zdenek Dvorak To: Andrew MacLeod Cc: Jeff Law , Diego Novillo , gcc mailing list Subject: Re: [tree-ssa] Lazy updating of stmt operands Message-ID: <20031215210301.GB24610@atrey.karlin.mff.cuni.cz> References: <1070818186.7334.30.camel@frodo.toronto.redhat.com> <200312111936.hBBJabGj024859@speedy.slc.redhat.com> <20031211223056.GA20061@atrey.karlin.mff.cuni.cz> <1071515090.3354.1681.camel@p4> <20031215191836.GA8653@atrey.karlin.mff.cuni.cz> <1071521539.31157.1824.camel@p4> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1071521539.31157.1824.camel@p4> User-Agent: Mutt/1.5.4i X-SW-Source: 2003-12/txt/msg00817.txt.bz2 Hello, > > > > > >> > tree-dfa.c:compute_immediate_uses() > > > > > >> > > > > > >> Which needs to pass through every single statement in the program. Not > > > > > >> really terribly efficient. > > > > > >> > > > > > >*shrug*, it's used by SSA-CCP. Since def-use edges are only needed by > > > > > >some passes, I don't think it would be worth our while trying to > > > > > >maintain them in get_stmt_operands. > > > > > > > here is the patch. It increases time for compiling preprocessed gcc > > > > sources from 3m43.734s to 3m47.967s. It does not use interface of > > > > immediate uses, since that is not well suited for updating; instead it > > > > just keeps lists of uses for each ssa name. The old interface and ccp > > > > that uses it are not changed by the patch, so in fact the cost would > > > > be a bit smaller. > > > > > > Why isn't it well suited for updating? > > > > suppose a statement is changed. To update the immediate uses of this > > statement, you would need to go to the defining statement for each > > variable, find yourself in a (possibly very long) list of uses and > > make the update. This would be a disaster for the performance. > > > > And how is that different than what you have to update? Oh, I see you > are actually maintaining a double linked list for each use or def. It > would require less memory to keep integer index that this use is in the > defining stmt's use-list. Thats only one word instead of two for a > prev/next pointer. and is quite a bit harder to manipulate (don't ask me why, just try to think for a while how would you implement this; if you still feel it is easy then, persuade me :-) ). Yes, it could be also done this way, but I don't find the saving so important to make the things more complicated than necessary. > > > The information is in the > > > defining stmt's annotation, so given any SSA variable, you can get to > > > the immediate uses by looking at the annotation for SSA_NAME_DEF_STMT. > > > It needs a marginal extention to deal with the fact that there can be > > > multiple defs/vdefs on one stmt, but we need to do that to handle > > > virtual defs anyway. I would prefer to keep this information right with > > > the stmt rather than in a table on the side. > > > > Immediate use is not a property of the statement, but the property of > > the ssa name; so it should be in the SSA_NAME, as my patch does, > > not in the statement annotations. > > Point of view. the SSA_NAME is defined by its stmt, so the two are > inextricably linked. The SSA_NAME exists so we have a DECL node. > > The immediate uses information is all stmt based data flow information, > so it should be in the stmt, IMO. If you change a stmt, you change the > uses information. We never "change" an SSA_NAME, we just change its > defining stmt. Its six of one, and a half dozen of the other I guess, I > just think its more constant to keep it all the dataflow info in stmt > annotaions, rather than half in ssa_names and half in stmts. > > In any case, I'll make immediate_uses my next task (unless there is > something more pressing?). I'll think about whether putting it into > SSA_NAMES makes sense or not. > > I presume you are going to have a need in the loop infrastructure code > to maintain it up to date? Presuming so, I can make it so that its be > updated, if its present. > > In order to move forward, I also presume you need a way to ask whether a > specific SSA_NAME has immediate_uses infomation available for it so you > can decide whether to merge blocks or not right? > > something like > bool immediate_uses_avail_p (tree ssa_name) > or > bool immediate_uses_avail_p (tree stmt) > > Presumably the latter, but both are easy to provide. ??? I don't really quite get you. Either the information should be available for every statement or not at all. Having something in the middle is just confusing. Zdenek