Calculation of WCET with symbolic execution

Sammanfattning

Calculating WCET for schedulability analysis of RTIC applications is today performed with a hybrid approach with both static analysis of code and hardware measurements. A fully static analysis tool would allow for a easier integration into a CI/CD pipeline without the actual hardware. This thesis attempts to compute WCET statically, using symbolic execution engine KLEE to generate all the possible paths of execution for a task and then analyses these paths to approximate the worst-case for each path which would yield a approximate WCET for the analysed program. To analyze a path in a program the low-level intermediary assembly language used by the LLVM optimization infrastructure (called LLVM IR) is compared to the finished assembly language to draw conclusions on how an LLVM IR instruction is processed into assembly. To be able to perform this mapping from LLVM IR to assembly, the symbolic execution engine KLEE has been extended to also log each LLVM IR instruction run in a path. These logs combined with a translation table is how the approximations are calculated. The resulting approximations correlate with the actual cycles when the analysed program is run on actual hardware, which indicates that tool could actually be used to approximate WCET. There are however no guarantees and the tool has not been tested for larger scale programs.