Static program analyses and code transformations for DSP software

Abstract

Digital Signal Processors (DSPs) are highly specialized processors designed to operate on very specific data. To enhance performance, DSPs typically support advanced architectural features, as found in the Harvard architecture, Instruction Level Parallelism, and specialized instruction sets. Traditionally, software developers have programmed DSPs in assembly language for efficiency. With more complex embedded systems and higher costs for software development, programming such systems without the support of high-level programming languages becomes impractical. However, to be efficient, code generators for DSPs require new compilation algorithms which account for the special hardware features. On the other hand, the observation that most DSPs have been programmed in assembly language gives rise to a natural desire to recover as much as possible of the large investment locked up in assembly source.<br />In this thesis we address both problems. We present static program analyses and code transformations for DSP software formulated both for high level languages and for assembly programs. In particular: (i) We present an SIMD (Single Instruction Multiple Data) generation algorithm for a C compiler whose target hardware is a digital signal processor. The algorithm is based on loop unrolling and involves an alignment analysis of the memory accesses required by SIMD instructions.<br />(ii) We present the reconstruction of control flow from DSP assembly programs. The goal of the analysis is to identify program subroutines and to construct the call graph. To verify the consistency of return addresses of the subroutines we introduce a stack analysis which reasons about the run-time stack behaviour of a program.<br />The effectiveness of our methods is substantiated by experimental results.<br />

Digitale Signalprozessoren (DSPs) sind hochspezialisierte Prozessoren, die für die Verarbeitung von spezifischen Daten entwickelt wurden. Um die Effizienz zu erhöhen, unterstützen DSPs normalerweise fortgeschrittene architekturelle Eigenschaften, wie eine Harvardarchitektur, Instruction Level Parallelism, und spezialisierte Befehlssätze. Um die Effizienz zu steigern, haben Softwareentwickler DSPs üblicherweise in Assembler programmiert. Durch immer komplexere Anwendungen und damit höheren Softwareentwicklungskosten wird die Programmierung ohne Unterstützung durch höhere Programmiersprachen nicht mehr praktikabel. Um jedoch effizient zu sein, fordern Codegeneratoren für DSPs neue Übersetzungstechniken, welche die speziellen Hardwareeigenschaften berücksichtigen. Da oft die meisten DSPs in Assembler programmiert sind, gibt es einen natürlichen Wunsch so viel Entwicklungskosten wie möglich, die in Assemblercode enthalten sind, zu bewahren.<br />In dieser Doktorarbeit behandeln wir beide Probleme. Wir stellen statische Programmanalysen und Codetransformationen für DSP Software vor, die in höheren Programmiersprachen sowie in Assembler programmiert wurde:<br />(i) Wir stellen einen SIMD (Single Instruction Multiple Data) Codeerzeugungsalgorithmus für C Übersetzer vor, dessen Zielhardware ein digitaler Signalprozessor ist. Der Algorithmus basiert auf loop unrolling und umfasst eine Ausrichtungsanalyse von Speicherzugriffen, welche durch SIMD Befehle erfordert werden.<br />(ii) Wir stellen die Rekonstruktion der Ablaufsteuerung aus DSP Assemblerprogrammen vor. Das Ziel dieser Analyse ist eine Identifikation der Unterprogramme und die Konstruktion des Aufrufgraphen. Um die Konsistenz von Rücksprungadressen der Unterprogramme zu prüfen, führen wir eine Stackanalyse ein, welche das Laufzeitverhalten eines Programms bezüglich des Stacks untersucht. Die Effizienz unserer Methoden wird durch experimentelle Ergebnisse belegt.