Date: Tue, 15 Sep 1998 21:27:00 +0000 (GMT) From: Terry Lambert <tlambert@primenet.com> To: eivind@yes.no (Eivind Eklund) Cc: tlambert@primenet.com, freebsd-hackers@FreeBSD.ORG Subject: Re: Unused functions Message-ID: <199809152127.OAA25996@usr09.primenet.com> In-Reply-To: <19980915120620.32623@follo.net> from "Eivind Eklund" at Sep 15, 98 12:06:20 pm
next in thread | previous in thread | raw e-mail | index | archive | help
> [... on dead code elimination at the final code level ...]
> > > It allows the programmer and the C scoping rules to
> > > work together to determine what should be associated and what need not.
> >
> > Instead of the compiler merely calculating hamiltonian cycles in
> > the dependency graph to do dead code elimination.
>
> I don't get what Hamilton cycles has to do with this. It looks like a
> simple mark-and-sweep GC to me, and I can't see how looking for
> Hamilton cycles are going to find.
You are looking for code without cycles through known referenced
symbols (if it has a cyle through a known referenced symbol, you
add it to the list of symbols). Since you already have the tree
in memory, with the edges correctly arranged, this is simpler than
trying to run Warshall's across the entrie symbol table from the
point of view of each node (and cheaper by an order of magnitude).
> Also, I can't think of a single case where I have written code that is
> likely to have even a single Hamilton cycle - I usually don't call
> main() from elsewhere in my program (and I certainly don't call
> _start). If you can involve Hamilton cycles at all here, it sounds
> like it must be on a subgraph. How?
Consider all top level "known referenced" symbols to be connected
by an edge.
> For those following: A Hamilton cycle touch every node in the graph
> exactly once, and forms a cycle.
More importantly, you can tell as DAG from a DCG. Symbols in a DCG,
where "known refrenced" forms an edge to the rest of the graph, means
that you have to reference increasingly fewer nodes as you go on.
Note: this rather dry argument still applies only to dead code
elimination in library archives in statically linked images).
Consider the user's symbols seperate from other symbols (you have
to do this because of Mike Smith's point about the user's symbols
vs. library symbols). By definition, these symbols are considered
"used". Then you go through the archives (libraries), and examine
these symbols. These are second order symbols.
You sort these onto either the "used" or the "unknown" list.
Then you look for a DCG using the "used" as a list, and traverse only
the "unknown" entries. If you find a cycle, you add the "unknown"
symbols in the cycle to the "used" list.
You repeat this process until, after a pass, no new symbols are added
to the "used" list. The remaining symbols on the "unknown" list now
represent "dead code"/"dead data".
Now you eliminate this code from inclusion in the relocation and
image write phase of the link. This works, even in the case of
static symbols, since statics must also be relocated, and therefore
will have a pseudo-symbol. All code/data between an unused symbol
or pseudo-symbol and a used one is dead, and may be eliminated.
Actually, you should talk to SEF about this; he's an old compiler
guru, and he worked on the Microsoft compiler for SCO. He has an
interesting "shaggy dog" story about emission of pseudo-symbols
for data on something like:
main()
{
char *str = "Hello World!" + 6;
puts( str - 6);
puts( "Goodbye ");
puts( str);
}
[ oversimplification; the exact case was the loss of "Hello " through
dead-data elimination for the "whoami" program, if I remember
correctly... Microsoft failed to emit a correct pseudo-symbol for
the start of the str data, emitting only _str for "World!"... ]
Terry Lambert
terry@lambert.org
---
Any opinions in this posting are my own and not those of my present
or previous employers.
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-hackers" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199809152127.OAA25996>