Automatic SIMD vectorization of SSA-based control flow graphs ; Automatische SIMD Vektorisierung von SSA-basierten Steuerflussgraphen (German)

Applications that require the same computation to be performed on huge amounts of data play an important role in today’s computing landscape: Particle simulations, stock option price estimation, and video decoding are some examples for such data-parallel programs. Languages like OpenCL and CUDA facilitate their development. They allow to write a scalar function that is executed on different input values in parallel by a runtime system. To unleash the full parallel potential of modern processors, the compiler and runtime system of these languages then have to make use of all available cores as well as SIMD instructions: These allow to efficiently execute a single operation on multiple input values at once per core. This thesis presents Whole-Function Vectorization (WFV), an approach that allows a compiler to automatically exploit SIMD instructions in data-parallel settings. Without WFV, one processor core executes a single instance of a data-parallel function. WFV transforms the function to execute multiple instances at once using SIMD instructions. For simple, straight-line code, the transformation is easily applied and delivers drastically improved performance. However, problems such as particle simulations or shading in computer graphics exhibit more complex code. We show that in such scenarios, a na¨ive WFV approach will often not improve performance or even slow down execution. The focus of this thesis is to present an advanced WFV algorithm that includes a variety of analyses and code generation techniques that help to improve the generated code. An implementation of WFV has been evaluated in different settings: First, in a stand-alone OpenCL runtime system. Second, in a compiler for domain-specific languages used in real-time ray tracing. Third, in a compiler that performs classic loop vectorization upon request by the user. In all scenarios, WFV improves performance compared to state-of-the-art approaches. The performance of the OpenCL implementation is on par with the proprietary Intel driver, and faster ...