OpenCL programs are prone to memory and control flow divergence. When implementing OpenCL for machines with explicit SIMD instructions, compilers can usually generate more efficient code if they can prove non-divergence of memory and branch instructions. To this end, they leverage a so-called divergence analysis. However, in practice divergence is often input-dependent and exhibited for some, but not all inputs. Hence, static analyses fail to prove non-divergence. To obtain good performance, developers can manually split the input space, however this is a tedious and error prone task.
In this talk we present a new OpenCL to CPU compiler pipeline that addresses this problem by automatically ensuring divergence free control flow through program specialization. To this end we represent the full kernel as well as the implicit work item dimensions in the polyhedral model. For data dependent control flow and non-affine expression overapproximation is used. From the polyhedral iteration domains and memory access functions we can then derive conditions for the absence of memory as well as control divergence. Based one these conditions the input space is split in order to generate specialized kernel versions with beneficial divergence characteristics. Commonly large parts of the input exhibit regular access and control patterns and only a fixed size boundary of the input space does not. In such cases we can achieve speedups almost as high as the used vectorization with. However, also for non-diverging kernels our technique can improve the performance due to simplifications in the polyhedral model.
