DETECTING VALUE-BASED SCALAR DEPENDENCE

Precise value-based data dependence analysis for scalars is useful for advanced compiler optimizations. The new method presented here for fl ow and output dependence uses Factored Use and Def chains (FUD chains) , our interpretation and extension of Static Single Assignment. It is precise with respect to conditional control flow and dependence vector s. Our method detects dependences which are independent with respect t o arbitrary loop nesting, as well as loop-carried dependences. A loop- carried dependence is further classified as being carried from the pre vious iteration, with distance 1, or from any previous iteration, with direction <. This precision cannot be achieved by traditional analysi s, such as dominator information or reaching definitions. To compute a nti- and input dependence, we use Factored Redef-Use chains, which are related to FUD chains. We are not aware of any prior work which expli citly deals with scalar data dependence utilizing a sparse graph repre sentation.