Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!zaphod.mps.ohio-state.edu!ncar!boulder!pikes!aspen.craycos.com!pmk
From: pmk@craycos.com (Peter Klausler)
Newsgroups: comp.lang.misc
Subject: Re: The Universal Language
Message-ID: <1990Aug14.134001.4255@craycos.com>
Date: 14 Aug 90 13:40:01 GMT
Organization: Cray Computer Corporation
Lines: 41

In <1990Aug13.224738.5469@usenet.ins.cwru.edu> eric@cwphysbb.PHYS.CWRU.Edu (Eric M. Rains)
quite correctly points out that whether a function is recursive is *in general*
indecidable:

>>me:
>>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:
>	[deleted]
>P.S.  Besides; in a language like C, the problem of determining whether a
>program performs recursion is equivalent to the halting problem...

However, on real programs, a compiler and/or linker *can* do an effective job
detecting the impossibility of recursion. Briefly, the technique is:

	- Determine the basic call graph; for each function f, compute the set
	  CALLS (f) of functions it invokes
	- Compute the transitive closure of CALLS(f) for each function f
	- Assume recursion for a function f if f is in the transitive closure
	  of CALLS(f)

It's not quite this simple in practise, for one must deal with signal handlers
and functions called indirectly. But this, too, is not "completely impossible";
good, approximate, conservative solutions can be computed and used to speed
up your program.

The transitive closure of the call graph is also useful for problems of
temporary storage allocation -- a set of functions mutually excluded from all
their CALLS sets can all be assigned to the same set of temporary registers.
Finding these sets of functions is nontrivial, but again, approximate methods
are effective.

Real-world compiler work often involves approximate methods; if they err on
the conservative side and are effective on meaningful programs (read: customer
benchmarks), they win.