Tempo Specializer - Limitations

Caution: The limitations listed in this document are not meant to be exhaustive.

• Missing Features
  • Input language
  • Aliases and casts
  • Mutually recursive structure declarations
  • Binding-time imprecision due to goto elimination
  • Identifier naming in compile-time specialization
  • Multiple compile-time specialization
  • Run-time specialization
• Preservation of the Semantics
  • Off-line partial evaluators
  • Naming of identifiers
  • Initializations
  • Run-time specialization
• Improvements Gained by Specialization
• Plans for the Future

Some features are missing in Tempo. Though some of them are still challenges, others are just due to a (relative) lack of manpower.

• Bit fields,
• Switch,
• Functions with a variable number of arguments.

For the time being, in order to guarantee that the alias analysis will produce correct results, the following rules should be obeyed:

1. Pointer arithmetic can only be applied to pointers pointing to the contents of an array. (A warning is raised.)

2. The only scalar that can be cast to a pointer is 0, i.e. the pointer NULL pointer. (A fatal error is raised: Tempo stops.)

3. Casting a pointer to a pointer is allowed only if the pointed objects are scalars. (A pointer is a scalar.) A warning is raised when the target type is not a pointer to a scalar.

4. If a pointer to a structure or union is cast to another pointer type it should be considered ``opaque'' (i.e. not dereferenced, neither for reading nor writing) until it is cast back into the original type.

All cast restrictions apply to unions that are used as casts, i.e. when an object is stored in the union under a certain name (and type) and retrieved under another name.

Some of these limitations are due to the monovariance of the alias analysis, others to the lack of a store model in Tempo. (Locations rely on names rather than physical, even abstract, memory.)

In order to express non-opaque casts between structure types (as may be needed for object-oriented programming), consider modeling them explicitly as abstract functions in the actx.c analysis context file.

For the analysis to be correct, Tempo has to know all the possible aliases of locations if they have an impact on the semantics. This can also specified using the actx.c analysis context file.

int if_test(int S, int D)
{
  int x,y;

  if (S > 32) goto L33;
  x=150;
  if (D > 32) goto L38;
  y=100;
  goto L38;
L33:
  x=200;
L38:
  return x + y;
}

int if_test(int S, int D)
{
  int x,y;

  if (S <= 32) {
    x = 150;
    if (D <= 32) {
      y = 100;
    }
  else x = 200;
  return x + y;
}

extern int if_test_1/*0*/(int S, int D)  {
    int goto1_L33;
    int goto1_L38;
    int x;
    int y;

    goto1_L33 = 0;
    goto1_L38 = 0;
    goto1_L33 = 32 < S;
    if (! goto1_L33)
      {
        x = 150;
      }

    if (goto1_L33 || 32 >= D)
      {
        if (! goto1_L33)
          {
            y = 100;
            goto1_L38 = 1;
          }

        if (! goto1_L38)
          {
            goto1_L33 = 0;
            x = 200;
          }

      }
    goto1_L38 = 0;
    return x + y;
  }

int if_test(int S, int D)
{
  int x,y;

  if (S > 32) goto L33;
  x=150;
  if (D > 32) goto L27;
  y=100;
  goto L38;
L27:
  y=45;
  goto L38;
L33:
  x=200;
L38:
  return x + y;
}

extern int if_test_1/*0*/(int S, int D)  {
    int goto1_L27;
    int goto1_L33;
    int goto1_L38;
    int x;
    int y;

    goto1_L27 = 0;
    goto1_L33 = 0;
    goto1_L38 = 0;
    if (32 >= S)
      {
        x = 150;
        if (32 >= D)
          {
            y = 100;
            goto1_L38 = 1;
          }
        if (! goto1_L38)
          {
            goto1_L27 = 0;
            y = 45;
            goto1_L38 = 1;
          }
      }

    if (! goto1_L38 && ! goto1_L38)
      {
        goto1_L33 = 0;
        x = 200;
      }
    goto1_L38 = 0;
    return x + y;
  }

Essentially the problem is that because else branches are not introduced by the goto elimination, dynamic tests are introduced to jump over the else branch of the static conditional in all cases that can result from taking its then branch.

The PORKY_DEFAULTS and PORKY_PRE_DEFAULTS phases of Suif rearrange goto statements in a way that can also be detrimental to binding times. In many cases, these options can be turned off (which is the default for the current version of Tempo), but in some cases porky will not work if these phases have not been performed.

In the current implementation of the compile-time specializer, global names are renamed during specialization. This can cause problems if they are external, or are referenced externally during specialization.

The renaming of global variables is controlled by the .sctx.h file, which for the global variable var might contain a definition akin to:

#define var _store.var

One solution is to only give Tempo the relevant program slice during analysis, and then give it the whole program during specialization. This allows any redefinitions in the sctx.h file to take effect without incurring a large overhead (unless the program is very large). Of course, this only works if source code is available for the whole program, and may require some minor rewriting of the program. Other alternative solutions include referencing such variables through functions or to copy their value when the specialization starts.

This problem is likely to be removed in a future version, by avoiding any renaming of variables during specialization.

There is no specific support for multiple compile-time specialization. In particular, when linking simultaneously different specializations, redundant definitions may appear. They must be removed by hand. Similarly, useless declarations may occur.

Note that identifiers are renamed by compile-time specialization. Global identifier are prefixed with _G, local identifiers are prefixed with _L (or _Y for nested block declarations) and the name of the function they belong to.

• Store management in rebuilt conditionals
• Management of specializations, i.e. no memoization or memory reuse

Only gcc and a slightly modified version of lcc can be used for constructing a run-time specializer; see variable compiler.

• Tempo is stuck if a static expression loops. If that expression happens to be dead code (remember that this is undecidable), Tempo will loop whereas the original program terminates.
• If a static expression raises an error (like division by zero), Tempo's behavior is unpredictable but probably wrong.

As mentioned above, there is no store management in the run-time specialization. This can produce an incorrect result from run-time specialization. A conditional statement is annotated ``rebuild'' when the test is dynamic by there is code that can be evaluated during specialization in one of the branches. In compile-time specialization, when specializing each branch the store is initialized to the store that existed just after specializing the conditional test. Thus the static side-effects in one branch have no influence on the other branch. This is not the case for run-time specialization. In run-time specialization the store that exists at the end of specializing the first branch is the store that is used to specialize the second branch. This strategy can lead to wrong results, as illustrated by the following example:

x=1;
if(Dyn)
{
  x=2;
  f(x);
}
else
{
  g(x);
}

if(Dyn)
{
  f(2);
}
else
{
  g(2);
}

if(Dyn)
{
  f(2);
}
else
{
  g(1);
}

Note that no warning will be issued. If such a situation is spotted, one possible workaround is to prevent speculative evaluation by turning dynamic the dangerous side-effects.

Another effect of the lack of store management is that there is no memoization of the current store when specializing a function. This is in contrast with compile-time specialization that able to recognize that a function has already been specialized (or is being specialized) and to yield a call to that specialized function rather than invoking the specializer anew. As a result, run-time specialization may loop if the specialized function is recursive. This is typically the case when specializing interpreters with backward jumps. There are workarounds though; see Recursive and Multiple Run-Time Specializations in the User's Manual.

• As is the case for most program transformations, even though it respects the operational semantics, specialization may alter the cache's behavior. This can have large (positive or negative) impact on modern architectures.

• Cache impact is important in particular for loop unrolling. As Tempo blindly evaluates any static expression, it will unroll all static loops, whether large or small. Not only the program can be much bigger, but the instruction cache behavior can be very bad.

• Initializations are turned into explicit assignments so that Tempo can work on a smaller C subset. While theoretically less efficient (execution time and program size), this has not been a problem in practice in our examples.

The following features are being considered for the next releases of Tempo. Some are already implemented in large part and being tested. They are listed in order of likeliness to be released soon.

1. Switch
2. Inlining at run time
3. User-refined memory management (compile-time specialization)
4. Data specialization
5. More efficient compile-time specialization
6. Structure (and union) polyvariance
7. Better handling of casts

Tempo currently relies on version 0.93 of SML New Jersey (see the SML Environment). This is quite an old version, that in particular performs very badly on PCs. We plan to port it on the new version 110, offering thus not only better performances but also support for Windows.

• Users' mailing list: tempo-talk@irisa.fr
• Developers and maintainers: tempo@irisa.fr
• Compose project home page: http://compose.labri.fr
• Tempo Specializer home page: tempo