From owner-freebsd-hackers Wed Sep 16 01:03:38 1998 Return-Path: Received: (from majordom@localhost) by hub.freebsd.org (8.8.8/8.8.8) id BAA26258 for freebsd-hackers-outgoing; Wed, 16 Sep 1998 01:03:38 -0700 (PDT) (envelope-from owner-freebsd-hackers@FreeBSD.ORG) Received: from ns1.yes.no (ns1.yes.no [195.119.24.10]) by hub.freebsd.org (8.8.8/8.8.8) with ESMTP id BAA26250 for ; Wed, 16 Sep 1998 01:03:34 -0700 (PDT) (envelope-from eivind@bitbox.follo.net) Received: from bitbox.follo.net (bitbox.follo.net [195.204.143.218]) by ns1.yes.no (8.9.1a/8.9.1) with ESMTP id KAA25076; Wed, 16 Sep 1998 10:03:13 +0200 (CEST) Received: (from eivind@localhost) by bitbox.follo.net (8.8.8/8.8.6) id KAA27161; Wed, 16 Sep 1998 10:03:12 +0200 (MET DST) Message-ID: <19980916100311.62440@follo.net> Date: Wed, 16 Sep 1998 10:03:11 +0200 From: Eivind Eklund To: Terry Lambert Cc: freebsd-hackers@FreeBSD.ORG Subject: Re: Unused functions References: <19980915120620.32623@follo.net> <199809152127.OAA25996@usr09.primenet.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Mailer: Mutt 0.89.1i In-Reply-To: <199809152127.OAA25996@usr09.primenet.com>; from Terry Lambert on Tue, Sep 15, 1998 at 09:27:00PM +0000 Sender: owner-freebsd-hackers@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG On Tue, Sep 15, 1998 at 09:27:00PM +0000, Terry Lambert wrote: > > [... 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). Hmmm. I can't see any reason why you would want to do a Floyd-Warshall - that calculate the connectivity of the entire graph, which is really producing a lot of data you don't need. I can see two ways of doing this that seem useful. Both of them require (well, prefer) a bit of used/unused for each symbol (partial pseudo-code follows below). (1) Recursive mark'n'sweep void Symbol_MarkAllChildren(struct Symbol *pSymbol) { int iChild; if (!pSymbol->isUsed) { pSymbol->isUsed = 1; for (iChild = 0; iChild < pSymbol->nChildren; iChild++) Symbol_MarkAllChildren(pSymbol->aChildren[iChild]); } } Clear_isUsed_in_all_symbols(); for (pSymbol over each symbol in the initially used set) { Symbol_MarkAllChildren(pSymbol); } /* Symbols marked with 'isUsed' are needed - the rest can be discarded */ (2) Non-recursive mark'n'sweep void Symbol_MarkChildren(struct Symbol *pSymbol) { int iChild; for (iChild = 0; iChild < pSymbol->nChildren; iChild++) { if (!pSymbol->aChildren[iChild]->isUsed) { pSymbol->aChildren[iChild]->isUsed = 1; Symbol_TransferToTempUsedList(pSymbol->aChildren[iChild]); } } } Clear_isUsed_in_all_symbols(); for (pSymbol over each symbol in the initially used set) { Symbol_MarkChildren(pSymbol); Symbol_TransferToFinalUsedList(pSymbol); } do { for (pSymbol over each symbol in the TempUsedList) { if (pSymbol->isUsed) { Symbol_MarkChildren(pSymbol); Symbol_TransferToFinalUsedList(pSymbol); } } } while(!List_isEmpty(TempUsedList)); /* Symbols marked isUsed are needed - the rest can be discarded. The symbols to be used are in the 'FinalUsedList', while the ones that are to be discarded are left in the inital pool */ Both algorithm 1 and 2 are o(N) and O(N) in the number of edges connecting the set of used symbols. The only case you can avoid examining all of these edges is if all symbols are included in the final used set; then you could do a cutoff. I don't think it would be worthwhile, though. The algorithms are sort-of equal - algorithm 1 just use the stack for storing examination order, while algorithm 2 does the same thing using three lists, giving a slightly different order for the marking (basically a depth-first vs a breadth-first walk). > > 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. Connected to _what_ 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. [...] > 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. Why is this easier/faster than the trivial algorithms I present above? And where does hamilton cycles (as opposed to just cycles in the graph) enter into this? I can sort of get a picture of using cycles to separate used/unused symbols, but I can't see any direct advantages to it, and I can't see Hamiltonian cycles in there at all. What am I missing here? (I'm interested due to sometimes needing this type of algorithms, and if something else is more effective than the techniques outlined above - well, then I want that :-) > Actually, you should talk to SEF about this; he's an old compiler > guru, and he worked on the Microsoft compiler for SCO. SEF, this is your call. Speak up. Eivind. To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-hackers" in the body of the message