🚀 go-pugleaf

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.

	<mike
--
I know the world is flat.				Mike Meyer
Don't try tell me that it's round.			mwm@relay.pa.dec.com
I know the world stands still.				decwrl!mwm
Don't try to make it turn around.