| © 1998 IRISA / INRIA - University of Rennes 1 |
Version |
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.
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:
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:
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:
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:
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
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
variable := value
val variable = value
- 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
- 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")
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";
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.
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"))
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.
Modular specialization supports for specializing a fragment of an application. It is explained through the following definitions.
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).
main() function.
printf() or strcpy().
Behavior of External Functionsbelow for more details.
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.
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.
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.
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.
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.
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...
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.
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.
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.
Array Monovariancebelow),
Structure Monovariancebelow).
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
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
The alias analysis computes the set of possible targets for pointer locations and expressions. This analysis is:
The side-effect analysis computes the set of non-locals variables that are read or written in each function. This analysis is:
The binding-time analysis annotates the program with binding-time information. This analysis is:
Array Monovariance. There is a single location of all instances of a given structured type (structure or union); see
Structure Monovariance.
The evaluation-time analysis make the binding-time analysis use-sensitive:
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.
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:
In order to parameterize the analyses, the user must provide Tempo with the following compulsory information.
In addition, the user may provide the following information.
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.
wd
variable, as in
wd := "/home/jake/spec/misc";
cd
command, as in
cd "/home/jake/spec/misc";
wd. By default, the working
directory is the directory in which Tempo is run, unless the shell
variable TEMPOWORK is
defined.
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";
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.
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.
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)
extern; all other specialized functions are made
static (in the C sense). You have to manually
turn those specifiers into extern.
specialized_entry_point_name).
The sub entry points have to be renamed by hand, if desired.
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.
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.
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"];
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"];
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"];
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.
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"];
static_locations := ["pt.x"];
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[].
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.
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.
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
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.
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.
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.
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.
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
}
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;
}
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
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.
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:
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.
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:
set_analysis_context() function (if any)
with arguments that are pointers to the original entry-point
arguments.
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.
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.
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.
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.)
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 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 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.
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:
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 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: max_width
(width of displayed code)
max_decls_size
(threshold for declarations ellipsis)
print_dir_in_html_title
(display path in HTML title)
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:
verbose_aliases
(display alias information)
verbose_aliases_in_specializations
verbose_callsig
(display polyvariance index)
verbose_headers
(display signature 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 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 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.
There two meanings for the pink color, according to the phase
SD_FUNC (static and dynamic function).
Such calls will eventually be flattened in a subsequent phase.
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).
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 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.
The legend in ".at.color" files, that express the results of the Action Analysis phase, is:
/* LEGEND: EVAL REDUCE REBUILD IDENTITY STRUCTURE EV&RES */
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.
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 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.
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.
A function call looks like this:
bar/*7*/(statexp, dynexp, (sdexp))
The corresponding binding-time information can be read as follows.
bar(...)
/*7*/
statexp, dynexp, (sdexp)
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.
int
foo
/*3*/
(...)
int stat, int dyn
{...}
return ...
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.
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:
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.
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:
live_locations
Tempo variable, or residualized via the
set_post_analysis_context() function.
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:
.at file).
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:
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.
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:
.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.
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 <math.h>
#include <stdio.h>
#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.
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:
ctcg_cflags
(flags for the C/C++ compiler)
ctcg_ldflags
(flags for the link editor)
ctcg_ldflags
(additional libraries)
sh_command
(shell setting)
default_cts_bufsize
(default buffer size for the specializer)
explicit_cts_bufsize
(buffer size for the specializer)
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.
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.
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.
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);
}
tempo-talk@irisa.fr
tempo@irisa.fr
http://compose.labri.fr
tempo