Analyzable language

Heptane analyzes programs written in the C programming language (programs that can be compiled by a Gnu C compiler).

Some restrictions on the source code are required to identify the worst-case execution path of a program. On the one hand, the use of function pointers is forbidden in order to identify called functions statically. On the other hand, features that may cause unstructured control flow graphs (i.e. control flow graphs that are not compatible with the syntax tree) are not allowed. Such features are for instance the use of the goto construct and the inclusion of assembly code that contains branching instructions. This restriction comes from the fact that our analysis highly relies on the program syntax.

Loop annotations

Finding the WCET of a loop requires a knowledge of the maximum number of loop iterations. Heptane requires the user to give this information through annotations in the source program. Annotations are designed to support nested loops whose number of iterations depends on the counter variables of outer loops (see our publications on WCET analysis).

unsigned NumberOfBitsNeeded(unsigned PowerOfTwo)
{
    unsigned        i, res;
    for (i = 0; PowerOfTwo == 1; i++) [11, i] {
        PowerOfTwo = PowerOfTwo / 2;
        res = i;
    }
    return res;
}
 

unsigned ReverseBits(unsigned index, unsigned NumBits)
{
    unsigned        i, rev;
    for (i = rev = 0; i < NumBits; i++) [10, i] {
        rev = (rev << 1) | (index & 1);
        index = (index >> 1);
    }
    return rev;
}
 

void fft()
{
    unsigned        NumSamples = 2048;
    double          RealIn[2048];
    double          ImagIn[2048];
    double          RealOut[2048];
    double          ImagOut[2048];
    double          SINTAB[11][2];
    unsigned        NumBits;
    unsigned        i, j, sin_index, k, n;
    unsigned        BlockSize, BlockEnd;
    double          angle_numerator = 2.0 * (3.14159265358979323846);
    double          delta_angle;
    double          alpha, beta;
    double          delta_ar;
    double          tr, ti;
    double          ar, ai;
    SINTAB[0][0] = 1.0;
    SINTAB[0][1] = 0.0;
    SINTAB[1][0] = 0.707107;
    SINTAB[1][1] = 1.000000;
    SINTAB[2][0] = 0.382683;
    SINTAB[2][1] = 0.707107;
    SINTAB[3][0] = 0.195090;
    SINTAB[3][1] = 0.382683;
    SINTAB[4][0] = 0.098017;
    SINTAB[4][1] = 0.195090;
    SINTAB[5][0] = 0.049068;
    SINTAB[5][1] = 0.098017;
    SINTAB[6][0] = 0.024541;
    SINTAB[6][1] = 0.049068;
    SINTAB[7][0] = 0.012272;
    SINTAB[7][1] = 0.024541;
    SINTAB[8][0] = 0.006136;
    SINTAB[8][1] = 0.012272;
    SINTAB[9][0] = 0.003068;
    SINTAB[9][1] = 0.006136;
    SINTAB[10][0] = 0.001534;
    SINTAB[10][1] = 0.003068;

    NumBits = NumberOfBitsNeeded(NumSamples);

    for (i = 0; i < NumSamples; i++) [2048, i] {
        j = ReverseBits(i, NumBits);
        RealOut[j] = RealIn[i];
        ImagOut[j] = ImagIn[i];
    }

    BlockEnd = 1;
    sin_index = 0;

    for (BlockSize = 2; BlockSize <= NumSamples; BlockSize = BlockSize << 1)
    [11, pow(2, (i + 1))] {
        delta_angle = angle_numerator / (double) BlockSize;
        alpha = SINTAB[sin_index][0];
        alpha = 2.0 * alpha * alpha;
        beta = SINTAB[sin_index][1];
        sin_index++;

        for (i = 0; i < NumSamples; i += BlockSize) [(2048 / nlast(P, 1)), i * nlast(P, 1)] {
            ar = 1.0;
            ai = 0.0;
 
           for (j = i, n = 0; n < BlockEnd; j++, n++) [nlast(P, 2) / 2, i] {
                k = j + BlockEnd;
                tr = ar * RealOut[k] - ai * ImagOut[k];
                ti = ar * ImagOut[k] + ai * RealOut[k];
                RealOut[k] = RealOut[j] - tr;
                ImagOut[k] = ImagOut[j] - ti;
                RealOut[j] += tr;
                ImagOut[j] += ti;
                delta_ar = alpha * ar + beta * ai;
                ai -= (alpha * ai - beta * ar);
                ar -= delta_ar;
           }
        }
        BlockEnd = BlockSize;
    }
}