From: Andrew MacLeod <amacleod@redhat.com>
To: Zdenek Dvorak <rakdver@atrey.karlin.mff.cuni.cz>
Cc: Jeff Law <law@redhat.com>, Diego Novillo <dnovillo@redhat.com>,
gcc mailing list <gcc@gcc.gnu.org>
Subject: Re: [tree-ssa] Lazy updating of stmt operands
Date: Mon, 15 Dec 2003 20:55:00 -0000 [thread overview]
Message-ID: <1071521539.31157.1824.camel@p4> (raw)
In-Reply-To: <20031215191836.GA8653@atrey.karlin.mff.cuni.cz>
On Mon, 2003-12-15 at 14:18, Zdenek Dvorak wrote:
> 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.
However, point taken that we dont want to do any searching at all to
perform the update. That just means a little more memory required to
maintain the info.
> > 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.
Andrew
next prev parent reply other threads:[~2003-12-15 20:52 UTC|newest]
Thread overview: 43+ messages / expand[flat|nested] mbox.gz Atom feed top
2003-12-07 16:22 Zdenek Dvorak
2003-12-07 17:14 ` Diego Novillo
2003-12-07 17:28 ` Zdenek Dvorak
2003-12-07 17:36 ` Diego Novillo
2003-12-07 18:09 ` Zdenek Dvorak
2003-12-11 19:39 ` law
2003-12-07 22:20 ` Steven Bosscher
2003-12-09 14:30 ` Andrew MacLeod
2003-12-09 20:40 ` Zdenek Dvorak
2003-12-11 19:41 ` law
2003-12-11 19:38 ` law
2003-12-11 19:52 ` Zdenek Dvorak
2003-12-11 22:36 ` Zdenek Dvorak
2003-12-11 23:34 ` Andrew MacLeod
2003-12-15 19:10 ` Andrew MacLeod
2003-12-15 19:19 ` Zdenek Dvorak
2003-12-15 20:55 ` Andrew MacLeod [this message]
2003-12-15 21:06 ` Zdenek Dvorak
2003-12-15 21:39 ` Andrew MacLeod
2003-12-15 21:49 ` Zdenek Dvorak
2003-12-15 22:04 ` Andrew MacLeod
2003-12-15 22:39 ` law
2003-12-17 4:56 ` law
2003-12-16 23:32 ` Andrew MacLeod
2003-12-17 0:09 ` Zdenek Dvorak
2003-12-17 0:21 ` Andrew MacLeod
2003-12-17 3:28 ` law
2003-12-15 19:28 ` Diego Novillo
2003-12-11 22:31 Chris Lattner
2003-12-12 3:14 ` law
2003-12-12 3:58 ` Chris Lattner
2003-12-12 19:25 ` Andrew MacLeod
2003-12-12 19:42 ` Zdenek Dvorak
2003-12-12 19:45 ` Andrew MacLeod
2003-12-12 19:54 ` Chris Lattner
2003-12-12 19:55 ` Andrew MacLeod
2003-12-12 21:26 ` Diego Novillo
2003-12-12 19:57 ` Chris Lattner
2003-12-13 16:02 ` Andrew MacLeod
2003-12-14 3:39 ` Chris Lattner
2003-12-15 23:41 ` law
2003-12-16 6:02 ` Andrew MacLeod
2003-12-15 20:47 Chris Lattner
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1071521539.31157.1824.camel@p4 \
--to=amacleod@redhat.com \
--cc=dnovillo@redhat.com \
--cc=gcc@gcc.gnu.org \
--cc=law@redhat.com \
--cc=rakdver@atrey.karlin.mff.cuni.cz \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).