From: Chris Lattner <sabre@nondot.org>
To: Andrew MacLeod <amacleod@redhat.com>
Cc: Zdenek Dvorak <rakdver@atrey.karlin.mff.cuni.cz>,
Jeff Law <law@redhat.com>, gcc mailing list <gcc@gcc.gnu.org>
Subject: Re: [tree-ssa] Maintaining/representing def-use/use-def information
Date: Mon, 15 Dec 2003 20:26:00 -0000 [thread overview]
Message-ID: <Pine.LNX.4.44.0312151353030.26453-100000@nondot.org> (raw)
In-Reply-To: <1071516477.3353.1693.camel@p4>
> > That is my point. There is no reason to have an extra SSA_NAME memory
> > allocation at all. If SSA is properly integrated into the representation
> > (ie, not something tacked onto an existing representation designed for
> > something else), then the expression implicitly defines the computed
> > value.
> An SSA_NAME is a decl, just like a variable declaration.
> so in non ssa LAND, we have
> a = 10
>
> thats a tree:
> MODIFY_EXPR
> / \
> VAR_DECL CONST
> A 10
>
> in ssa land we have
>
> a_2 = 10
>
> MODIFY_EXPR
> / \
> SSA_NAME CONST
> / \ 10
> VAR_DECL 2
> A
>
> so the expression does implicitly define the computed value. Its really
> no different than variable except we can associate the version number
> with a var_decl.
What you are saying is that instead of _one_ memory allocation to
represent a logical operation, you are uisng 4 (VAR_DECL, SSA_NAME, "2",
MODIFY_EXPR). Even if some of these are shared, doesn't this make
traversing the representation really expensive and cache unfriendly. You
also didn't show how a variable is referenced as an operand.
When I said that the SSA form wasn't integrated as a first-class entity,
this is _exactly_ what I meant: your SSA form is added on top of the
existing trees. Contrast this with LLVM. Consider the expression: "X =
(1+2); Y = X+X;", which is following LLVM instructions:
%X = add int 1, 2
%Y = add int %X, %X
Ignoring types, which every value has, the following are the memory
objects we have to allocate and process:
CONST1 CONST2
\ /
ADD
| |
ADD
ie, there are _4_ memory allocation, ones for each instruction, and one
for the two constants being referenced. There are no intermediate objects
used to represent "SSA_NAME"s or variables being declared, etc. An
instruction which computes a value is directly pointed to by operands.
There is no need to go through an auxillary symbol table to traverse
def-use or use-def chains.
This is what I mean by integrating SSA as a first-class feature in your
representation. How would this be represented in tree-ssa?
> Its not much different than duplicating the var_decl for A and adding an
> integer field for the version number. We chose this way because there
> is a ton of variable specific information like type, etc etc that we
> dont need to duplicate, and it doesnt impact any non-ssa parts of the
> compiler. It also makes it trivial to look at a cariable and tell if its
> in SSA form or not.
I understand why you chose to use the existing tree representation as the
basis of tree-ssa, but you have to admit that it has some serious
overheads and costs. I am not at all convinced that you can eliminate all
of them, even if substantial effort is put towards slimming them down.
> > > > Adding capabilities like this at a late date will mean that a lot of code
> > > > will need to be rewritten.
> >
> > > I think virtually nothing will have to be rewritten to add this
> > > capability. I have to make a minor change to the way immediate uses is
> > > currently calculated/stored, but its pretty minor. And we'll have the
> > > capability to calculate/maintain def->use links without a lot of
> > > trouble.
> >
> > Ok, that makes sense. :)
>
> We just cant do everything up front. We implement additional
> features/requirements things as we need them, and attempt to keep the
> architecture well enough designed to let us add these things, hopefully,
> without much trouble. Its just not worth spending time on something that
> someone might need in the future.
Ok, sounds good. Also, you have a much better chance designing a _good_
interface if you have several use cases. Your approach makes sense.
-Chris
--
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/
next prev parent reply other threads:[~2003-12-15 20:04 UTC|newest]
Thread overview: 46+ messages / expand[flat|nested] mbox.gz Atom feed top
2003-12-11 22:31 [tree-ssa] Lazy updating of stmt operands 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 20:39 ` [tree-ssa] Maintaining/representing def-use/use-def information Chris Lattner
2003-12-13 13:46 ` Andrew MacLeod
2003-12-14 3:59 ` Chris Lattner
2003-12-15 17:17 ` Andrew MacLeod
2003-12-15 19:18 ` Chris Lattner
2003-12-15 19:43 ` Andrew MacLeod
2003-12-15 20:26 ` Chris Lattner [this message]
2003-12-15 20:29 ` Diego Novillo
2003-12-15 20:52 ` Andrew MacLeod
2003-12-15 21:01 ` Zdenek Dvorak
2003-12-15 21:09 ` Andrew MacLeod
2003-12-15 21:11 ` Zdenek Dvorak
2003-12-15 21:20 ` Diego Novillo
2003-12-15 21:23 ` Zdenek Dvorak
2003-12-15 21:31 ` Andrew MacLeod
2003-12-17 8:47 ` law
2003-12-15 21:03 ` Diego Novillo
2003-12-15 21:11 ` Andrew MacLeod
2003-12-15 21:11 ` Chris Lattner
2003-12-15 21:16 ` Zdenek Dvorak
2003-12-15 21:19 ` Chris Lattner
2003-12-15 21:38 ` Daniel Berlin
2003-12-15 22:08 ` Chris Lattner
2003-12-15 23:09 ` Daniel Berlin
2003-12-15 23:31 ` Chris Lattner
2003-12-15 23:46 ` Daniel Berlin
2003-12-15 21:32 ` Daniel Berlin
2003-12-15 21:31 ` Andrew MacLeod
2003-12-17 7:51 ` law
2003-12-15 20:04 ` Diego Novillo
2003-12-15 23:26 ` law
2003-12-15 23:32 ` Chris Lattner
2003-12-12 21:26 ` [tree-ssa] Lazy updating of stmt operands 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
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=Pine.LNX.4.44.0312151353030.26453-100000@nondot.org \
--to=sabre@nondot.org \
--cc=amacleod@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).