ILP-based path analysis on abstract pipeline state graphs

Abstract

This thesis presents a novel approach to path analysis which is an integral part of the WCET analysis. Up to now, there have been two different methods for this step, each with its respective advantages and disadvantages. The new ILP-based path analysis on abstract pipeline state graphs supersedes the existing ones and combines the positive aspects of both but does not introduce new limitations. It provides high precision and the flexibility of user-provided annotations at the same time while opening up new possibilities for optimizations such as a new kind of persistence analysis.

Diese Arbeit präsentiert einen innovativen Ansatz für die Pfadanalyse, ein integraler Bestandteil der WCET-Analyse. Bisher gab es zwei verschiedene Methoden für diesen Schritt, jede mit ihren spezifischen Vor- und Nachteilen. Die neue ILP-basierte Pfadanalyse auf abstrakten Pipelinezustandsgraphen ersetzt die beiden existierenden und kombiniert die positiven Aspekte, ohne neue Beschränkungen einzuführen. Sie bietet sowohl eine hohe Präzision als auch die Flexibilität benutzerbestimmter Annotationen. Darüber hinaus bietet sie neue Optimierungsmöglichkeiten wie zum Beispiel eine neuartige Persistenzanalyse.