3. A Second Issue: Control of Execution Time

We present here an example of the compatibility problems, not at the interface level but at a lower level. This problem is illustrated with the control of the execution times of analyses in PIPS (See the author's thesis for PIPS and the libraries mentioned below).

Being an underlying component of PIPS, the library $C^3$ uses POLYLIB as an external library to perform polyhedral operations. To control the execution times of $C^3$, a timeout mechanism is added by the author. This mechanism requires modifications of certain functions of POLYLIB, e.g. Chernikova function. We here present several possible implementations and several functional interfaces. Then we propose a solution which we wished to implement in the POLYLIB's Chernikova function but we could not obtain a general agreement. This mechanism could be added to the magnitude control, i.e. integer overflow, which is already implemented in POLYLIB.

The pre-existing operators in the $C^3$ library, such as boolean sc_feasibility_ofl_ctrl() , boolean sc_projection_ofl_ctrl() and Psysteme sc_convex_hull() , or POLYLIB's void chernikova() that is used by $C^3$, did not have a timeout mechanism properly established. Some analyses can last a long time whereas the abstract interpretation enables us to sacrifice the precision to obtain speed. The activation of this timeout mechanism in $C^3$ with the example ocean.f has grealty reduced PIPS execution time, from three days to three hours with TRANSFORMER_INTER_FULL, PRECONDITIONS_INTER_FULL, MUST_REGIONS analyses .

Moreover, the execution times of some algorithms can be very sensitive to non-semantic modifications of the parameters, for example the order of successive projections of a set of variables. The exponential complexity of some operators can yield durations of some tens of seconds to hours, with no differences in the final result.

If an operation may last a long time, we want to put a timeout so that its execution finishes within a time limit set by the programmer. But we also want to preserve the current functionality. That is possible using one of the two solutions as follows:

• Implementation of an "alarm" call, which will stop the operation when the timeout is reached. The routine handling an exception is launched by the means of a longjump and can position a flag which is tested later on in the operator;
• Modification of POLYLIB so that it supports timeout management.

For the call of a throw_exception using a longjump, we have a problem. If the main process is executing a malloc, i.e. allocation of memory, or a system call, the memory context is probably incoherent, which can lead to a core dump.

This first approach has however an advantage: it is not necessary to modify the operator implementation itself. It is enough to add a layer of wrapping. If in the process, there is no malloc or system calls, we can take the risk to use a longjump. If there is, we must modify the code somewhere in the operation, for example the main loop. The new code should take into account the existence of the flag. The disadvantages are: 1, a modification of the existing code which can be in an external library, such as for example POLYLIB; 2, a slightly slower algorithm since it is necessary to test the flag for timeouts in one, or several, main loops of the initial algorithm.

One can directly use a throw_exception in the case where there is no malloc, by releasing the memory used in CATCH. For the convex hull operator with many calls to malloc, or the satisfiability test using the simplex method with memory allocation of a hash table, we must modify the code.

The implementation of the additional code can be hidden by a mechanism of #ifdef which allows us to generate two versions of the original operator. This complicates the non-regression tests but guarantees the absence of changes for those who do not need the timeouts.

The second solution, which requires an activation of the timeout mechanism, is preferable. By default, the timeout mechanism is not active. To allow the use or not of the timeout, there are at least two possibilities in the implementation: 1, specify the timeout by using one or more variables of the environment, i.e. one always uses the same signatures of operators; or 2, establish a new interface that takes into account the timeout as additional parameters and additional pieces of code if a timeout took place. With 1, the old interface is preserved and used in a wrapper which can activate or not the mechanism of timeout. With 2, the old operator is modified to accept the necessary additional parameters.

However, POLYLIB does not support this approach in general ; in this way we can see the human-factor complexity of the problems. Consequently, in order to use the timeout in Psysteme sc_convex_hull , we must choose the first solution. POLYLIB has the same mechanism for exception management using TRY/CATCH as the $C^3$ library, which is used at CRI, thus the solution was implemented by the author without difficulty.

As mentioned above, in this chapter we propose a new interface (4_sec:HQ_interface), and then compare it to existing interfaces. However, POLYLIB is not considered , since its interface is a subset of the other four that we have chosen which are $C^3$'s, New POLKA's, Octagon's, whose interface was based on New POLKA's, and PPL's. In the next section, we present a comparison between the octagonal and the polyhedral interfaces.