A Context-Parameterized Model for Static Analysis of Execution Times

摘要

The static analysis of the execution time of a program (i.e. the evaluation of this time for any input data set) can be useful for the purpose of optimizing the code or verifying that strict real-time deadlines can be met. This analysis generally goes through determining the execution times of partial execution paths, typically basic blocks. Now, as soon as the target processor architecture features a superscalar pipeline, possibly with dynamic instruction scheduling, the execution time of a basic block highly depends on the pipeline state, that is on the instructions executed before it. In this paper, we propose a model to specify the local execution context of a basic block as a set of parameters. The execution time of the block can then be computed as a function of these parameters. We show how this model can be used to determine an upper bound of the execution time of a basic block, that can be used for computing the Worst-Case Execution Time of the program. Experimental results give an insight into the tightness of the estimations.