From owner-freebsd-hackers Tue Sep 15 14:27:30 1998 Return-Path: Received: (from majordom@localhost) by hub.freebsd.org (8.8.8/8.8.8) id OAA08643 for freebsd-hackers-outgoing; Tue, 15 Sep 1998 14:27:30 -0700 (PDT) (envelope-from owner-freebsd-hackers@FreeBSD.ORG) Received: from smtp01.primenet.com (smtp01.primenet.com [206.165.6.131]) by hub.freebsd.org (8.8.8/8.8.8) with ESMTP id OAA08636 for ; Tue, 15 Sep 1998 14:27:27 -0700 (PDT) (envelope-from tlambert@usr09.primenet.com) Received: (from daemon@localhost) by smtp01.primenet.com (8.8.8/8.8.8) id OAA02512; Tue, 15 Sep 1998 14:27:09 -0700 (MST) Received: from usr09.primenet.com(206.165.6.209) via SMTP by smtp01.primenet.com, id smtpd002486; Tue Sep 15 14:27:04 1998 Received: (from tlambert@localhost) by usr09.primenet.com (8.8.5/8.8.5) id OAA25996; Tue, 15 Sep 1998 14:27:00 -0700 (MST) From: Terry Lambert Message-Id: <199809152127.OAA25996@usr09.primenet.com> Subject: Re: Unused functions To: eivind@yes.no (Eivind Eklund) Date: Tue, 15 Sep 1998 21:27:00 +0000 (GMT) Cc: tlambert@primenet.com, freebsd-hackers@FreeBSD.ORG In-Reply-To: <19980915120620.32623@follo.net> from "Eivind Eklund" at Sep 15, 98 12:06:20 pm X-Mailer: ELM [version 2.4 PL25] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: owner-freebsd-hackers@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG > [... 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