Tempo Specializer - User's Manual

Running Tempo

The user interacts with the Tempo Specializer system through an interactive top level that encapsulates all functionalities. It is actually a Standard ML top level (Tempo is mainly built on top of SML/NJ) where the Tempo functionalities have been pre-loaded.

To run the Tempo system, invoke the shell command tempo. You should see something that looks like this (the output of the system is in bold face, roman is for what you type):

mingus% tempo
TEMPO Version 1.191, 03/24/98,
  Copyright (c) IRISA/INRIA-Universite de Rennes
val it = () : unit
-

The "-" sign is the prompt character of this SML top level.

To exit the Tempo system, just type ^D, i.e. control-D, i.e. end-of-file character.

Running the Analysis

Before specializing a program, Tempo must first analyze it. This not only prepares the specialization process (it makes it more efficient) but also lets you assess the degree of specialization before actually providing specialization value.

Starting from compulsory files file.c and file.config.sml (the file.actx.c file is optional), the analyses produce as the final result a file.at file. By default, it also produces color files that show the intermediate results of the analyses (see Visualization.)

The SML command that runs the whole analysis phase is an. Alternatively, you may use the tempo SML command (not the tempo shell-level command) to run sub-phases individually or up to a certain phase. E.g.,

- an "power";
Starting from /home/jake/spec/power.c
Generating Suif file
Generating Suif tree
Generating abstract syntax tree
Eliminating gotos
Analyzing aliases
iterating analysis
Eliminating function pointers
Analyzing side effects
Generating MONO binding time information
Generating MONO evaluation time information (phase 1)
Generating MONO evaluation time information (phase 2)
Generating flattened program (phase 1 - Return sensitivity)
Generating flattened program (phase 2 - S&D)
Generating action tree
Produced file : power.at
val it = true : bool

Note that if the program to specialize does not lie in the directory where the tempo shell-level command was run, you have to specify the working directory explicitly (see Specifying the Program to Specialize below).

See also:

Building a Compile-Time Specializer

When the ".at" action file has been generated and assessed, you can move on to building a compile-time specializer, using the top-level cs command. The result is split into two files: .ctspec.C and .ev.c. E.g.,

- cs "power";
Starting from /home/jake/spec/power.at
Generating specializer file
Produced file : power.ctspec.C
val it = true : bool

An additional .sctx.h is also produced, to be used in the next phase, i.e. actual specialization.

See also:

Running a Compile-Time Specializer

The last step is the generation of the source of a specialized program, given actual values for the static parameters of the entry point. For this, you must provide a .sctx.c file, that expresses parameters' initialization as C code, and run the sp command.

- sp "power";
Starting from /home/jake/spec/power.ctspec.C
Generating specializer
gcc   -c -I/usr/local/lib/tempo/bin/../ctcg
  /home/jake/spec/power.ev.c
  -o /home/jake/spec/SunOS-5/power.ev.o
gcc   -c -I/usr/local/lib/tempo/bin/../ctcg
  /home/jake/spec/power.ctspec.C
  -o /home/jake/spec/SunOS-5/power.ctspec.o
gcc   -c /home/jake/spec/power.sctx.c
  -o /home/jake/spec/SunOS-5/power.sctx.o
gcc    -L/usr/local/lib/tempo/bin/../ctcg/SunOS-5
  /home/jake/spec/SunOS-5/power.ev.o
  /home/jake/spec/SunOS-5/power.ctspec.o
  /home/jake/spec/SunOS-5/power.sctx.o
  -lctcg -lbsdmalloc
  -o /home/jake/spec/SunOS-5/power.ctspec 
Specializing
TEMPO specializer: version 1.18, 98/03/03, Copyright Irisa
Postprocessing
Translating abstract syntax into C text
Produced file : power.cts.c
val it = true : bool

The result of the specialization may be found in the generated .cts.c file. It is up to you to install it in your original application. Make sure you call the specialized entry point when appropriate, i.e. when the specialization hypothesis (actual values of static parameters) are valid.

See also:

Building a Run-Time Specializer

Starting from the ".at" action file after the analysis has been performed, you may also generate a run-time specializer. There is nothing like an .sctx.c file to provide at this stage as the static parameters will be given at run time, when calling the specializer.

In other to build the run-time specializer, run the rs command.

- rs "power";
Starting from /home/jake/spec/power.at
Generating binary run-time specializer
gcc -O0   -c /home/jake/spec/power.temp.c
  -o /home/jake/spec/SunOS-5/power.temp.o
/usr/local/lib/tempo/bin/../rtcg/tcc/SunOS-5/tcc
  /home/jake/spec/power.temp
  /home/jake/spec/SunOS-5/power.temp
tcc: ret in template temp_5 offset 0x0010
gcc -O0   -c  -DSUNOS5 /home/jake/spec/power.rtspec.c
  -o /home/jake/spec/SunOS-5/power.rtspec.o
ld -r -o /home/jake/spec/SunOS-5/power.rts.o
  /home/jake/spec/SunOS-5/power.rtspec.o
  /home/jake/spec/SunOS-5/power.temp.o
  /usr/local/lib/tempo/bin/../rtcg/rts/SunOS-5/functions.o
  /usr/local/lib/tempo/bin/../rtcg/rts/SunOS-5/flushcopy.o
Produced file : power.rts.o
val it = true : bool

The result of the specialization may be found in the generated .rts.o file, that is generated in a directory named after the architecture and system of the current machine (see variable arch_dep_dir). A .rts.h file is also generated in the working directory; it contains the signature of the run-time specialization function.


It is up to you to install the run-time specializer in your original application, including the management of run-time specialized functions: when to specialize, caches for already specialized functions, etc. Make sure you call the run-time specialized entry points when appropriate, i.e. when the specialization hypothesis (actual values of static parameters) are valid.

See also:

SML Top Level

The Tempo Specializer top level provides a standard SML top-level interaction. You may type any SML code, i.e. definitions as well as expressions to evaluate, separated by semicolons.

- 1+2;
val it = 3 : int 
- "Te" ^ substring("compose",2,3);
val it = "Tempo" : string
- val foo = ["bar","gee"];
val foo = ["bar","gee"] : string list
- (hd foo, tl foo, fact 6);
val it = ("bar",["gee"]) : string * string list
- hd [];
uncaught exception Hd
- fun fact n = if n=0 then 1 else n*fact(n-1);
val fact = fn : int -> int
- fact 6;
val it = 720 : int

Using SML Variables

In particular, from this top level the user may consult or set Tempo configuration variables. Most of those variables are reference variables, i.e. pointers to a value. This can be seen from the type: it ends with "ref". E.g.

- explicit_cts_bufsize;
val it = ref NONE : int option ref
- max_decls_size;
val it = ref 100 : int ref
- max_decls_size := 3 * (!max_decls_size);
val it = () : unit
- max_decls_size;
val it = ref 300 : int ref

Note the use of:

!variable
to return the value pointed by a existing reference variable, i.e. to dereference it.
variable := value
to assign a value to an existing reference variable, i.e. to overwrite its previous value.
val variable = value
to define a top-level variable. (This is not needed unless having very complex interactions with Tempo.)

Using SML Commands

The user may also run Tempo commands, e.g.

- cd "/home/jake/spec";
val it = "/home/jake/spec" : string
- cs "power";
Starting from /home/jake/spec/power.at
Generating specializer file
Produced file : power.ctspec.C
val it = true : bool

Note that all of the SML commands provided by Tempo are curried i.e. arguments are provided separated by spaces. For example, the SML-level tempo command (not the tempo shell-level command) is used as follows:

- tempo "power" "alias" "bta";
Starting from /home/jake/spec/power.alias.as
Eliminating function pointers
Analyzing side effects
Generating MONO binding time information
Produced file : power.bta.as
val it = true : bool

If you forget an argument to this command, you will not get a type error; you will be returned a partially instantiated closure without any action being performed, e.g.

- tempo "alias" "bta";
val it = fn : string -> bool

However, if you provide the arguments as a tuple (separated by commas and surrounded by parentheses), you do get a type error:

- tempo("power","alias","bta");
std_in:26.1-26.29 Error: operator and operand don't agree
(tycon mismatch)
  operator domain: string
  operand:         string * string * string
  in expression:
    tempo ("power","alias","bta")

Using SML Files

Besides the user's interaction at the SML top level, there are two SML files that are used in Tempo: the file.config.sml per-program configuration file and the .tempo.sml per-session configuration file. Those are standard SML files. In particular, you may write (nestable) comments in them as follows.

(* Specialization of pow(base,expon)
   Assume expon is known
 *)
entry_point := "pow(D,S)";

post_inlining := true;
output_mode := COLOR;
external_functions := RESIDUALIZE ["printf","scanf"];

Note that each variable setting must be ended by a semicolon. If you wish to load explicitly an SML file, type:

use "some_file.sml";

Running Tempo In Batch Mode

If you wish to run Tempo in batch mode, just pipe SML commands into the shell command tempo, e.g.

mingus% echo 'wd := "/home/jake/spec"; cs "power"' | tempo
Running Tempo on SunOS-5
TEMPO Version 1.191, 03/24/98,
  Copyright (c) IRISA/INRIA-Universite de Rennes
val it = () : unit
- val it = () : unit
Starting from /home/jake/spec/power.at
Generating specializer file
Produced file : power.ctspec.C
val it = true : bool
- mingus%

The end of the input marks the end of the job.

Running Tempo Under Emacs

Here is a suggestion for running Tempo under emacs (courtesy of Olivier Danvy). Put the following lines in your .emacs file and run run-tempo to get a convenient shell buffer with a running Tempo.

(setq tempo-path "/usr/local/lib/tempo/bin/tempo")
(defun run-tempo ()
  "Run an inferior Tempo process,
     input and output via buffer *Tempo*."
  (interactive)
  (require 'comint)
  (pop-to-buffer
    (make-comint "Tempo"
		 "/bin/sh"
		 nil
		 "-c"
		 tempo-path))
  ;(inferior-sml-mode) 
  (make-local-variable 'comint-prompt-regexp)
  (setq comint-prompt-regexp "- ")
  (setq mode-name "Inferior Tempo"))

Modular Specialization

It is not usually practical or even desirable to apply specialization to a complete application, i.e. from the main() function down to all leaf functions. Instead, specialization is usually applied to part of an application (without altering the rest of the application) or to library functions.

Concepts

Modular specialization supports for specializing a fragment of an application. It is explained through the following definitions.

Application.
An application is some code that makes up a full executable, i.e. that contains a main() function. Part of it may be available only in binary form; you only need to have the source code of the parts that you wish to specialize (the module), and to know how those parts are called (the execution context).
Entry Point.
The entry point is (the name of) the function of your application that you wish to specialize. In practice, it generally is not the main() function.
Formals, Actuals and Parameters.
We use the terms formals to refer to the formal arguments of a function, actuals to refer to their actual value and parameters to designate the formals as well as the global variables that are visible from this function.
Execution Context.
An execution context before a function is called (or execution pre-context) is some knowledge about the current memory store as well as the actual arguments of the function. An execution context after a function is called (or execution post-context) is some knowledge about the uses of the results of the function, not only the returned value but all uses of the memory affected by the function call. (The term "knowledge" is intentionally vague as in practice we actually refer to analysis and specialization contexts; see below.)
Analysis Context.
The analysis context is a set of properties that are true at some point of the execution flow. The analysis context before a function is called (or analysis pre-context, or initial analysis context) is the execution pre-context that consists of alias relations and binding time properties concerning its parameters. The analysis context after calling a function (or analysis post-context), consists of the live uses of memory locations occurring after the function has returned.
Specialization Context.
The specialization context of the entry point (and more generally of any function) consists of actual values for the parameters (including content values for pointers).
Program (a.k.a. Module).
The program (or module) is the set of functions of your application that you wish to specialize. It at least includes the entry-point function. It may also include other functions called by the entry point, however it does not have to include all such functions. The program is provided to Tempo as a single C file.
External Function.
External functions are functions that are external to the program, i.e. functions of your application that are called by the program but that you do not want to specialize. The definitions of external functions should not be provided in the program file. Such functions may include library functions such as printf() or strcpy().
Making a function external can be a choice: it may not interesting to specialize, not actually specializable (always called with only static or only dynamic arguments), too big, etc. When a function is part of a library whose source code is inaccessible, the function of course must be external.
Abstract Function.
An abstract function is a function written to model the behavior of another function (usually an external function) with respect to the analyses. In other words, it may not respect the execution semantics of the function (i.e. return the same results) but it should respect the analysis semantics (i.e. return the same analysis results). Most often, an abstract function is useful in order to give an abstract definition to an existing function that is uninteresting to specialize or that is available only as binary code. See Behavior of External Functions below for more details.
Context Abstract Function.
Tempo needs to know the execution context in which the entry point is called from the application. This analysis context can be specified using a context abstract function. It may also be necessary to specify the behavior of the application after the entry-point function is called, especially uses of locations that are manipulated by the entry point (because otherwise they may be specialized away). This may also be specified using a context abstract function.
Abstract Function File.
Abstract functions (for external functions as well as context abstract functions) are provided to Tempo in a separate file suffixed with actx.c (e.g. fft.actx.c). This abstract function file is optional.

More practical details are given in the sections Behavior of External Functions and Specifying Complex Analysis Contexts below.

Installation of a Specialized Function

It is up to the user to integrate in the application a specialized function or, more generally, various instances of specialized functions. (Whether the specialized functions are produced at compile time or generated at run time is a separate issue.) In doing so, you must make sure that you call the specialized functions when appropriate, i.e. when the specialization hypotheses (actual values of static parameters) are valid. There are several strategies for that. In the general case, you must implement some switching mechanism between the original function and specialized functions.

Specialized Application

In some cases, it is possible to restrict the domain of your application so that your are sure that the specialized functionality will always be called in the appropriate context, unconditionally. In those cases, you can just replace the original entry point with the specialized one. This is often the case when you specialize interpreters. Another, less common case is when you specialize your whole application.

Dynamic Testing

If switching functions is needed, one approach is to test the execution context. If it matches a context for which you have a specialized function (either constructed at compile time or generated at run time), then call it. Otherwise call the original, generic, entry point function.

The cost is in performing the tests for each invocation of the function. This strategy is interesting when the test is negligible with respect to the execution time of the specialized function.

Guards

Another strategy to switching functions is to invoke the function indirectly via a pointer variable and to put guards at each program point where the execution context may change (with respect to specialization hypotheses). Each time the context is changed in the course of the execution, the corresponding guard checks if the new execution context matches a context for which you have a specialized function (either constructed at compile time or generated at run time). If so, the function pointer variable is set to the specialized function. If not, the function pointer variable is set to the original, generic, entry point function. Invocations should be indirect, through the function pointer variable.

The cost here is in performing the tests each time the context may change. This second strategy is interesting when there are many function invocations between each context change. Otherwise, you might end up performing tests, installing new specialized functions, but never actually calling the function.

Specialized Functions Cache

Another issue concerns specialized functions cache when doing run-time specialization: When is it interesting to make a new specialized function as opposed to use the original function? When is it interesting to keep in a cache an installed specialized function when the context changes, in the hope that it will eventually switch back to the same context? The answers to those questions are highly dependent on your application...

The Analyses and Their Precision

Tempo is an off-line partial evaluator: specialization is preceded by an analysis phase that prepares the specialization process (and makes it more efficient). Moreover, it lets you assess the degree of specialization of your program. The main analyses compute:

A large part of the power of an off-line partial evaluator lies in the precision of its analyses. All Tempo analyses are inter-procedural, i.e. properties at the various call sites of a function are exploited when analyzing the function. In the following, we list other features, that are specific to each analysis. But before that, we need to present the memory model used by Tempo.

Memory Model

Before explaining the different ways to parameterize and to read the results of Tempo's analyses, the concept of "location" must first be understood: all initial and deduced properties are specified or computed in terms of locations. Here are some definitions that will be used afterwards.

Scalar and Structured Types.
A scalar type is an integer, floating point or pointer type (including array). A structured type is a structure or union.
Named Memory Cells.
All C objects are stored in memory cells. Each memory cell has an address. Scalar memory cells store integers, floating point numbers or pointers (including pointers to arrays). Composite memory cells store structures, unions and arrays (i.e. the sequence of cells, not the pointer). A named memory cell is a memory cell that can be given a name, i.e.
  • a variable (whether local or global),
  • a function (for indirect function calls),
  • an array (i.e. the name of the constant pointer to the first array cell),
  • a structured data type (structure or union),
  • a field of a structured data type.
This is in contrast with for example malloc(), that does not return a named memory cell. In other words, named memory cells include static and stack allocated cell, but exclude heap allocated cells.
Locations.
A location is a named scalar memory cell. The fact that a location is scalar and that Tempo's analyses work on locations means that there is no property directly attached to a structure or a union; properties only apply to (scalar) fields of those structured types. Consequently, when providing information about a structured data type, each of its (scalar) field must be referred to individually. Similarly, visualization of computed properties attaches no explicit information to structured data type as a whole; however, each occurrence of individual fields does reflect the properties.
Composite Locations.
A composite location is a location that corresponds to possibly many actual memory cells. Composite locations are
  • arrays: a single name for all cells of the array, i.e. there is not an explicit location for each cell (see Array Monovariance below),
  • structure and union fields: a single name for all instances of the same structure or union type (see Structure Monovariance below).
Since properties are attached to locations, this means in particular that properties of arrays are properties that are true for all cells of the array (i.e. index does not matter).
Globals, Locals and Non Locals.
Globals are location that are static (in the C sense, i.e. not on the stack nor on the heap) and visible from everywhere in the program file. Locals of a function are stack allocated locations, i.e. local variables. Non locals of a function are all locations but locals that can be manipulated from the function, i.e. globals and, possibly, locals of other functions up in the call graph that are passed as pointer arguments or via globals.
Structure Monovariance.
Currently, our alias and binding-time analyses are monovariant with respect to structured types (structure and union). This means that for the purposes of the analyses, all instances of a given field are represented by a single location. Thus, properties of fields are properties that are true for all instances of the structured type. In Tempo, we use the name of the type to refer to structured type locations, as opposed to using the names of instances.
Array Monovariance.
Similarly, our alias and binding-time analyses are monovariant with respect to array cells. This means that for the purposes of the analyses, all cells of an array are represented by a single location. Thus, properties of arrays are properties that are true for all cells of the array. As a matter of fact, in Tempo we use the name of the array to refer to any (pointed) array cell.
Composite Locations and Binding Times.
Because of monovariance, once a field has become dynamic at some point in the control flow, it cannot be made static again afterwards, neither by an assignment nor by any other mechanism. This is because making the field of one instance static does not guarantee that the corresponding field of all other instances may be considered static, whereas it is always safe to leave it dynamic. The same applies to array cells: putting a dynamic value in an array cell makes the whole array dynamic for the rest of the control flow. E.g., 
struct str {int a; ...} s1, s2;
int u[5], x;
// Assume everything is static initially

x = dynexp;     // x becomes dynamic
u[0] = dynexp;  // u[i] becomes dynamic for all i
s1.a = dynexp;  // Both s1.a and s2.a become dynamic

x = 42;         // x is now static
u[0] = 42;      // u[i] stays dynamic for all i
s1.a = 42;      // Both s1.a and s2.a stay dynamic
Note that this happens even if there is only one instance of a given structured type or if the array index is fully known.
Composite Locations and Aliases.
The same applies to the alias property: once a field may point to some location at some point of the control flow, there is no way to "kill" this afterwards. This is because assigning the field of an instance with a pointer to some other location does not guarantee that the corresponding field of all other instances are still not able to point to the original location. However, it is always safe to assume that the field (of all instances) may point to both the old and the new location. 
struct str {int *a; ...} s1, s2;
int u[5], *p, a, b;
// Assume all pointers may point to nothing initially

p = &x;     // p may point to x only
u[0] = &x;  // u[i] may point to x for all i
s1.a = &x;  // Both s1.a and s2.a may point to x

p = &y;     // p may point to y only
u[0] = &y;  // u[i] may point to x or y for all i
s1.a = &y;  // Both s1.a and s2.a may point to x or y
Note that this happens even if there is only one instance of a given structured type or if the array index is fully known.

Alias Analysis

The alias analysis computes the set of possible targets for pointer locations and expressions. This analysis is:

flow-sensitive
The set of possible targets for a given pointer location may differ from one statement to another.
context-insensitive
There is a single alias analysis for each function, i.e. a single alias description for each function, not one per call site.

Side-Effect Analysis

The side-effect analysis computes the set of non-locals variables that are read or written in each function. This analysis is:

flow-sensitive
The set of possible effects depends on the control flow.
context-insensitive
There is a single side-effect analysis for each function, i.e. no particular context depending on the call site is exploited. It relies only on alias information, which is computed on a context-insensitive basis as well.

Binding-Time Analysis

The binding-time analysis annotates the program with binding-time information. This analysis is:

flow-sensitive
The binding time of a given location may differ from one statement to another.
context-sensitive
There is a separate binding-time analysis for each call site, depending on its binding-time context. This is also called (function) polyvariance.
return-sensitive
The BTA distinguishes between the binding time of the body of a function (static if the whole body is static, dynamic otherwise) and the binding time of its return value. With this approach, if a function performs some dynamic side effects but returns a static value, the static value can be exploited at the call site. The ability of the BTA to make this distinction is called return sensitivity.
sensitive to partially-static structures
A structure may have both static and dynamic fields at the same time.
use-sensitive
The binding time of a location is affected not only by the binding times of locations that it depends on, but also by the uses of the location. This information is actually computed by the evaluation-time analysis.
monovariant with respect to arrays, structures and unions
There is a single location for all cells of an array; see Array Monovariance. There is a single location of all instances of a given structured type (structure or union); see Structure Monovariance.

Evaluation-Time Analysis

The evaluation-time analysis make the binding-time analysis use-sensitive:

  • It makes dynamic all static expressions that appear in a dynamic context and are not representable as C program text (i.e. pointers, structures and arrays): ETA1.
  • It makes dynamic all the static definitions of variables with dynamic uses: ETA2.
  • If there is no static use of a definition, the definition is turned totally dynamic as the static facet is not needed: ETA2.

Precision for evaluation times in the ETA is the same as the precision for binding times in the BTA, i.e. the ETA is flow-sensitive, context-sensitive, return-sensitive, sensitive to partially static structures and monovariant with respect to arrays, structures and unions.

Configuring the Analyses

Tempo is an off-line specializer. This means that the specialization is preceded by an pre-processing phase. This pre-processing phase is divided into a sequence of program analyses that compute properties about locations and resulting specialization transformations:

  • the alias relation between locations,
  • the binding times of program locations,
  • the specialization actions, i.e. the transformations to perform at specialization time.

The result of the analyses can be visualized in order to assess the degree of specialization of the program.

In order to parameterize the analyses, the user must provide Tempo with the following compulsory information.

  1. A program, i.e. a single legal ANSI C file.
  2. An entry point, i.e. the root of the call-graph, i.e. the name of the function to specialize.
  3. Initial binding times for the arguments of the entry point.

In addition, the user may provide the following information.

  1. Initial binding times of global variables. By default, all uninitialized global variables are assumed dynamic.
  2. Initial binding times of arrays. This is necessary because of the array monovariance of the analyses. By default, all arrays are assumed dynamic.
  3. Initial binding times of structures and unions. This is necessary because of the structure (and union) monovariance of the analyses. By default, all fields are assumed dynamic.
  4. The binding time of external functions calls, i.e. the permission or prohibition to evaluate external functions (if any) at specialization time if all the arguments are static,
  5. The binding time of unknown indirect function calls, i.e. the permission or prohibition to evaluate external indirect function calls (if any) at specialization time if all their arguments are static,
  6. The behavior of external functions with respect to aliases and binding times. By default, external functions are assumed not to have any effect on aliases or binding times at all.
  7. The binding time of parameters passed by reference (for the entry-point function). The standard binding-time specification for the arguments describes just the arguments themselves, not the values they point to. By default, pointed scalar values have the same binding time as the pointer and pointed composite values are dynamic (i.e. default binding time rules for structures, unions and arrays apply).
  8. Initial alias relations among pointer parameters (actual arguments and global variables), if any. By default, it is assumed that all locations are unrelated.
  9. Live locations after the entry point is called in the original application. By default, no location is assumed to be live at the end of the program.

Specifying the Program to Specialize

The program to specialize is provided to Tempo as a single legal ANSI C file. It is passed through cpp (the C pre-processor) before parsing. Consequently, it may contain statements like #include, #define and #ifdef. When visualizing annotated source code with Tempo, you will see the result of the C pre-processor expansion, not the original code.

The specification of the program to specialize is done in two steps.

  1. The user must specifying the working directory, which is the directory where the program lies. In order to do so, the user may use either the wd variable, as in 
    wd := "/home/jake/spec/misc";
    or the cd command, as in 
    cd "/home/jake/spec/misc";
    which also sets the variable wd. By default, the working directory is the directory in which Tempo is run, unless the shell variable TEMPOWORK is defined.
  2. Then, in order to run any phase, the name of the program must be used each time, as in 
    an "fft";
    cs "fft";
    sp "fft";

    This runs the analyses and specialization of the program fft.c, located in the current working directory. Note that you must specify the file prefix only, not the suffix (i.e., "fft", not "fft.c").

    Note also that several programs may reside in the same working directory. Thus, you may run:

     

    sp "fft";
    an "power";
    if both fft.c and power.c lie in the current working directory.

In practice, step 1 is done once, as long as you work on the same program file, and step 2 is performed many times.

Entry Point and Binding Times For Its Arguments

The entry point and the binding-time information of its arguments are defined by the SML variable entry_point. This variable must be defined in the config.sml file (e.g. fft.config.sml), in the same directory as the c file (e.g. fft.c). Assigning it at the SML top level has no effect and the default value ("") is not meaningful. In the following example

entry_point := "foo(S,D)";

the function foo is the entry point. It has two arguments: the first one is initially static, the second one is initially dynamic.

Valid binding-time specifications for the entry-point parameters are:

S : scalar static argument
D : scalar dynamic argument
_ : uninitialized or non-scalar argument

If an argument is a structured type (union or structure), the specified binding time must be _ and the actual binding time must be provided separately (see Binding Time of Structures and Unions below). If the argument is a pointer (hence a scalar), the specified binding time is for the pointer, not the pointed value. See below for specifying binding time of pointed values.

Specifying Several Entry Points

For the time being, Tempo is restricted to a single entry point and binding-time information definition. If you wish to perform specialization for multiple entry points (e.g., a whole library), you have to explicitly (i.e. manually)

  1. Build a dummy entry point that calls all sub entry points. This is typically in a switch or a cascade of ifs so that the call to one entry point doesn't influence the calls to the others. It is up to you to propagate relevant binding time information from the dummy entry point to each sub entry points.
  2. Extract specialized entry points. There is some additional work to do on the resulting specialized file.
    1. At the moment, in a specialized program file, only the specialization(s) of the entry point is/are declared extern; all other specialized functions are made static (in the C sense). You have to manually turn those specifiers into extern.
    2. Furthermore, it is only possible to specify the name of the specialization of the actual entry point (using the variable specialized_entry_point_name). The sub entry points have to be renamed by hand, if desired.
    You must also make sure that sub entry points are not inlined into the dummy entry point.

 

Binding Time of Global Variables

The initial binding time for global variables is specified using the SML variable static_locations. The default is that no global locations are static, i.e. static_locations is the empty list. As an example, the following definition specifies that the global variables x and y are static; all other global variables are considered dynamic.

static_locations := ["x", "y"];

It is not necessary to specify the binding times of local variables (including formals), as these are determined automatically by their use.

Binding Time of Arrays

Because of array monovariance, there is only one location associated with an array. This location can be declared static using the SML variable static_locations as well, meaning that all cells of the array are static. E.g., an array int a[5] can be declared static as follows.

static_locations := ["a"];

Note that only the name of the array is used, without the brackets. Note also that the pointer to the array (i.e. a itself, meaning &a[0]) is a constant, and hence is always static.

Binding Time of Structures and Unions

Unlike binding times for scalar variables which are "per variable", binding times for a given structured type are the same for any instance: it is a "per type" binding time. (See Monovariance above.)

For example, if the C program contains the following declaration,

struct pt {
  int x;
  int y;
} point1, point2;

then specifying

static_locations := ["pt.x"];

with the following C declaration in the program file

makes both point1.x and point2.x static. An error will be reported if you try to specify

static_locations := ["point1.x"];

In other words, you must provide the name of the type for the fields of a structure or a union, not the name of an instance.

Structures and Unions Fields

If a whole structure or union is static, each field must be declared as such individually. For example, specifying

static_locations := ["pt.x","pt.y"];

with the following C declaration in the program file

struct pt {
  int x;
  int y;
} point1, point2;

will make both point1 and point2 totally static. An error will be reported if you try to specify

static_locations := ["pt"];

This is because there is no location associated to a structured type; the only locations are for each field.

Nested Structures and Unions

Let us consider the following global declarations:

struct pt2d {
  int x;
  int y;
};

struct pt3d {
  struct pt2d pt;
  int z;
};

struct pt2d u;
struct pt3d v;

Because the pt field of a pt3d structure has a structure type, trying to directly declare pt3d.pt or pt3d.pt.x to be static will raise an error. The only locations that can be declared static are pt2d.x, pt2d.y and pt3d.z. For example, the following makes u and v.pt static:

static_locations := ["pt2d.x", "pt2d.y"];

The following makes u and v static:

static_locations := ["pt2d.x", "pt2d.y", "pt3d.z"];

Anonymous Structures or Unions

If the definition of your original structure or union is anonymous (this is common with nested structures) like this

struct /*no name here*/ {
  int x;
  int y;
} point;

then SUIF will automatically generate a dummy name:

struct __tmp_struct1 {
  int x;
  int y;
} point;

As the name is generated automatically with an unknown suffix, it is not safe to rely on SUIF to pick a particular name for you. When is possible, it is better to provide an explicit name in the original file.

Restrictions on Typedef

Names of structured types defined using typedef cannot be used to specify a location. For example, with a type definition like this

typedef struct pt {
  int x;
  int y;
} point;
point point1, point2;

You cannot specify

static_locations := ["point.x"];

You have to write

static_locations := ["pt.x"];

Binding Time of External Function Calls

The SML variable external_functions is used to specify the binding times of external function calls. For each function, you may either force all calls to be residualized (i.e. dynamic) or to be evaluated (i.e. static) provided the arguments allow it (i.e. if they are all static).

Evaluation is often allowed for library functions, whereas residualization can be required to prevent I/O side-effects at specialization time (such as printing).

E.g., the following declaration means that all calls to the external functions foo and bar are residualized, regardless of the arguments or the possible abstract definitions are; all calls to other external functions are evaluated if all their arguments are static.

external_functions := RESIDUALIZE["foo","bar"];

This declaration has the following impact on the binding-time analysis.

foo(stat,dyn);  // Natural residualization of the call
foo(stat,stat); // Forced residualization of the call
gee(stat,dyn);  // Natural residualization of the call
gee(stat,stat); // Allowed evaluation of the call

If you have more external functions to residualize than to evaluate, you may want to use this other form, instead:

external_functions := EVALUATE["foo","bar"];

The above declaration means that all calls to the external functions foo and bar should be evaluated if their arguments are static; all calls to other external functions are always residualized. I.e.

foo(stat,dyn);  // Natural residualization of the call
foo(stat,stat); // Allowed evaluation of the call
gee(stat,dyn);  // Natural residualization of the call
gee(stat,stat); // Forced residualization of the call

The default treatment is to residualize all calls, i.e. to evaluate none of the external functions: EVALUATE[].

Binding Time of External Indirect Function Calls

The boolean variable residualize_all_icalls is used to specify the binding time of indirect external function calls. If it is true, indirect calls to unknown external functions are always residualized (independently of their arguments). If it is false, they are evaluated if possible (i.e. function pointer and arguments are static) at specialization time.

This variable is only useful when the phase to eliminate indirect function calls cannot totally transform some indirect calls. This usually happens when not enough information is given to the alias analysis: some unknown function pointer (provided as a global variable or as an argument to the entry-point function, or returned by an external call) may be used for an indirect call.

In the following program, fp may point to f1, f2, or *gfp, for which alias information is not provided.

int f1(int, int), f2(int, int), (*gfp)(int, int);

int entry()
{
  int (*fp)(int,int);

  if (c == 1)
    fp = f1;
  else if (c == 2)
    fp = f2;
  else
    fp = gfp;

  // fp may point to f1, f2 and ... *gfp

  return (*fp)(a,b);
}

The phase that eliminates external function pointers rewrites this program as follows:

int entry()
{
  if (c == 1)
    fp = f1;
  else if (c == 2)
    fp = f2;
  else
    fp = gfp;

  return _apply_1(fp,a,b);
}

int _apply_1(int (*_q)(int,int)), int _a1, int _a2)
{
  if (_q == f1)
    return f1(_a1,_a2);
  else if (_q == f2)
    return f2(_a1,_a2);
  else
    return (*_q)(_a1,_a2);
}

This rewriting enables possible specializations of f1 and f2, even though they are used through function pointers. However, the global variable gfp might point to some unknown function f3. That is why a default case (*_q)(_a1,_a2) remains in _apply_1. If the alias analysis can determine that the only possible targets are known functions (as here, f1 and f2), there is no such default case.

The remaining indirect external call

(*_q)(_a1,_a2);

can be forced to be dynamic or allowed to be static (providing all arguments are static), using the residualize_all_icalls variable. With

residualize_all_icalls := true;

the binding-time analysis yields only dynamic indirect calls, even if _q, _a1 and _a2 all are static

(*_q)(_a1,_a2);  // Note: static pointer _q later
(*_q)(_a1,_a2);  //       turned dynamic by eta1
(*_q)(_a1,_a2);  // Ditto

whereas with

residualize_all_icalls := false;

the binding-time analysis may yield a static (i.e. evaluated at specialization time) indirect call if both the function pointer and the arguments are static:

(*_q)(_a1,_a2);  // Redidualized because _a1 is dynamic
(*_q)(_a1,_a2);  // Redidualized because _q is dynamic
(*_q)(_a1,_a2);  // Evaluated

There is no way to specify an imposed or allowed binding time per indirect call site, not even per generated _apply_n function.

Behavior of External Functions

By default, external functions are supposed not to have any action. Consider for example a pointer argument to an external function call that has not been given an abstract definition:

ch = 'X';       // 'X' is static
read(fd,&ch,1); // Call to read does not affect ch
t = ch;         // Considered static instead of dynamic

The pointer &ch is read at the call site, but the content ch is considered unaffected, not even read. This is not specific to binding times: a similar case can be constructed regarding aliases. The problem is that the default void behavior for external functions is not safe.

In Tempo, the behavior of external functions with respect to aliases and binding times is expressed using abstract functions, i.e. some C code that mimics the actual implementation of external functions. The code of those abstract functions is used during the analyses to simulate the real behavior and yield the proper analysis results. However, at specialization time, only the actual values and implementations are used. In other words, abstract function are not specialized; calls to them may either be residualized or evaluated using the real implementation.

Example

Consider for example this implementation of the strcpy() function.

char *strcpy(char *dest, const char *src)
{
  char *orig_dest;
  orig_dest = dest;
  do
  {
    *dest++ = *src;
  }
  while (*src++ != '\0');
  return orig_dest;
}

This function copies the value of the src array into the dest array. No aliases are created. The alias and binding-time behavior of this function may be modeled by the following abstract function.

char *strcpy(char *dest, const char *src)
{
  *dest = *src;
  return dest;
}

Because of the monovariance of arrays, we achieve the effect of copying the contents of an array into another by copying a single cell. We also model the return behavior of strcpy by returning the dest pointer.

As a result, the binding-time analysis of the program file yields, for example, the following propagation of dynamic values (assuming q points to an array with dynamic content):

x = p[0];    // Static pointer to static array
strcpy(p,q); // Copy from static pointer to dynamic array
y = p[0];    // Static pointer to dynamic array

or the preservation of static computation (assuming q points to an array with static content):

x = p[0];    // Static pointer to static array
strcpy(p,q); // Copy from static pointer to static array
y = p[0];    // Static pointer to static array

Similarly, the alias analysis exploits the fact that the returned value of strcpy is a pointer to the same targets as the first argument.

char a[5], b[5], c[5], d[5], *p, *q, *r;
p = c1 ? a : b;
q = c2 ? c : d;
x = p/* a[], b[] */[0];  // p may point to arrays a or b
y = q/* c[], d[] */[0];  // q may point to arrays c or d
r = strcpy(p,q);
z = r/* a[], b[] */[0];  // r may point to arrays a or b

This model is correct with respect to an analysis that does not make any difference for different array cells (as is the case for Tempo). This is why the loop that is present in the original strcpy() function does not need to be represented in the abstract function. If the analysis was finer, e.g. interval analysis and separate attributes for array segments, a loop would be needed in order to express the (potentially partial) overwriting of dest with src.

Providing Abstract Functions

In order to provide abstract functions definitions to Tempo, just write them in a separate abstract function file, i.e. suffixed with actx.c. Thus, if the program file is foo.c, the optional abstract function file should be foo.actx.c.

When an abstract function is provided, Tempo automatically uses the abstract function for analysis and the actual function for specialization. Note that, additionally, you still may have to use variable external_functions in order to specify whether actual functions may be called at specialization time (see Binding Time of External Function Calls above).

In practice, the content of the program file and the abstract function file (c and actx.c) are merged and analyzed together. (There is a special treatment for functions defined in the abstract function file though.) When visualizing the result of the analyses, you can see abstract functions as well. However, all abstract functions are removed during action analysis, i.e. the last analysis phase, which yields an action-annotated program without any trace of abstract code.

Modeling Dynamic Memory Allocation

As explained above, the memory model of Tempo does not handle memory cells that have no name, such as cells generated by dynamic memory allocation. Another typical use of external functions is to bestow (predefined) names on such memory cells by providing a function that models memory allocation. E.g.,

char dummy_location[1];

char *malloc(size_t size)
{
  return dummy_location;
}

The above abstract definition returns the same named memory cell, i.e. dummy_location[], for any call to malloc(). At specialization time, this abstract definition is removed; the actual malloc() function is used if static, or else residualized (see Binding Time of External Function Calls above).

Returning the same location for each call to malloc() will merge all effects concerning that location. For a finer analysis, you may want to define and use a different memory allocation routine per call site, each one returning locations with a different name.

Moreover, calls to malloc() are often followed by a cast. Because it is not totally safe to use casts in Tempo (especially for structured types), it is safer to define at least a "per type" allocation routine, e.g.

struct foo dummy_struct_foo;

struct foo *malloc_struct_foo(size_t size)
{
  return &dummy_struct_foo;
}

Note that it is useless to have several memory allocation routines for the same structured type because of monovariance: all named structures (or unions) will share the same analysis properties anyway.

Safety of Abstract Functions

You must be careful in writing an abstract function as Tempo can do nothing but assume it models the original function correctly.

Moreover, you must keep in mind the precision of the analyses: there does not exists a single good abstraction for a function that is independent of the analyses. Sometimes an abstract definition might be too precise with respect to present analyses.

Consider for example the above abstract definition for the function strcpy(). In this definition, it is necessary for dummy_location to be an array for safety reasons. If it is a scalar, as in the following abstract definition,

char dummy_location;

char *malloc(size_t size)
{
  return &dummy_location;
}

this is not be safe as one could write (pink color is for a static & dynamic binding time)

p = malloc(1);  // p points to dummy_location
*p = dynexp;    // dummy_location becomes dynamic
q = malloc(1);  // q points to dummy_location
*q = 's';       // dummy_location becomes static
ch = *p;        // Considered static instead of dynamic

Note that it is always safe to consider an expression dynamic instead of static. (After all, the BTA, as most analyses, just computes an approximation.) However, it is not safe to consider static an expression that depends on a dynamic value.

The problem above comes from the fact that the assignment *q = 's' acts as a killing definition for the binding time of dummy_location. This situation does not arise with an array definition for dummy_location as, according to the memory model, the analysis conservatively merges binding times of all cells (i.e. array monovariance). Hence, with this definition,

char dummy_location[1];

char *malloc(size_t size)
{
  return dummy_location;
}

the program is analyzed as follows

p = malloc(1);  // p points to dummy_location
*p = dynexp;    // dummy_location becomes dynamic
q = malloc(1);  // q points to dummy_location
*q = 's';       // dummy_location stays dynamic
ch = *p;        // Considered dynamic

Now *p is safely considered dynamic.

Standard Tricks for Specifying Aliases and Binding Times

To finish with generalities concerning abstract functions, here are some standard tricks that are commonly used to express various binding-time or alias behaviors in abstract function files. The section Specifying Complex Analysis Contexts below contains other typical uses.

Dummy Dynamic Location

To make a dynamic location, you can declare a global location in the actx.c abstract function file; global locations are dynamic by default (see the variable static_locations ). Alternatively, calling a dummy external function returns a dynamic value by default (see the variable external_functions ). E.g.

int dyn;
foo()
{
  x = dyn;    // Globals are dynamic by default
  y = fdyn(); // So are external calls
}

Dummy Static Location

To make a static location, you can declare a location in the abstract function file and initialize it to a constant value (or declare it static in the config.sml configuration file). E.g.

int stat = 0;  // Or add stat in static_locations
foo()
{
  x = stat;
}

Turn a Location Dynamic

A location may be turned dynamic either by assigning a dynamic value to it or by making an assignment under dynamic control, e.g. 

if (dyn)  // Any dynamic condition
  x = x;  // Even if x is static,
use(x);   // now x is dynamic

Pointer to a Set of Locations

To make a dynamic (resp. static) pointer to a set of locations, you can assign the pointer to one of the required targets depending on a dynamic (resp. static) condition, e.g. 

{
  if (cond)  // p gets the same binding time as cond
    p = &x;  //   p may point to x
  else       // or 
    p = &y;  //   p may point to y
}

Now p points to either x or y. Furthermore, the variable p has the same binding time as the expression cond.

Note that cond should not be a constant because SUIF unconditionally eliminates dead code when parsing code such as if(0) or if(1). A simple variable, as used in if(cond) above, does the trick.

Note also that the ifs are necessary because assignments to pointers may kill previous targets. E.g., after 

{
  p = &x;  // p may point to x only
  p = &y;  // p now may point to y only
}

variable p may point to location y only.

Specifying Complex Analysis Contexts

When only a module of a larger application is to be specialized (modular specialization), the user must specify the exact analysis context of the module. This description includes information about the execution context both before and after the entry point is called from the larger application.

If the parameters (formals of the entry point and globals) are simple scalars, the variables entry_point and static_locations are enough to provide Tempo with the relevant initial binding time context (see Entry Point and Binding Times For Its Arguments and Binding Time of Global Variables above). This covers a lot of common cases.

For specifying more complex contexts, i.e. initial alias relations, binding times of parameters passed by reference, or live locations after calling the entry point, another (less declarative) mechanism is provided, named context abstract functions.

In addition to abstract external functions, the abstract function file (i.e. suffixed with actx.c) may contain:

  • a function void set_analysis_context(), whose arguments are pointers to the entry point's arguments, to be used for setting the initial analysis context, i.e. the execution context just before calling the entry point in the original application.
  • a function void set_post_analysis_context(), whose arguments are pointers to the entry point's arguments, to be used for setting the uses of non-locals of the entry point, i.e. the execution context after calling the entry point in the original application.

If a function set_analysis_context() or set_post_analysis_context() is defined in the abstract context file, Tempo will automatically create a new (dummy) program entry point. This new entry point has the same interface as the previous one and does three things:

  1. It calls the set_analysis_context() function (if any) with arguments that are pointers to the original entry-point arguments.
  2. It calls the original entry point.
  3. It calls the set_post_analysis_context() function (if any) with arguments that are pointers to the original entry-point arguments.

For example, starting from a program file bar.c with content

 

char foo(int a, struct baz *b) { ... }

and an abstract context file bar.actx.c with content

 

void set_analysis_context(int *p_a, struct baz **p_b)
{ ... }
void set_post_analysis_context(int *p_a, struct baz **p_b)
{ ... }

Tempo actually analyses merge the two files and considered as the new entry point the following generated function.

char dummy_entry_point(int a, struct bar *b)
{
  char retval;

  set_analysis_context(&a,&b);
  retval = foo(a,b);
  set_post_analysis_context(&a,&b);
  return retval;
}

Do note that abstract context functions set_analysis_context() and set_post_analysis_context() take as arguments pointers to the real entry-point arguments. The body of those functions may contains any C code in order to model the proper execution context (see Behavior of External Functions).

Note also that the dummy entry-point function, as well as set_analysis_context() and set_post_analysis_context(), are only used in the main analysis stages. They are removed at the beginning of the phase that performs the flattening of static returns (return sensitivity processing) and replaced by the original entry point. In particular, there remains no trace of them in the action-annotated program.

The following sections give various examples showing uses of context abstract functions.

Binding Times of Parameters Passed By Reference

When declaring a pointer static or dynamic, the binding time concerns the address only, not the content. By default, pointed scalar values have the same binding time as the pointer and pointed composite values are dynamic (i.e. default binding-time rules for structures, unions and arrays apply). The exact binding time of the content can be specified as follows.

Pointers to Structures or Unions

Because of monovariance, the binding time of structures and unions are declared for all instances and must be stated separately (see Binding Time of Structures and Unions above). This is the case even when the structure or a union is first given as a pointer.

Pointers to Scalars

Declaring a pointer to static or dynamic scalar can be specified using the context abstract function set_analysis_context(). Consider for example the following program file foo.c

int a, b, *q1, *q2, *q3, *q4;

entry(int *q, int x) { ... }

and the foo.actx.c file.

int dyn1, dyn2; // Dummy dynamic locs
int stat = 0;   // Dummy static (thanks to the init) loc

                    // Declarations from foo.c are needed
extern int *q1,*q2; // only for the variables that are
                    // actually used in foo.actx.c

void set_analysis_context(int **p_q, int *p_x)
{
  // p_q is a pointer to the real (pointer) argument q
  // p_x must be present though unused 

  if (dyn1)
    q1 = &dyn1; // q1 dynamic ptr to some dynamic loc
  if (dyn1)     // q1 may also point to some other
    q1 = &dyn2; //   dynamic loc
  q2 = &dyn1;   // q2 static ptr to some dynamic loc
  q4 = &dyn2;   // q4 static ptr to some other dynamic loc
  *p_q = &stat; // q static ptr to some static loc
}

Note that, in the above example, q1 may point to two locations whereas q2 and q4 may point only to a single (different) locations. It is important here to provide a faithful information (i.e., same or different location) because it may have an impact on the analysis. For example, if q2 and q4 were pointing to the same location dyn1, then assigning a static value to *q2 would make *q4 static as well. (*q1 would still not be static though, because it could point to dyn2 as well.)

Note also that the above specification concerning q1 is not equivalent to the following one:

  if (dyn1) {
    q1 = &dyn1; // q1 points to dyn1 only
    q1 = &dyn2; // q1 now points to dyn2 only
  }

Indeed, because the assignment act as a killing definition, only the latest one is taken into account in the final result. (See Behavior of External Functions: pointer to a set of locations.)

Pointers to Strings and Arrays

As is the case for structures and unions, the binding time of arrays (e.g. strings) must be declared explicitly because of array monovariance. However, the binding time is not "per type" but "per actual array". Hence the above scheme can be applied to specify the binding time of pointed arrays.

There is a trick though, because SUIF unconditionally turns array arguments into pointers. As a result, type information is lost, which can make the analysis unsafe. Let us consider an entry point f defined as follows:

int f(int a[])
{
  a[0] = 3;
  return a[1];
}

This program is translated by SUIF into:

int f(int *a)
{
  *a = 3;
  return a[1];
}

As a result, Tempo cannot tell any longer whether a points to an scalar integer or to an array. Now assume the array a is dynamic. In the first case, if a points to an scalar integer, the statement *a = 3 acts as a killing definition and the location a is made static. As a result, a[1] is considered static as well, which is wrong (i.e. unsafe). In the second case, if a is considered to point to an array, the statement *a = 3 does not act as a killing definition and the location a is stays dynamic because of array monovariance. In order to have that second, correct behavior, you can define the following context abstract function.

int dummy_array[1];

void set_analysis_context(int **p_a)
{
  *p_a = dummy_array;
}

This actually defines argument a of f as a static pointer to a dynamic array. If the array is static, just add dummy_array in the variable static_locations. Note also that the above context abstract function forces the binding time of the argument of f to static, even if the variable entry_point specifies f(D). This is because dummy_array is a constant (hence static) pointer. If the pointer to the array is dynamic, you may define:

int dyn, dummy_array[1];

void set_analysis_context(int **p_a)
{
  if (dyn)               // Dynamic condition makes
    *p_a = dummy_array;  // pointer p_a dynamic
}

Initial Alias Relation

Initial alias relations between locations can be specified using set_analysis_context(). Suppose we want to specialize the following procedure, which has been extracted from a larger program. Let dyn be some dynamic expression and assume arguments of f are all static pointers to static locations.

int a;               // Assume a is static initially
f(int *x,int *y)     // Static ptrs to static locations
{
  if (dyn)           // The dynamic test makes *x
    *x = *y - a;     //   dynamic after the condition
  c = (*y + a) / *x; // Is (*y + a) static ?
}

Without more information, Tempo will consider that expression *y + a is static, so that it can be replaced by a constant during specialization. This is unsafe as function f could be called in the larger program (i.e. the application) with one of the following contexts:

f(&a, &b);
f(&b, &b);

In the first case, making *x dynamic also makes a dynamic because of the aliasing relation. In the second case, making *x dynamic makes *y dynamic as well.

We can specify these properties using the context abstract functions and thus yield a safe specialization. For example, the second case above can be specified by the following set_analysis_context() which states that the arguments x and y of f point to the same static cell.

int dummy = 0;      // Any static value

void set_analysis_context(int **p_x, int **p_y)
{
  *p_x = *p_y = &dummy; // *p_x and *p_y refer to the same thing
}

Live Locations After The Entry Point

Live locations refer to locations that are still live at the end of the program being specialized. This can happen during modular specialization, when the program fragment is extracted from a larger program and this fragment is reinserted after specialization. Consider for example this function

void foo(int a, int b)
{
  x = x + y;
  y = x + b;
  z = x + a;
}

used in the following context in the larger application.

x = 1;
y = 2;
z = dyn;
foo(4,z);
bar(x,y,z);  // Called with arguments (3,3+dyn,7)

In this context, function foo can be specialized with a binding-time context where: a, x and z are static; b and y are dynamic. The binding time analysis then yields:

void foo(int a, int b)
{
  x = x + y;    // Static assignment
  y = x + b;    // Dynamic assignment
  z = x + a;    // Static assignment
}

which leads to the following specialization:

void foo_1(int b)
{
  y = 3 + b;
}

However, it is not correct to replug this function in the original application.

x = 1;
y = 2;
z = dyn;
foo_1(z);
bar(x,y,z);  // Called with arguments (1,3+dyn,dyn)

The problem comes from the fact that Tempo has not been instructed that locations x, y and z are used after the entry point is called. Tempo has assumed that they were not used and has specialized away all the static locations (that is why only y remains).

The variable live_locations is used to indicate to Tempo that some locations are live after the entry point is called. (Syntax and constraints on locations are the same as for variable static_locations.)

live_locations := ["x", "y", "z"];

Using this information, Tempo now produces the following binding times.

void foo(int a, int b)
{
  x = x + y;    // Static & dynamic assignment
  y = x + b;    // Dynamic assignment
  z = x + a;    // Dynamic assignment
}

which leads to the following specialization:

void foo_2(int b)
{
  x = 3;
  y = 3 + b;
  z = 7;
}

It is now correct to replug this function in the original application.

x = 1;
y = 2;
z = dyn;
foo_2(z);
bar(x,y,z);  // Called with arguments (3,3+dyn,7)

Live locations may be thought of as dynamic uses after calling the entry point. It is actually implemented using the backward propagation of dynamic uses performed by the evaluation-time analysis phase, i.e. ETA2.

It is equivalent to specify live locations using variable live_locations or to model a use of those locations in the set_post_analysis_context() function. E.g., in the above example, live locations could also have been specified using this definition in the abstract context file:

int dyn;                // Dynamic by default

void set_post_analysis_context(int *a, int *b)
{
  do { x=x; y=y; z=z; }  // Turns them dynamic
  while (dyn);           // and make dynamic uses
}

In practice, variable live_locations covers most common cases. The function set_post_analysis_context() is used for more complex cases, especially when aliases are involved, as it is easier to rely on Tempo's analyses to simulate the exact dynamic uses. In this case, some C code from the application can be copy/pasted (and possibly abstracted) into the function set_post_analysis_context().

New alias relations occurring after the entry point is called do not actually have an impact on analysis and modular specialization. However, they may imply different uses of locations, which does have an impact on specialization.

Visualization

Files containing the result of intermediate stages of the analysis have extensions ".as" and ".at", e.g. fft.bta.as, fft.at. They are not kept by default, except the ".at" file which is the final result of all the analysis phases.

The results are also stored as commented colored C files (generated by default) that can be used to visualize the outputs of the analysis, e.g. fft.bta.color, fft.at.html. In those colored files, the main items for understanding the result of the analyses are:

Colored Files

Color files show the result the analyses. Each color file has a legend near the top describing the colors used in the file. The colors have similar meanings (i.e. binding-time and evaluation-time information) in most of the files, except the at.color file, showing the results of the action analysis. We describe the colors used in this file separately.

For visualizing those files, you can choose between two colored files formats:

  • the HTML format, that can be displayed using any any web browser,
  • the MIME text/enriched format, than can be displayed using GNU emacs or xemacs.

The Tempo viewer variable let you choose between those two formats. It may be set to either html or emacs triggering the generation of HTML files (suffixed with .html) or MIME text/enriched format files (suffixed with .color).

Be careful: if you choose, say, html, then the ".color" files that might be present in the directory will not be removed when the ".html" files are generated. This may lead to inconsistencies and confusion if later on you forget about html and read the ".color" files (that will not be up-to-date).

In the following explanation, we assume that viewer is set to emacs. If viewer is set to html, the HTML files generated are colored similarly.

If you have troubles visualizing ".color" files with emacs, consider reading the Emacs Installation Issues in the Installation Manual.

See also:

Text For Alias information

Recall that the analyses operate on the output of SUIF. Hence the color files contain the results of transformations performed by SUIF. In particular, note that SUIF unconditionally performs the following translations:

 

ptr->field => (*ptr).field
... *ptrexp ... => suif_tmp42 = ptrexp;
... *suif_tmp42 ...

where ptrexp is some pointer expression (not just a variable). Hence any dereference is explicit and applies only to a pointer variable.

Alias information appears in the C output files as comments after each pointer dereference:

*ptr/* loc1, ..., locN */

where loc1, ..., locN is the list of locations where "ptr" may point to, i.e. it is a superset (safe approximation) of possible targets. Those locations may be variable (including pointers) locations, array (contents) locations, structure locations, or (structure) member locations (remember that all instances of a structure type have the same binding time.) Here is how you can read alias information:

*ptr/* var */
ptr may point to variable var,
*ptr/* a[] */
ptr may point to any cell of array a,
*ptr/* {s} */
ptr may point to any structure of type struct s,
*ptr/* s.f */
ptr may point to field f of any structure typed struct s.

If the pointer variable has not been initialized (it may point to nothing yet), we consider that it points to... what it points to!:

*ptr/* *ptr */

Thus, the alias information is never empty.

See also:

Colors For Binding-Time and Evaluation-Time Information

The legend in ".bta.color" files, that express the results of the BTA phase, is:

/* LEGEND:  STATIC  DYNAMIC  SD_FUNC  STRUCTURE  BOTTOM
 */

In the subsequent phases (i.e., ".color" files for "eta1", "eta2", "flsret", "flsd" and "preproc2"), the legend is:

/* LEGEND:  STATIC  DYNAMIC  STAT&DYN  STRUCTURE  BOTTOM
 */

The only difference concerns the interpretation of the pink color, i.e. SD_FUNC vs. STAT&DYN.

Blue color: Static

Blue is always used for static expressions. The color of the left-hand side of an assignment statement deserves some explanation. After the BTA (i.e., in the ".bta.color" file), when the L-value is known at specialization time, the left-hand side of an assignment is considered static, regardless of the binding time of the variable before or after the assignment statement. Beginning with the ETA1 (i.e., in the ".eta1.color" and subsequent files), the color reflects the evaluation time of the assignment, and thus the binding time of the variable after the assignment.

Red color: Dynamic

Red is always used for dynamic expressions and statements. The color of a function identifier (and parentheses) in a function call reflects the binding time of the body of the called function. Regardless of this binding time, if the function definition is part of the program, it will be specialized. Thus even when the call is dynamic, some specialization can occur.

Pink color: Static & Dynamic

There two meanings for the pink color, according to the phase

BTA
The pink color in the BTA only refers to calls to functions that contain some dynamic code in the body and have a static return value. This property is indicated in the legend as SD_FUNC (static and dynamic function). Such calls will eventually be flattened in a subsequent phase.
ETA (and subsequent phases)
The pink color in the ETA and subsequently refers to definitions (and their subcomponents) that are both evaluated and residualized. This property is indicated in the legend as STAT&DYN (static and dynamic expression). The use of pink in ETA files is actually ambiguous, since it is also used for calls to functions that contain a dynamic body and a static return value (as in the BTA).

Pale blue color: Structure

In the ".color" files (except the ".at.color" file), structures are considered to simply have a generic "structure" binding-time. This "structure" binding-time does not specify if the structure is totally static, partially static, or totally dynamic. It only appears if the structure is manipulated as a whole, e.g. assigned to another structure or passed as an argument. When a field is selected (with the "." dot operator), the field will be annotated with its corresponding binding time.

This color may appear as pale green, rather than pale blue.

Black color: Bottom

Black indicates a term for which no binding time can be determined. Black usually appears when local variables are used before they are assigned. If the code is not dead code, this situation may represent an error in the source program. When combined with other binding times during the BTA, the "bottom" binding time is treated as a "static" binding time, i.e. a static (resp. dynamic) expression combined with a bottom expression make a static (resp. dynamic) expression.

Colors For Actions

The legend in ".at.color" files, that express the results of the Action Analysis phase, is:

/* LEGEND:  EVAL  REDUCE  REBUILD  IDENTITY  STRUCTURE  EV&RES
 */

Blue color: Evaluate

Blue indicates a term that can be completely evaluated during specialization. Variable declarations that can be eliminated during specialization are also colored blue.

Green color: Reduce

Green indicates a term that can be simplified during specialization, but contains some dynamic components. For example, an if statement with a static test but dynamic code in the branches would be colored greern: after specialization, the if statement will be rewritten into (the specialization of) one of the two branches.

Orange color: Rebuild

Orange indicates that a term cannot be simplified during specialization, but that the term does contain some subexpressions that can be simplified. For example, in an addition expression with a static operand and a dynamic operand, the addition operator would be colored orange.

Red color: Identity

Red indicates a term that must be completely residualized. Such terms are essentially copied unmodified into the residual program. Variable declarations that are not used during specialization and will be part of the residual program are also colored red.

Pale blue color: Structure

Pale blue is used for values of structure type, as in the other analyses. (It actually hides one of two possible actions: "identity" or "evaluate & residualize"; the case "evaluate" is printed out properly.)

Pink color: Evaluate & Residualize

Pink is used for terms and variable declarations that are both evaluated and residualized during specialization. Because of the function flattening phase, there is not the second meaning of pink (in the BTA or ETA files) to indicate a function that has a static return value but some dynamic expressions in the function body.

Function Polyvariance (a.k.a. Context Sensitivity)

After the BTA, a function definition may appear several times in the colored file. Because the BTA is polyvariant, each occurrence of the definition corresponds to a different binding-time contexts, e.g. once with a static argument, once with a dynamic argument. The binding-time context includes the binding times of the read variables, as well.

In order to differentiate each variant of the function at the call site, the name of each function is labeled with an index (shown as a comment just after the function name) at the function definition as well as at the call site. Note that the index is global: each function, variant or not, gets a different index (e.g. f 1, f 2, g 3, g 4), as opposed to a "per-function" index (e.g. f 1, f 2, g 1, g 2).

Note that there exist also a degree of polyvariance in the ETA as each BTA variant may be further split into several ETA variants.

Note also that the polyvariance index is global to the current file: there is no relation between some index in the ".bta.color" file and the same index in the ".eta2.color" file.

Function Call Site

A function call looks like this:

bar/*7*/(statexp, dynexp, (sdexp))

The corresponding binding-time information can be read as follows.

Function name and actuals' parentheses: bar(...)
Binding time of the both the function body and the return value: blue means that both are static, red means that both are dynamic, pink (as above) means that the body is dynamic while the return value is static. If the function has a void return type, the binding time color is that of the body (thus it cannot be pink).
Number next to function name: /*7*/
Polyvariance index, in order to find the corresponding definition (see Function Definition below). Note that the index numbers for a particular function vary from analysis to analysis. In the HTML colored files, the index number at each call site is a hyperlink to the corresponding definition.
Actuals: statexp, dynexp, (sdexp)
Binding time of each actual argument. The possible extra parenthesis level means that the binding time of the actual argument (given by the color of the expression inside the parentheses) is different from the binding time of the formal argument (given by the color of the parentheses) in the analyzed function; this may happen only after ETA2 as the analysis may turn a static expression into a static&dynamic or a totally dynamic expression.

Function Definition

Let us consider the following colored binding-time annotations computed for a function definition.

// BT of return, index, BT of body, BT of formals
extern int foo/*3*/(int stat, int dyn)
  {               // BT of body: dynamic
    gdyn = dyn;   // BT of stmt: dynamic
    return stat;  // BT of return: static
  }               // BT of body: dynamic

The corresponding binding-time information can be read as follows.

Type and function name: int foo
The color of the function name and type (here blue, i.e. static) indicates the binding time of the return value. If the function has a void return type, the function name and type are displayed in black.
Number next to function name: /*3*/
Polyvariance index. Because of polyvariance, there can be several definitions of the same function corresponding to different call site (see Function Definition above), each with different binding-time properties. While all variants have the same name, each has a unique index number. Note that the index numbers for a particular function vary from analysis to analysis.
Formals' parentheses: (...)
Binding time of the body of the function: red, i.e. dynamic, in the above example.
Formals: int stat, int dyn
Binding time of each formal argument.
Body's braces: {...}
Binding time of the body of the function: red, i.e. dynamic, in the above example.
Return statement: return ...
Binding time of the return value: blue, i.e. static, in the above example. If the function has a void return type, the binding-time color (static or dynamic) is irrelevant.

Function Signature

A signature is generated for each function when the variables verbose_headers is true (the default). In this case, the signature is shown in a comment at the beginning of each function. It provides information about the non-locals of a function. It looks like this.

extern int foo/*42*/(int u, int v)
/*
binding times of read non_locals: a, b, tab, str.x
binding times of written non_locals: a, str.y
residual non-locals top: a, str.x
eval non-locals top: str.x
residual non-locals bottom: b
 */
  {
    ...
  }

Names listed are location names: scalar variables, arrays (without brackets), fields of structures and unions (with the name of the type, not of an instance).

This signature contains up to six parts. Only the non-empty parts are shown. The following signature components may appear in all color files.

binding times of read non_locals:
This list gives the binding times of non-local variables and structure fields that are read in either this function or in any function called by this function.
binding times of written non_locals:
This list gives the binding times of non-local variables and structure fields that are written by either this function or by any function called by this function.

The ETA2 propagates information backwards from the point where variables are used to the points where they are defined. (There are possibly several of them.) In the ".eta2.color" file (as well as colored file of subsequent phases), a function signature contains in addition information about non-local variables that are evaluated or residualized within the function (or some function it calls) and about non-local variables that are evaluated or residualized after some call site of the function:

residual non-locals top:
There are residual occurrences of the non-local variables in this list somewhere in the control flow path after entering this function.
eval non-locals top:
There are evaluated occurrences of the non-local variables in this list somewhere in the control flow path after entering this function.
residual non-locals bottom:
There are residual occurrences of the non-local variables in this list somewhere in the control flow path after leaving this function.
eval non-locals bottom:
There are evaluated occurrences of the non-local variables in this list somewhere in the control flow path after leaving this function.

If a variable is in a "top" list, but not in the corresponding "bottom" list (not to be confused with the black "bottom" binding time), then there is an occurrence of the variable within the function or some function it calls. If a variable is in a "bottom" list, but not in the corresponding "top" list, then the function or some function it calls provides the definition required for the subsequent occurrence of the variable.

Entry-Point Signature

If verbose_headers is true (the default), there is also a comment near the beginning of each color file indicating the call signature of the entry point. This signature may contains the following information:

binding times of formals:
This list gives the binding times of the formals.
binding times of read non_locals:
This list gives the binding times of the global variables that are used by the program.
residual non-locals bottom:
This amounts to a list of the live variables after the program is called in the larger application, as specified by the live_locations Tempo variable, or residualized via the set_post_analysis_context() function.

Compile-Time Specialization

Once the analysis has been performed successfully, i.e. if you are satisfied with the computed binding times, you can move on to building a compile-time specializer. The compile-time specialization is done in two steps:

  1. Construction of a Compile-Time Specializer, given a successful analysis (i.e. an .at file).
  2. Invocation of a Compile-Time Specializer, given actual values for static parameters of the entry point, yielding the source of a specialized program.

The first step is generally done once; you do not have to rebuild a new compile-time specializer as long as your program does not changes. The second step can be performed many times, for each set of specialization values.

See also:

Construction of a Compile-Time Specializer

There is no special parameterization for the construction of a compile-time specializer; just run the cs top-level command on your program. (See Building a Compile-Time Specializer.)

You do have to rebuild the specializer each time that you provide new specialization values; just edit the .sctx.c file (see below) and re-run the sp top-level command.

Invocation of a Compile-Time Specializer

Before specializing a program, using the sp top-level command (see Running a Compile-Time Specializer), a value must be provided for each piece of data which has previously been declared as static. Recall that static parameters can be globals as well as arguments of the entry point. Because the initialization of those values can be arbitrarily complex, including library calls, the values are given using a C file that is linked to the compile-specializer for performing actual specialization. This C file is suffixed ".sctx.c". It should at least:

  • Include the file suffixed .sctx.h, that has been generated by the construction of the compile-time specializer phase. The .sctx.h file provides the exact prototype of the set_specialization_context() function (see just below). It also contains the type definitions and the declarations of the global variables of your program.
  • Define a function named set_specialization_context() whose arguments are pointers to the actual static arguments of your entry point, in the same order. Unlike the set_analysis_context() function, the dynamic arguments of the entry point are not (and must not be) present.

The set_specialization_context() function is called to set the static values before specialization so that you can set them by an indirect assignment. Because all declarations are provided through the .sctx.h file, static global variables can be set by ordinary assignment. E.g. 

#include "foo.sctx.h"

void set_specialization_context(int *expon)
{
  *expon = 4;
  glob = 3;
}

You can use the name that you want for the arguments as it is a normal C function. In practice, it is convenient to reuse the argument names of the entry point, i.e. to start from the list of formal arguments in the definition of the entry point function, remove the dynamic ones and "add a star" in front of each remaining formal.

The general rule for not forgetting to provide a static value to a static memory cell is to check all locations listed in the static_locations variable, as well as the static entry point arguments listed in the entry_point variable. If you forget to initialize a memory cell, its value is undefined, as in any C program.

Since the .sctx.c file is a standard C file, you may also call functions, open files, read from the terminal, etc. E.g. 

#include 
#include 
#include "foo.sctx.h"

void set_specialization_context(int *n, struct bar **x)
{
  printf("Enter number of iterations: ");
  scanf("%d",n);

  phase = 4.0 * atan(1.0);

  *x = (struct bar *) malloc(sizeof(struct bar));
  (*x)->a = *n / 2;
  (*x)->b = &phase;
}

As you can see in the above example, there is no need to declare the global variable phase nor the strcture type bar: they are declared in the foo.sctx.h file.

Note that structure bar may have more fields than a and b. During specialization, the structure that are partially static are not split into separate static and dynamic parts. You may thus call a function that initializes all fields of a structure even though only some of them are static. The initialization of dynamic fields is just useless. However, you cannot initialize, say, a dynamic global variable as it is not declared in the .sctx.h file.

Common Errors in Setting Specialization Contexts

A common error is to set the local variables of set_specialization_context(), not their pointer values (i.e. not the static arguments of the entry point), e.g. 

void set_specialization_context(int *expon)
{
  expon = 4;  // Should be *expon
}

Another common error in .sctx.c files is not to provide/allocate memory cells. This generally leads to segmentation faults or bus erros. Consider for example the following implementation of an inner product. 

int dot_product(int size, int *u, int *v)
{
  int i, sum = 0;
  for (i = 0; i < n; i++)
    sum += u[i] * v[i];
  return sum;
}

Assuming vector u and integer size are static, it is an error to define this: 

#include "dotprod.sctx.h"

void set_specialization_context(int *size, int **u)
{
  *size = 3;
  (*u)[0] = 1;
  (*u)[1] = 0;
  (*u)[2] = 5;
}

The reason is that no memory cell has been allocated for vector u. What the entry point expects is an initialized integer size and a initialized pointer to an initialized vector. What is written above does initialize the size but does not initialize the pointer; it assumes the pointer is initialized and only initializes the vector. When specializing the program, you will most likely get a segmentation fault or a bus error but in any case not the expect behavior. A pointer and a vector may be initialized as follows. 

#include "dotprod.sctx.h"

int init_u[3] = {1,0,5};

void set_specialization_context(int **u, size *n)
{
  *size = 3;
  *u = init_u;
}

You may also use malloc() to allocate the memory. But you should not define a local variable in set_specialization_context() and initialize a static location with a pointer to it because the corresponding cell is lost (it is stack allocated) as soon as function set_specialization_context() returns, e.g. 

#include "dotprod.sctx.h"

void set_specialization_context(int **u, size *n)
{
  int init_u[3];

  *size = 3;
  *u = init_u; // Will put you into trouble
  (*u)[0] = 1;
  (*u)[1] = 0;
  (*u)[2] = 5;
}

See also:

Run-Time Specialization

A compile-time off-line specializer first takes the source code of a program (i.e., a set of functions and an entry point) and a description of the invariants. Analyses partition the program into fragments of code that can be evaluated knowing the invariants, and fragments of code that cannot be evaluated until run time. Then, given specialization values, the specializer yields the source code of the specialized program. This result may then be compiled to obtain a specialized executable code.

Unfortunately, this approach is not well suited to cases where the specialization values are only known at run-time. For those cases, specialization must be performed at run time. Directly reusing the traditional source-to-source program specialization would involve the use of a compiler at run-time. In most cases, because compilation is an expensive operation, this solution yields no speed up, but rather a slow down...

Run-time specialization is an extension of traditional off-line specialization. Our system uses the concept of generating extension. A traditional generating extension for a given program is a dedicated specializer that, given specialization values as input, yields the source code of the specialized program. Our generating extensions, called run-time specializers, directly produces the executable code of the specializations. A run-time specializer may be called at run time to dynamically yield specialized executable code from run-time values.

A key issue in run-time specialization is amortization, i.e. the number of time the specialized code has to be called to recover the cost of its production (because production occurs at run-time). Our approach to lower amortization is to do as much compilation as possible before run-time using code templates, leaving only the assembling of templates for run time. Additionally, we prefer to rapidly produce reasonably fast code rather than aggressively optimize the specialized code: the run-time specializer generates good code (but not optimal), very quickly. In particular, no code optimization is done at run-time.

Construction of a Run-Time Specializer

In Tempo, compile-time and run-time specialization share the same analysis up to the action analysis (although it is possible to parameterize the evaluation-time analysis specifically to get better results from run-time specialization; see lift_all and lift_global variables). Consequently, the specification of the analysis context is the same in both cases. The only difference lies in the type of programs that can be specialized as it may rely on values that are only known at run-time.

In order to build a run-time specializer, given a successful analysis (i.e. an .at file), run the rs top-level command on your program. (See Building a Run-Time Specializer.) At the moment, only gcc (or a slightly modified version of lcc) can be used for constructing a run-time specializer; see variable compiler.

The result is a compiled run-time specializer in a file suffixed with .rts.o. This file is generated in a directory named after the architecture and system of the current machine; see variable arch_dep_dir. A .rts.h file is also generated in the working directory; it contains the signature of the run-time specialization function.

Invocation of a Run-Time Specializer

In order to install the run-time specializer in your original application, just include the .rts.h header file wherever you need to call the run-time specialization function and link the .rts.o file with your application.

You get the name of the run-time specialization function by looking in the .rts.h header file, that contains its prototype. This name has the form: rts_entrypointname_suffix, e.g. 

/* TEMPO Version 1.193, 04/18/98,
  Copyright (c) IRISA/INRIA-Universite de Rennes */

extern void *rts_pow_1(int);

Using the run-time specializer is very simple: just call it with actual values for the static arguments of your entry point. It returns a pointer to the dynamically produced specialized function. E.g., 

int (*spow)(int);

x1   = pow(base,expon);
spow = rts_pow_1(expon);
x2   = (*spow)(base);

Actually, this is note pure ANCI C. This is because the prototype is not "complete". It should be: 

extern int (*((*rts_power_1)(int)))(int);

Thus, to be ANSI compilant, you would not have to write: 

spow = ((int(*((*)(int)))(int))rts_power_1)(expon);

The specialized function whose address is stored in spow is generated once, at run-time, and may be called many times to amortize the cost of generating it.

See also:

Recursive and Multiple Run-Time Specializations

In order to do multiple specializations, it is necessary to allocate new buffer space each time the specializer is called. Recursive functions have multiple specializations for the same function and thus require allocation of buffer space as well. By default, the run-time specializer allocate new buffer space each time the specializer is called and for each function. This also makes certain global variables local, so that generating extensions can be recursive to specialize recursive functions. The reentrant top-level variable can be set to false to instruct the specializer to generates code in a static buffer and returns a pointer to this buffer.

Note: The run-time specializer does not have a specialization cache and thus recursive calls with previously specialized values will cause the specializer not to terminate. For example, backward branches in a byte-code interpreter will cause an infinite loop. (See the Limitations to Run-Time Specialization.)

Allocating new space each time a generating extension is called is not always desirable, however. If the entry-point function calls a second function, for example, then two buffers will be allocated but only a pointer to the entry-point function (and thus its buffer) is returned. In this situation, the second buffer can never be deallocated. This behavior can be changed by overriding the allocation functions used by the runtime specializer. The specializer calls the functions pointed to by rts_alloc_data and rts_alloc_code to allocate data and code buffers respectively. These are global variables and can be used to override the default allocation routines (malloc).

The following is an example of overriding the allocation functions so that all code and data are allocated from different sections of a single buffer, so that the memory can be later released. 

/* Declare the function pointers for
   run-time specializer allocation */
extern char *(*rts_alloc_data)(unsigned int);
extern char *(*rts_alloc_code)(unsigned int);

/* Define some buffer sizes */
#define BUF_CODE_SIZE 500000   /* Total code buffer size */
#define FUN_CODE_SIZE 500      /* Amount of code buffer
                                    for each function */
#define BUF_DATA_SIZE 50000    /* Total data buffer size */
#define FUN_DATA_SIZE 50       /* Amount of data buffer
                                    for each function */

/* Pointers to the buffers */
char *code_buffer, *data_buffer;

/* The current positions in the buffers */
int code_pos, data_pos;

/* New allocation functions */

char *get_code_mem(unsigned int sz)
{
  char *ret;

  ret = code_buffer + code_pos;
  code_pos += FUN_CODE_SIZE;
  if (code_pos > BUF_CODE_SIZE) {
    puts("Code buffer overflow.");
    exit(1);
  }
  return ret;
}

char *get_data_mem(unsigned int sz)
{
  char *ret;

  ret = data_buffer + data_pos;
  data_pos += FUN_DATA_SIZE;
  if (data_pos > BUF_DATA_SIZE) {
    puts("Data buffer overflow.");
    exit(1);
  }
  return ret;
}

void reset_rts_buffers()
{
  code_pos=0;
  data_pos=0;
}

/* Use run-time specializer */

void main()
{
  /* Override allocation functions */
  rts_alloc_data = get_data_mem;
  rts_alloc_code = get_code_mem;

  /* Allocate buffers */
  code_buffer = (char *) malloc(BUF_CODE_SIZE);
  data_buffer = (char *) malloc(BUF_DATA_SIZE);
  reset_rts_buffers();

  /* Specialize function */
  sp = rts_myfunc_1(5);

  /* Specialize again overwriting previous specialization */
  sp = rts_myfunc_1(10);
  
  /* Release buffers */
  free(code_buffer);
  free(data_buffer);
}
 
Tuesday, 02 February 2010 08:30

Inria   LaBRI