Go to the next section.

Version 1.0

This manual is part of the SUIF compiler documentation set.

Copyright (C) 1994 Stanford University. All rights reserved.

Permission is given to use, copy, and modify this documentation for any non-commercial purpose as long as this copyright notice is not removed. All other uses, including redistribution in whole or in part, are forbidden without prior written permission.

Overview

Data dependence analysis involves analyzing the dynamic memory reference behavior of array operations so that compilers will only parallelize loops in the cases where any resultant reordering of memory references does not change the sequential semantics of the program. In general, data dependence analysis is undecidable, and compilers must conservatively approximate array reference behavior, thus sequentializing parallel loops. Traditional data dependence analysis research has concentrated on the simpler problem of affine memory disambiguation. Many algorithms have been developed that conservatively approximate even this simpler problem. By using a series of algorithms, each one guaranteed to be exact for a certain class of input. Our compiler, in practice, solves exactly and efficiently the affine memory disambiguation problem.

Go to the next section.