Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!ucsd!sdd.hp.com!decwrl!bacchus.pa.dec.com!granite.pa.dec.com!mwm From: mwm@raven.pa.dec.com (Mike (Real Amigas have keyboard garages) Meyer) Newsgroups: comp.lang.misc Subject: Re: The Universal Language Message-ID: Date: 14 Aug 90 00:13:13 GMT References: <1990Aug13.213113.3743@craycos.com> <1990Aug13.224738.5469@usenet.ins.cwru.edu> Sender: news@wrl.dec.com (News) Organization: Missionaria Phonibalonica Lines: 68 In-Reply-To: eric@cwphysbb.PHYS.CWRU.Edu's message of 13 Aug 90 22:47:38 GMT In article <1990Aug13.224738.5469@usenet.ins.cwru.edu> eric@cwphysbb.PHYS.CWRU.Edu (Eric M. Rains) writes: In article <1990Aug13.213113.3743@craycos.com> pmk@craycos.com (Peter Klausler) says: >Matthew Austern: >> Can you really imagine a C compiler/linker that can prove that a >> program has no recursive calls, and use a simpler calling convention >> for such programs?) > >Uh, yes, I can. I use one daily. Why is this so unimaginable? Because it's completely impossible, that's why. Imagine the following piece of C code: [code deleted] Remember, theory is closer to practice in theory than in practice. Yes, you can't solve the halting problem. From which one can conclude that it's impossible to prove that all programs that have no recursive calls have no recursive calls. But you don't need to do that to be able to take advantage of quicker calling conventions for non-recursive functions. All you need to be able to do is determine that some specific function is non-recursive. That's easy for many functions, and mistakenly tagging a non-recursive function as recursive just costs a little extra run time. No problem, so long as you're consistent about it. [more code deleted] How can I link to this other module? The calling conventions will be different (assuming the module with non_recursive_func has no recursion)... Now you're dealing with implementation details. First, a minor nit - you're assuming the worst case - that caller and callee have to change. Depending on the architechture, this may not be true. You may only have to change the callee, which makes things trivial. It's having to change the call that creates problems. Second, you can safely mix calling conventions in a single program. All you have to do is insure that everyone agrees on how any given function is called. Therefore, you can apply this optimization on a per-function basis. How well you can apply it is another problem. Some brainstorming, based on C: Two entry points: Generate your non-recursive routine with the "fast" calling convention. Callers from the same compilation unit use that entry. You also generate a wrapper that uses the "recursive" calling convention, and then calls the "fast" function, just for "recursive" external calls and calls through function pointers. Your smart linker discards the wrapper if it's never used. Link-time call generation: Tag all non-recursive functions as such in the object file. When the linker fixes the addresses being called, it adds code to use the appropriate call convention. Actually, extending that another step, it may be possible to upgrade possibly recursive functions to non-recursive post-compile. There are already compilers that do post-compile, pre-link optimization of this nature, so it's not impossible.