Static Worst-Case Execution Time (WCET) analysisis a technique to derive upper bounds for the executiontimes of programs. Such bounds are crucialwhen designing and verifying real-time systems. A keycomponent for static derivation of precise WCET estimatesis upper bounds on the number of times differentloops can be iterated.In this paper we present an approach for derivingupper loop bounds based on a combination of standardprogram analysis techniques. The idea is to bound thenumber of different states in the loop which can influencethe exit conditions. Given that the loop terminates,this number provides an upper loop bound.An algorithm based on the approach has been implementedin our WCET analysis tool SWEET. We evaluatethe algorithm on a number of standard WCETbenchmarks, giving evidence that it is capable to derivevalid bounds for many types of loops.
展开▼