8th International Workshop on Worst-Case Execution Time Analysis (WCET'2008), Prague, Czech Republic, July 1, 2008

Computing Time as a Program Variable: A Way Around Infeasible Paths

Niklas Holsti


Conditional branches connect the values of program variables with the execution paths and thus with the execution times, including the worst-case execution time (WCET). Flow analysis aims to discover this connection and represent it as loop bounds and other path constraints. Usually, a specific analysis of the dependencies between branch conditions and assignments to variables creates some representation of the feasible paths, for example as IPET execution-count constraints, from which a WCET bound is calculated. This paper explores another approach that uses a more direct connection between variable values and execution time. The execution time is modeled as a program variable. An analysis of the dependencies between variables, including the execution-time variable, gives a WCET bound that excludes many infeasible paths. Examples show that the approach often works, in principle. It remains to be seen if it is scalable to real programs.

paper (pdf), presentation (pdf, OpenOffice.org source, photo of speaker)

Valid HTML 4.01 Transitional