Skip to main content
Springer Nature Link
Log in

Detecting value-based scalar dependence

  • Published:
Save article
View saved research
International Journal of Parallel Programming Aims and scope Submit manuscript

Abstract

Precise value-based data dependence analysis for scalars is useful for advanced compiler optimizations. The new method presented here for flow 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 vectors. Our method detects dependences which are independent with respect to arbitrary loop nesting, as well as loop-carried dependences. A loop-carried dependence is further classified as being carried from the previous iteration, with distance 1, or from any previous iteration, with direction <. This precision cannot be achieved by traditional analysis, such as dominator information or reaching definitions. To compute anti- and input dependence, we use Factored Redef-Use chains, which are related to FUD chains. We are not aware of any prior work which explicitly deals with scalar data dependence utilizing a sparse graph representation.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+
from €37.37 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Price includes VAT (Netherlands)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

References

  1. Chau-Wen Tseng, An optimizing Fortran D compiler for MIMD distributed-memory machines. PhD. Dissertation TR93-199, Rice University, Department of Computer Science (January 1993).

  2. Paul Feautrier, Dataflow analysis of array and scalar references.Intl. Journal of Parallel Programming 20(1):23–54 (1991).

    Article  MATH  Google Scholar 

  3. J. R. Allen, Dependence analysis for subscripted variables and its application to program transformations. PhD. dissertation, Rice University, Department of Mathematical Sciences. (April 1983). (available from University Microfilms Inc., Document 83-14916).

  4. John R. Allen and Ken Kennedy, Automatic translation of Fortran programs to vector form.ACM Trans. on Programming Language and Systems 9(4):491–542 (October 1987).

    Article  MATH  Google Scholar 

  5. Michael Wolfe, Optimizing supercompilers for supercomputers. PhD. Dissertation UIUCDCS-R-82-1105, University Illinois, Department Computer Science (October 1982) (available from University Microfilms Inc., document 83-03027).

  6. Michael Wolfe and Utpal Banerjee, Data dependence and its application to parallel processingInt. J. Parallel Programming 16(2):137–178 (April 1987).

    Article  MATH  MathSciNet  Google Scholar 

  7. Vadim Maslov, Lazy array data-flow dependence analysis. InConf. Record 21st Annual ACM Symp. Principles of Programming Languages, Portland, Oregon, pp. 311–325 (January 1994).

  8. Michael Burke, Ron Cytron, Jeanne Ferrante, and Wilson Hsieh, Automatic generation of nested, fork-join parallelism.The Journal of Supercomputing,3(2):71–88 (July 1989).

    Article  Google Scholar 

  9. Michael Wolfe, Techniques for improving the inherent parallelism in programs. M. S. thesis UIUCDCS-R-78-929, University Illinois, Department Computer Science (July 1978).

  10. Michael Wolfe,Optimizing Supercompilers for Supercomputers. Research Monographs in Parallel and Distributed Computing. Pitman Publishing. London, 1989. (also available from MIT Press).

    MATH  Google Scholar 

  11. Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zedeck. Efficiently computing Static Single Assignment form and the control dependence graph.ACM Trans. on Programming Languages and Systems,13(4):451–490 (October 1991).

    Article  Google Scholar 

  12. Michael P. Gerlek, Eric Stoltz, and Michael Wolfe, Beyond induction variables: Detecting and classifying sequences using a demand-driven SSA form. To appear inTOPLAS (1995).

  13. Eric Stoltz. Michael Wolfe, and Michael P. Gerlek, Constant propagation: A fresh, demand-driven look. InSymposium on Applied Computing. ACM SIGAPP, Phoenix, Arizona (March 1994).

  14. Richard Johnson and Keshav Pingali, Dependence-based program analysis. InProc. ACM SIGPLAN '93 Conf. on Programming Language Design and Implementation, Albuquerque, New Mexico, pp. 78–89 (June 1993).

  15. Robert A. Ballance, Arthur B. Maccabe, and Karl J. Ottenstein, The Program Dependence Web: A representation supporting control-, data-, and demand-driven interpretation of imperative languages.

  16. Jong-Deok Choi, Ron Cytron, and Jeanne Ferrante, On the efficient engineering of ambitious program analysis.IEEE Trans. on Software Engineering 20(2):105–114 (February 1994).

    Article  Google Scholar 

  17. Eric Stoltz,Intermediate Compiler Analysis via Reference Chaining. PhD. thesis, Department of Computer Science and Engineering, Oregon Graduate Institute of Science & Technology (January 1995).

  18. Eric Stoltz, Michael P. Gerlek, and Michael Wolfe, Extended SSA with factored use-def chains to support optimization and parallelism. InProc. of 27th Annual Hwaii Intl. Conf. on Syst. Sci., pp. 43–52 (January 1994).

  19. A. V. Aho, R. Sethi, and J. D. Ullman,Compilers: Principles, Techniques, and Tools. Addison-Wesley, Reading, Massachusetts (1986).

    Google Scholar 

  20. George Cybenko, Lyle Kipp. Lynn Pointer, and David Kuck, Supercomputer performance evaluation and the Perfect Benchmarks. InIntl. Conf. on Supercomputing, pp. 254–266 (March 1990).

  21. Jong-Deok Choi, Ron Cytron, and Jeanne Ferrante, Automatic construction of sparse data flow evaluation graphs. InConf. Record 18th Annual ACM Symp. Principles of Programming Languages, Orlando, Florida, pp. 55–66 (January 1991).

  22. Michael E. Wolf, Improving locality and parallelism in nested loops. PhD. Dissertation COMP TR. CSL-TR-92-538, Stanford University, Department Computer Science (August 1992).

  23. Paul Havlak. Interprocedural Symbolic Analysis. PhD. thesis, Department of Computer Science, Rice University (1994).

Download references

Author information

Author notes

  1. Eric Stoltz

    Present address: Convex Computer Corporation, 3000 Waterview Parkway, 75080, Richardson, Texas

Authors and Affiliations

  1. Department of Computer Science and Engineering, Oregon Graduate Institute of Science & Technology, P.O. Box 91000, 97291-1000, Portland, Oregon

    Eric Stoltz & Michael Wolfe

Authors
  1. Eric Stoltz
    View author publications

    Search author on:PubMed Google Scholar

  2. Michael Wolfe
    View author publications

    Search author on:PubMed Google Scholar

Additional information

A preliminary version of this paper appeared in theSeventh Anual Workshop on Languages and Compilers for Parallel Computing, August 1994.

Supported in part by NSF Grant CCR-9113885 and a grant from Intel Corporation and the Oregon Advanced Computing Institute.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Stoltz, E., Wolfe, M. Detecting value-based scalar dependence. Int J Parallel Prog 23, 327–358 (1995). https://doi.org/10.1007/BF02577770

Download citation

  • Received:

  • Issue date:

  • DOI: https://doi.org/10.1007/BF02577770

Key Words