This thesis examines the problem of determining the bound on the running time of a given program on a given processor. An important aspect of this problem is determining the extreme case program paths. It is a very hard problem to explicitly enumerate all possible paths because the number of paths is typically exponential in the size of the program. In this thesis, a solution for this problem is presented, which considers all paths implicitly by using integer linear programming.
To use ILP, it is necessary to extract the CFG(Control Flow Graph) of the program. Usually, a CFG of a program can be constructed by using the object code of the program as input. But in this thesis, GCC intermediate representation(RTL) of a program has been used instead of the object code to construct CFG.
After constructing the CFG, program structural constraints of ILP must be derived. A rather inexact solution can be obtained from these constraints. But more exact solution could be obtained by adding more constraints. These added constraints are from program functionality and the static branch predictions.
It is found that the estimated number of executions by the method proposed in this work is very exact when compared with the number of executions measured by inputting the data that would follow the extreme case path. And the result is presented here.
