Exact vs. Approximate Array Region Analyses

Advanced program optimizations, such as array privatization, require precise array data flow analyses, usually relying on conservative over- (or may) and under- (or must) approximations of array element sets [26, 32, 21]. In a recent study [14], we proposed to compute exact sets whenever possible. But the advantages of this approach were still an open issue which is discussed in this paper. It is first recalled that must array region analyses cannot be defined on lattices. It implies that there exists no better solution for such data flow problems, and that ad-hoc solutions must be defined. For that purpose, it is suggested to perform under- and over-approximate analyses at the same time, and to enhance the results of must analyses with those of may analyses, when the latter can be proved exact according to an exactness criterion. This is equivalent to our previous approach, and is more effective than using only traditional techniques such as widening and narrowing operators which may..