problems/risks ...

[kenny at m.cs.uiuc.edu]

Several people post stuff about the cost of function activation in C.

This is a very real problem, and one that I have yet to see a C
compiler address convincingly.  As it turns out, there are some
(fairly...) simple ways to improve the situation.  A major one is the
concept of `activation record merging,' where a function's activation
record is merged with that of its caller.  The idea is due to
Barry Wolman, who at one point worked for Honeywell's Cambridge
Information Systems Laboratory and implemented the suggestion in the
Multics PL-1 compiler.

The idea works only for what PL-1 calls `internal procedures;' these
are equivalent to `static' functions in C.  The reason is that
external functions have to activated with a fully general activation
mechanism, as the compiler has no control over the callers.

For a compilation unit, the compiler constructs the call graph of all
the functions.  It then attempts to merge activation records.  The
local variables (and parameters) of any function g may be merged with
those of another function f if:
	- f is active whenever g is.
	- for any activation of g, there is a unique, identifiable,
	  activation of f, and moreover, at any time there is only one
	  activation of g that corresponds to that activation of f.
	  (This last condition rules out, for instance, recursion).
	- &g is never taken.  (This rules out the pathology of g's
	  being activated by a signal, among other things.)

As it turns out, these conditions are exactly equivalent to an
interval partition on the call graph (This last conclusion is Wolman's
fundamental insight).  The algorithm for activation record merging can
be expressed as:

	- Augment the call graph with a dummy node E that calls all
	  external functions and functions whose address is taken.
	- Use the Cocke-Allen interval partition to identify a set of
	  intervals that partition the call graph.

	  (An `interval' is a set I of nodes with the properties that:
	  - there is a node h in I, called the *head* of I, which is
	    contained in every path from outside I to within I.
	  - I is connected.
	  - all cycles within I contain h.

Only the interval heads need activation records; all other functions
in the interval can store their local data in the activation record of
the interval head.  This typically reduces the cost of a static
function activation to about three machine instructions -- those that
are actually needed for entry and exit -- saving all the stack and
frame manipulations.

Any C compiler wizards want to take a shot at implementing this trick
for a C compiler?

| /         o            Kevin Kenny   KE9TV                     (217) 333-5821
|<  /) |  | | |/\        Department of Computer Science           o  ,    o  ,
| \ X_  \/  | | |        University of Illinois                 40 07 N 88 13 W
kenny at cs.uiuc.edu        1304 W. Springfield Ave.       
uunet!uiucdcs!kenny      Urbana, IL 61820                    AD ASTRA PER ARDUA
k-kenny at uiuc.edu
kenny%cs at uiucvmd.bitnet