Towards execution Time estimation in abstract machine-based (Logic) languages

Abstract machines provide a certain separation between platform-dependent and platform-independent concerns in compilation. Many of the differences between architectures are encapsulated in the specific abstract machine implementation and the bytecode is left largely architecture independent. Taking advantage of this fact, we present a framework for estimating upper and lower bounds on the execution times of logic programs running on a bytecode-based abstract machine. Our approach includes a one-time, program-independent profiling stage which calculates constants or functions bounding the execution time of each abstract machine instruction. Then, a compiletime cost estimation phase, using the instruction timing information, infers expressions giving platform-dependent upper and lower bounds on actual execution time as functions of input data sizes for each program. Working at the abstract machine level allows taking into account lowlevel issues without having to tailor the analysis for each architecture and platform, and instead only having to redo the calibration step. Applications of such predicted execution times include debugging/verification of time properties, granularity control in parallel/distributed computing, and resource-oriented specialization