Compiler analysis of irregular memory accesses

Irregular array accesses are array accesses whose array subscripts do not h ave closed-form expressions in terms of loop indices. Traditional array ana lysis and loop transformation techniques cannot handle irregular array acce sses. In this paper, we study two kinds of simple and common cases of irreg ular array accesses: single-indexed access and indirect array access. We pr esent techniques to analyze these two cases at compile-time, and we provide experimental results showing the effectiveness of these techniques in find ing more implicit loop parallelism at compile-time and improved speedups.