Jones N.D.Partial evaluation and automatic program generation.1999

Introduction 231

/* Computes mini_printf("n% = %d", v) for all v */ void mini_printf_fmt(int *value)

f

putchar('n'); putchar(' '); putchar('='); putchar(' '); printf("%d", value[0]);

g

The cost of run time interpretation of the format string is often named the interpretation overhead. By specialization the interpretation overhead is completely eliminated. Evidently, the specialized version will be faster than the general ver-

sion.

2

Automatic binding-time analysis of C is a major problem which we brie y consider in Section 11.6. The focus of this chapter, however, will mainly be on the specialization phase, so we henceforth simply assume for the most part that bindingtime annotations are present in the programs we consider. In Section 11.2 the specialization of statements and expressions is described. Function specialization is problematic due to side-e ects and global data structures | it is important that the order of side-e ects is preserved, and sharing of residual functions is complex due to `hidden' side-e ects. This is the subject of Section 11.3. Next, in Section 11.4 we address the treatment of data structures and in particular pointers. We describe specialization of structs to static elds, dynamic memory allocation via malloc(), and how the binding-time separation can be improved by the means of pointer information.

11.1.2The C language

The standard of C imposes only a few restrictions upon its users. We are solely interested in automatic methods, and clearly this restricts the kind of `nasty' features that can be allowed. For example, it is di cult to handle programs exploiting uninitialized pointers that the programmer happens to know will point to something sensible. Thus a certain `clean' programming style is required.

We reject programs using features such as casting void pointers to di erent types. The recurring problem is binding-time analysis, which must then be overly conservative and in the worst case assume that a pointer can point to any dynamic object in a program. Naturally, one cannot expect good results when this is the case. On the other hand, if the goal is to process programs written in a larger subset of C, this can be done by our methods, the risk being that the bene t from specialization may be limited.

232 Partial Evaluation for the C Language

In general, a C program can be seen as a set of modules: there are les with the main() function, functions for opening and reading les, functions implementing computation, etc. We propose to apply partial evaluation to the latter functions, and for simplicity we assume that all static input is through the parameters of a goal function. In practice, reading of input from les is convenient and possible, but it requires additional attention.2

11.2Specialization of control ow

The statements making up the body of a function can by simple transformations be brought into a form resembling the owchart language of Chapter 4. For example, a while loop can be transformed into L: if () . . . goto L. The abstract syntax of a mix language is de ned in Section 11.5; for now, though, we leave the convertion implicit. Suppose that all statements are consistently marked as being either static or dynamic.

11.2.1Polyvariant program-point specialization

Consider rst specialization of statements where the control ow is entirely static. This implies that test expressions can be evaluated and branches performed.

Example 11.2 The well-known function power()3 computes base to the n'th.

int power(int base, int n) f

int pow;

for (pow = 1; n; n--) pow *= base;

return pow;

g

Assume that power is to be specialized with respect to n. Then the for loop can be executed during the specialization since it solely depends on the static n. The local variable pow must be dynamic due to the assignment pow *= base, forcing the initialization pow = 1 to be suspended as well.

Let n be equal to 3 and suppose that power is symbolically executed on this input. The test in the for loop is determined by the static n, so the loop can be unrolled three times. In the body of the loop, the dynamic assignment to pow gives rise to generation of a residual statement, as shown below.

2For example, to avoid a stream being read repeatedly whereas normal execution only would read it once.

3See Kernighan and Ritchie, Chapter 1 [147].

Specialization of control ow 233

/* This program computes base to the 3'rd. */ int power_3(int base)

f

int pow; pow = 1; pow *= base; pow *= base; pow *= base; return pow;

g

2

This program can, of course, be further optimized via traditional optimizations such as folding and constant propagation, but this can be accomplished by a good optimizing C compiler. On the other hand, since C compilers lack binding-time information, it is unreasonable to expect a compiler to execute static statements. The example also illustrates the typical tradeo between speed and size. The size of the residual program grows with the size of the static input n, and for huge n specialization may be undesirable.

Consider now the processing of a dynamic control ow statement, e.g. an if where the test expression is dynamic. The branch cannot be determined at specialization time and hence both branches must be specialized with respect to the values of the static variables.

Example 11.3 The strcmp() function returns 0 if two strings are equal.

int strcmp(int *s, int *t) f

for (; *s == *t; s++, t++) if (*s == 'n0') return 0; return *s - *t;

g

The for loop can be considered as syntax for the equivalent:

L: if (*s == *t) f

if (*s == 'n0') return 0; s++; t++;

goto L;

g

else return *s - *t;

Assume that the string s is static ('ab') but t is dynamic. Then the if inevitably must be annotated dynamic, and thus both branches of it must be specialized just like a compile compiles both branches even though only one will be executed at run time. The inner if is completely static, but note that both return statements must be dynamic since the function is supposed to return at run time.

234 Partial Evaluation for the C Language

int strcmp_s(int *t) f

L_0: if ('a' == *t)

f t++; L_1: if ('b' == *t)

f t++; L_2: if ('n0' == *t) return 0; else return 'n0' - *t;

g

else return 'b' - *t;

g

else return 'a' - *t;

g

In this particular example, the specialization is nothing more than loop unrolling. In other cases some static computations could appear in the branches and thus

disappear.	2
In general, a dynamic if (e) S1 else S2	is specialized as follows. The ex-

pression e is reduced as far as possible using the values of the static variables. Then copies of the static values are made (one for each branch), and both S1 and S2 are specialized with respect to these. Finally a residual statement if (e0) S10 else S20 is generated. Notice the similarities with the specialization algorithm for theowchart language given in Chapter 4. An algorithm for C is given in Section 11.5.

11.2.2Managing a mutable memory

As described above, every time a specialization point is processed, a copy of the memory, or the store, has to be made. The presence of pointers complicates this process since these must be adjusted to re ect possibly new locations of the objects they originally pointed to, and cyclic data structures must be taken into account.

In order to implement sharing of specialization points, i.e. to detect that a certain program point already has been specialized with respect to particular values of static values, it must be possible to `compare' di erent copies of the store against each other [6]. We consider this again below.

11.3Function specialization

By function specialization we mean the generation of a function fs, specialized with respect to static data s. For example, in Section 11.1 the power() function was specialized to 3 yielding power 3(). In the previous section we considered specialization of the body of a function. In this section we address issues such as side-e ects, sharing, and specialization strategy. Due to the semantics of C this is considerably more involved than seen in the foregoing chapters.

foo(int *p)

Function specialization 235

11.3.1Function specialization, pointers, and sharing

Functions must naturally be specialized with respect to both static parameters and static global variables.4 Since the only way to refer to heap-allocated objects is via pointer variables, no special action needs to be taken. What, however, does it mean to specialize with respect to a pointer?

Suppose a function has a static formal parameter of pointer type, and is to be specialized due to a call foo(e) giving the residual function foo'(). The specialization must be with respect to both the address (of e) and the indirection, that is, the content of all the locations that p legally can point to when the actual parameter expression is e. For example, if e is a where a is a static array int a[10], then p can refer to a[0],. . . ,a[9].

Suppose another call of foo() in the program. If the call signatures of the two calls are equal, that is, the values of the static variables at the call are equal to those to which foo() was specialized, then seemingly foo'() can be shared. To decide this, the specialization time stores have to be compared. Notice that in general it can rst be determined at specialization time which locations that must be compared | consider for example the di erence between two calls foo(a) and foo(&x) | and thus information about the size of static objects must thus be present during the specialization. One way to achieve this is to maintain a table of the start and end addresses of all objects allocated at specialization time.

11.3.2Functions and non-local side-e ects

Functional languages are characterized by referential transparency, meaning that two calls to a function with the same arguments always yield the same result. As is well known, this property is not valid in C due to global variables and nonlocal side-e ects.

Example 11.4 Assume a global integer stack	int stack[STACK		SIZE] and an
integer stack pointer sp.
int main(void)	void push(int v)
f	f
int x;	stack[++sp] = v;
push(e1);	g
push(e2);	int pop(void)
x = pop() + pop();	f
push(x);	return stack[sp--];
g	g

In many situations the content of the stack is dynamic while the stack pointer is static. Suppose we want to specialize the push() and pop() functions.

4Much of the discussion in this subsection carries over to specialization of control ow.

push 0()

the static value of sp has

236 Partial Evaluation for the C Language

First observe that function specialization must be depthrst in order to preserve the order of side-e ects. This means that a function must be specialized before the statements following the call. In this example, when the dynamic call to push(e1) is met, push() must be specialized before the remaining statements in main(). Thus sp will be incremented properly before the next push() is considered. Since the value of sp now di ers from the rst call, push() must be specialized again.

However, at the third call, it seems that the rst residual version of push() can simply be shared since sp possesses the same value as originally. By doing so, though, the static value of sp will not be incremented, which is semantically wrong. To remedy this, it is necessary to update the value of static variables after sharing a residual function.

int main(void)		void push_0(int v)
f int x;		f stack[4] = v; g
/*	sp = 3 */
push_0(e10 );		void push_1(int v)
push_1(e0 );		f stack[5] = v; g
	2
x = pop_0() + pop_1();
push_0(x)		int pop_0(void)
/*	sp = 4 */	f return stack[5]; g
g

int pop_1(void)

f return stack[4]; g

At specialization time, after the last call to been updated to 4.

In practice the calls to push() and pop() would, of course, be unfolded. Furthermore, as described in the next section, the array representing the stack could

be split.

2

Without a mechanism for updating the static values of variables after sharing a call, every dynamic call must either cause the function to be specialized again (or at least the static part to be re-executed) with consequent risk of non-termination; or all non-local side-e ects must be suspended.

11.3.3Non-local static side-e ects under dynamic control

In the previous subsection problems with static (non-local) side-e ects in residual functions were illustrated. However, the side-e ects can even be under dynamic control, as shown below. The scenario is that in a function, a non-local variable is assigned static values under a dynamic if. At specialization time, the if cannot be executed and hence both the branches are specialized. This means that eventually both the static assignments will be evaluated.

Function specialization 237

Example 11.5 Suppose global is classi ed as static and the function foo() below is specialized.

int global;
int main(. . . )	int foo(. . . )
f	f
global = 0;	if ( dyn) global = 1;
foo(. . . );	else global = -1;
S	return dyn;
g	g

where dyn represents a dynamic expression. Observe that even though global is assigned static values in each branch of the dynamic if in foo(), the concrete

value is unknown (at specialization time) after the call.

2

This is called non-local static side-e ects under dynamic control. The problem is that after processing a residual call, i.e. specializing a function, seemingly static variables becomes dynamic. When specializing a sequence of statements

if (e) S1 else S2; S,

where e is dynamic, the problem is solved by unfolding the remaining statements S into the branches, but this solution is not immediately applicable here since the if is hidden in another function. Either the power of the specializer must be strengthened to handle such situations, or non-local variables under dynamic control must be classi ed dynamic.

Suspension of side-e ects under dynamic control

The immediate solution is to suspend all (non-local) side-e ects under dynamic control. Thus specialization can proceed as normal after a call, since possibly side- e ected static variables can at most assume one value after a call. The reader should be aware that heap-allocated data structures are in the same category as global variables, so this strategy may have a major impact on the results gained by specialization.

A slightly improved strategy is to change the binding time of variables under dynamic control from static to dynamic by insertion of so-called explicators [85], i.e. assignments global = 1 . This is, however, in con ict with the monovariant division of variables into static and dynamic, and we shall not pursue this idea any further.

Unfolding of functions with side-e ects under dynamic control

Suppose that all calls to a function containing static side-e ects under dynamic control are unfolded. Then we can unfold the statements after the call into the now revealed dynamic if, and specialize these with respect to the di erent values of side-e ected variables.

238 Partial Evaluation for the C Language

Example 11.6 Reconsider Example 11.5. By unfolding foo() into main(), the following residual program could be generated:

int main(. . . ) f

if ( dyn0)	/* global = 1 */	S0
else	/* global = -1 */	S00

g

where an attached prime indicates `specialized'. Notice in particular that the remaining statements S have been specialized with respect to global being 1 and

-1, respectively.

2

The unfolding strategy fails when the candidate function is recursive and the recursion is under dynamic control, and even when the recursion is statically controlled, termination problems can occur. Moreover, unrestricted unfolding may lead to code size explosion since no sharing of functions occurs.

Online function unfolding is addressed in Section 11.5.

Handling static side-e ects under dynamic control by specialization

Observe that if specialization terminates, a static variable can assume only nitely many values. A tempting idea is to specialize the statements following a function call with respect to the nitely many di erent values, but without unfolding the function. For instance, in the running example, we would specialize S with respect to global being 1 and -1. We then need some machinery in the residual program which, at run time, can lead the control ow to the right specialized version of S. Notice that the decision to execute a particular version is determined by return statements in the called function, leading to a simple idea: to introduce the C equivalent of a continuation variable, to be set to a unique value before each return.

Example 11.7 Following is an example of a residual program using a continuation variable.

int endconf; /* Continuation variable */

int main(. . . )		int foo_0(. . . )
f		f
foo_0(. . . );		if ( dyn0)
switch (endconf) f		endconf = 1; return dyn0;
case 1: /*	global = 1 */	else
S0; break;		endconf = 2; return dyn0;
case 2: /*	global = -1 */	g
S00; break;

g

g

Data structures and their binding-time separation 239

In the specialized version of foo(), the continuation variable endconf is set to a unique value before every return. After the call, a branch is made to the code corresponding to the path through foo 0() actually taken. Note that this allows

sharing of residual functions.

2

More generally, the idea is to record the values of non-local static variables immediately after every return. For instance, in the example we would record global to be 1 at return statement 1, and -1 at return statement 2.

Then, after processing a call, we specialize the remaining statements to the stores obtained by updating the store active before the call with respect to the accumulated end-con gurations. For example, global would be updated to 1, since this is the value it has when the called function returns. In the residual program, we generate an assignment to a continuation variable before every return statement, and after the call, we generate code to branch on the continuation variable to the various specialized versions.

The end-con guration can also be used to update the static store after sharing a residual function (cf. Section 11.3.1). We just have to omit the function specialization.

Similar to the unfolding strategy, this method fails to handle recursive functions. The reason is that in order to specialize a function call, the called function must have been completely processed. Moreover, an extra call overhead is introduced in the residual program. In most cases, though, the overhead will be compensated for by other savings. More problematic is the copying of possibly huge static data structures which are side-e ected under dynamic control. Pragmatic reasons may require such structures to be suspended.

11.4Data structures and their binding-time separation

In this section we consider specialization of data structures and in particular pointers. Pointers are central to C: they occur in connection with arrays, the address operator &, and dynamically allocated memory can only be referred to by means of pointers.

The main problem is the binding-time separation. Consider for example a program which dynamically allocates a list p = malloc(sizeof(struct Node)) where Node is a struct with a `next' pointer eld. If all pointers assigned to the next eld are static, then we can allocate the list at specialization time and use it. However, suppose an assignment p->next = dynamic-value occurs later in the program. This implies that the structure of the list becomes dynamic and thus all the allocation calls must be suspended. Without a global analysis this cannot be determined when looking at the malloc() call in isolation. However, a bindingtime analysis can, prior to the specialization, mark all those allocation calls that can be evaluated and those which must be suspended.

240Partial Evaluation for the C Language

11.4.1Partially static arrays

Consider a program containing an array a[n+1] whose elements are dynamic, but where all of a's subscript expressions are static. It is then, under some restrictions, possible to split a into separate variables a 0,. . . ,a n. The objective is to eliminate subscript calculations and an indirection, enable register allocation, etc.

Example 11.8 Consider the following code fragment implementing addition of two numbers using a stack.

stack[++sp] = 2; stack[++sp] = 3; sp--;

stack[sp] = stack[sp+1] + stack[sp];

It is often the case that the content of the stack is dynamic but the stack pointer itself is static. This means that the stack can be split into separate variables as illustrated below.

stack_13	= 2;
stack_14	= 3;
stack_13	= stack_14 + stack_13;

During partial evaluation, all the operations on the stack pointer have been performed and the stack has been split into separate variables.5

2

It is crucial that every index expression e in a[e] in the program is static, otherwise a[e] cannot be replaced by a 3 (assuming that e evaluates to 3). This is not su cient, though. Assume that there is a dynamic pointer p. Unless it can be established that p newer will point to a, the array cannot be split since an expression *p cannot be replaced by the proper variable, say, a 7.

Next, recall that arrays are passed by reference in C. Suppose that a is passed to a residual function f and it is split. If, in the residual program, it is passed as f(a 1,. . .,a n), there is a change in the passing semantics from call-by-reference to call-by-value which in general is unsound.6 Thus, it seems reasonable to prohibit splitting of arrays which are passed to functions.

The decision whether or not to split an array depends on global information, and is thus hard to make online during the specialization. The binding-time analysis can, however, reveal the needed information and mark those arrays that can be split safely.

5Furthermore, applying constant folding in another postphase would give 3 + 2 = 5.

6Passing pointers to the variables are not desirable either, since it increases the call overhead.