Partial evaluation is program transformation that automates a program specialization process. Tempo is a partial evaluator for C programs. It has been applied in various domains such as operating systems and networking, computer graphics, scientific computation, software engineering and domain specific languages. A first workshop on Tempo has been organized in March 1998. Tempo is now being distributed. Its documentation is available on line, as well as tutorial slides.

An Overview of Tempo

Tempo is a partial evaluator for C programs. It is being developed in the Compose project at IRISA / INRIA - LABRI (France).

Tempo is an off-line specializer; it is divided into two phases: analysis and specialization.

The input to the analysis phase consists of a program and a description of which inputs will be known during specialization and which will be unknown. Based on this knowledge, dependency analyses propagate information about known and unknown values throughout the code and produce an annotated program, indicating how each program construct should be transformed during specialization. Because C is an imperative language including pointers, the analysis phase performs alias and side-effect analyses in addition to binding-time analyses. The accuracy of these analyses is targeted towards keeping track of known values across procedures, data structures, and pointers.

Following the analysis phase, the specialization phase generates a specialized program based on the annotated program and the values of the known inputs. Tempo can specialize programs at compile time (i.e., source-to-source tranformation) as well as run time (i.e., run-time binary code generation).

For more details, please consider reading some of our papers, most of which are available at the following URL: papers.

Program Analysis

As a first step, the user provides a program and specifies what arguments (including global variables) are static. For example, the user provides the following code for a miniprintf function, and specifies in this way that the first argument is static whereas the second is dynamic: miniprintf(S,D).

miniprintf(char fmt[], int val[])
{
  int i = 0;
  while( *fmt != '\0' ) {
    if( *fmt != '%' )
       putchar(*fmt);
    else
      switch(*++fmt) {
        case 'd' : putint(val[i++]); break;             
        case '%' : putchar('%');     break;
        default  : prterror(*fmt);   break;
      }
    fmt++;
  }
}

From this Tempo produces a program file with analysis annotations. These annotations can be visualized using colors that highlight the propagation of the known/unknown information throughout the program.

/*  LEGEND:  STATIC  DYNAMIC
 */
miniprintf(char fmt[], int val[])
{
  int i = 0;
  while( *fmt != '\0' ) {
    if( *fmt != '%' )
       putchar(*fmt);
    else
      switch(*++fmt) {
        case 'd' : putint(val[i++]); break;              
        case '%' : putchar('%');     break;
        default  : prterror(*fmt);   break;
      }
    fmt++;
  }
}

The blue color (bold face for black and white display) represent static constructions, i.e. values that can be computed at specialization time. The red color (standard font for black and white display) is for dynamic expressions, whose value cannot be precomputed knowing only the static arguments. Basically, everything in blue (bold) will disappear after specialization; only red (standard font) parts will remain.

The visualization of the analysis is very important for the user to assess the amount of specialization in the code. Furthermore, the analysis speeds up the specialization process (as opposed to on-line partial evaluators). The analysis is inter-procedural and takes into account pointer aliases and side-effects.

Compile-Time Specialization

When the user is satisfied with the analysis (i.e., what the user expects to specialize indeed appears as static), actual specialization values must be provided. For example, giving "" as the actual specialization value for the fmt argument of the miniprintf() function yields the following specialized code.

miniprintf_1(int val[])
{
  putchar( '<'    );
  putint ( val[0] );
  putchar( ','    );
  putint ( val[1] );
  putchar( '>'    );
}

Many specializations can be made, sharing the same analysis. Only different specialization values have to be provided.

Runtime Specialization

Tempo can also perform runtime specialization, using optimized binary code templates. A dedicated runtime specializer is generated from the analysis of the program. In the case of the miniprintf function, Tempo generates a runtime specializer rts_miniprintf_1() which can be used as in the following example.

/*
 * Some dynamic execution context for variable 'format'
 */
spec_printf = rts_miniprintf_1(format);
...
(*spec_printf)(val1);   /*  miniprintf(format,val1) */
(*spec_printf)(val2);   /*  miniprintf(format,val2) */

The function rts_miniprintf_1() is a dedicated runtime specializer. It returns a pointer to the specialized function. Several specialized versions can also be generated and used at the same time.

---

Applications of Tempo

Tempo has been successfully applied in various domains, yielding substantial speedups.

• Operating system and networking:
  • Sun RPC, Chorus IPC, BSD packet filter, Unix signals, active networks,
• Computer graphics (various filtering algorithms),
• Scientific computation (trajectory, FFT, math libraries),
• Software architectures and mechanisms:
  • Domain specific languages (GAL, PLAN-P),
  • Selective broadcast (implicit invocation),
  • Pattern matching,
  • Interpreters,
  • Software layers,
  • Generic libraries.

 

Besides C, Tempo is currently being used as a back-end for specializing Java programs using Harissa, a JavaVM-to-C compiler. Fortran and C++ programs have also been specialized using translators to C.

---

Projects Related to Tempo

Cyclone

Cyclone is a mobile code system being developed as part of the SwitchWare active-network project at the University of Pennsylvania. Cyclone uses two ideas to make mobile code safe as well as fast: run-time code generation and proof-carrying code. Cyclone relies on Tempo's analysis front-end (i.e. the binding-time analysis) and on TAL/T, an extension of the TAL typed assembly language.

---

Workshop

A workshop (actually closer to a ``winter school'') on Tempo has been organized at IRISA, March 16-18, 1998. The aim of this workshop was to present a three-day tutorial on Tempo and its applications to real size programs. We had 24 participants, coming from universities as well as industries. We believe it was a large success.

Depending on request, if the distribution of Tempo is a success, we might organize another workshop later. It would less be like a ``winter school'' but rather like a real workshop with users presenting applications and open discussions about possible improvements. It would be preceded by an optional one-day tutorial for people not knowing partial evaluation or Tempo.

---

Distribution

The Tempo specializer has been made publicly available under a licence in April 1998. At of March 99, it was being used by about thirty people around the world. The binary version of Tempo has just (July 2000) been made available without any restrictions, and we expect a full unrestricted source release under GPL to follow soon.

Getting access to Tempo no longer requires signing a license agreement. Tempo is simply available via anonymous FTP, as described below. In any case, we would very much like to hear from you if you are an active Tempo user. If you are, please also let us know if and for what purpose you are using Tempo, by sending an email to This e-mail address is being protected from spambots. You need JavaScript enabled to view it . We will by default add you to our tempo talk mailing list This e-mail address is being protected from spambots. You need JavaScript enabled to view it , where future Tempo releases will be announced, and Tempo users can discuss practical problems using Tempo.

Tempo can be downloaded :

• Here is a Tempo release that have been made publicly available: i386 Linux
• Most recent Tempo binary distribution for i386 Linux (tested on RedHat 6.1).

(Please remember to send an email to This e-mail address is being protected from spambots. You need JavaScript enabled to view it to let us know who you are and why you are using Tempo. Remember to explicitly indicate if you are not interested in joining the This e-mail address is being protected from spambots. You need JavaScript enabled to view it mailing list.)

In case of any problem with getting or installing the distribution, get in touch with us: This e-mail address is being protected from spambots. You need JavaScript enabled to view it

---

References

Here are general papers about Tempo and its architecture.

[CHL+98]

Tempo: Specializing Systems Applications and Beyond C. Consel, L. Hornof, J. Lawall, R. Marlet, G. Muller, J. Noyé, S. Thibault, N. Volanschi. To appear in ACM Computing Surveys, Symposium on Partial Evaluation, 1998.

[CMVM97]

Adaptabilité et évaluation partielle : Tempo, un spécialiseur pour le langage  C. C. Consel, G. Muller, N. Volanschi, R Marlet. Apr 1997. (In French.)