Program Analysis for Performance Evaluation
From PUMA Graduiertenkolleg
Static analysis has been traditionally employed to compute functional information about a program. One obtains local invariants, i.e., invariants that hold at a particular program point. To compute these invariants one defines an adequate lattice of abstract values, say A, and a mapping that attaches to each program execution an element of A. Under certain circumstances those invariants can be characterized as the least solution of a system of fixed point equations; it can be computed (or at least approximated) by worklist algorithms.
The same technique can be applied to performance questions. The most prominent example is perhaps the WCET (worst-case execution time) analysis. In WCET analysis the abstract values are natural numbers (CPU cycles); the invariant at a program point p is defined as the runtime of the longest execution path leading to p. However, performance questions concerning the average behaviour of the program, like average execution time or memory consumption, cannot be cast into the classical framework. The technical reason is that the operator that combines the values of different program executions is no longer idempotent. This constitutes a fundamental difference between worst-case and average behaviour.
While the classical framework can be extended to accommodate non-idempotent operators, the corresponding worklist algorithms are inefficient. We have provided a mathematical framework allowing to solve this problem. It extends Newton's method, a well-known technique from numerical analysis. From a theoretical point of view the framework has not yet been fully developed. The framework raises many new questions, particularly concerning its algorithmics. An exciting topic is especially the development and optimization of worklist algorithms that efficiently compute the Newton approximants.
From an applications point of view we develop a powerful generic engine that allows to perform various combinations of performance and functional analysis. More specifically, such a method will be able to compute high probability invariants, i.e., assertions that may be violated only by very unlikely program executions. We also envision applications outside the program analysis realm, particularly in the area of reputation systems.
see "Andreas Gaiser