This section provides a brief explanation of data dependence - the criterion that KAP uses to determine if a given loop can be optimized. KAP determines dependences between variables and arrays in loop iterations and bases decisions on this information automatically, informing you in the listing file only of those dependences that prevent optimization.
The study of data dependence analysis was originally motivated by parallel (vector and concurrent) computation. The techniques and notations are applicable to advanced serial transformations for uniprocessor computers.
KAP uses a data dependence graph that shows where data values are generated and where they are used within a loop or loop nest. The data dependence graph is processed with standard graph traversal techniques to find potential problem areas, which appear as cycles in the graph. Each data dependence cycle is carefully examined to see if it can be broken and the loop executed in parallel, or if part or all of the loop must be executed serially.
For an in-depth study of data dependence, consult the following: