Dynamic memory disambiguation for array references

ABSTRACT

Memory disambiguation, or alias analysis, is a key component of modern optimizing compilers. Any optimization that reorders or changes code containing memory operations must analyze the memory references to ensure that the original semantics of the program are not changed.The recent proliferation of machines able to exploit parallelism, either at the coarse grain or more commonly at the instruction level, has led to the development of sophisticated memory disambiguation algorithms. In particular, much work has been done on disambiguating array references across different loop iterations.While these algorithms can be very effective for certain classes of programs, there exists array references that cannot be disambiguated at compile time. Even references that theoretically can be disambiguated at compile time may require techniques that are much more sophisticated and expensive than currently used.In this paper, we present a new algorithm for dynamic memory disambiguation for array references that allows us to overcome limitations of static analysis. For array references that cannot be accurately analyzed at compile time, we defer the disambiguation process until run-time.We have implemented our analysis algorithm in a prototype version of the IBM XL compiler and used the generated information for several compiler optimizations: software pipelining with global instruction scheduling, loop-invariant motion and redundant load elimination. We evaluated the algorithm on an IBM POWER2 system using the SPEC92 benchmarks. We show that for numeric C benchmarks, dynamic memory disambiguation can greatly improve run-time performance. Perhaps more importantly, we show that even for the programs that cannot benefit from dynamic analysis, the overhead of our algorithm does not degrade performance.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• 3: D. Bernstein and Y. Lavon. A software pipelining algorithm based on global instruction scheduling. Technical Report TR88.338, IBM Hails, Nov 1993.
• 4: David Bernstein , Michael Rodeh, Global instruction scheduling for superscalar machines, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.241-255, June 24-28, 1991, Toronto, Ontario, Canada
• 5: M. Byler, M. Wolfe, J. Davies, C. Huson, and B. Leasure. Multiple version loops. In Proceedings of the International ConIerence on Parallel Processing, pages 312-318, 1987.
• 6: William Y. Chen , Roger A. Bringmann , Scott A. Mahlke , Sadun Anik , Tokuzo Kiyohara , Nancy J. Warter , Daniel M. Lavery , Wen-mei W. Hwu , Richard E. Hank , John C. Gyllenhaal, Using Profile Information to Assist Advaced Compiler Optimization and Scheduling, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.31-48, August 03-05, 1992
• 7: K. D. Cooper , K. Kennedy, Fast interprocedual alias analysis, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.49-59, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75282]
• 8: John R. Ellis, Bulldog: a compiler for vliw architectures (parallel computing, reduced-instruction-set, trace scheduling, scientific), 1985
• 9: P. Feautrier. Parametric integer programming. Technical Report 209, Laboratoire Methodologie and Architecture Des Systemes Informatiques, Jan 1988.
• 10: Gina Goff , Ken Kennedy , Chau-Wen Tseng, Practical dependence testing, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.15-29, June 24-28, 1991, Toronto, Ontario, Canada
• 11: L. Hendren and A. Nicolau. Parallelizing programs with recursive data structures. In international Conference on Parallel Processing, pages 49-56, August 1989.
• 12: A. S. Huang , G. Slavenburg , J. P. Shen, Speculative disambiguation: a compilation technique for dynamic memory disambiguation, Proceedings of the 21ST annual international symposium on Computer architecture, p.200-210, April 18-21, 1994, Chicago, Illinois, United States
• 13: KAP for IBM XL C User's Guide. Kuck & Associates, inc., 1993.
• 14: William Landi , Barbara G. Ryder, A safe approximate algorithm for interprocedural aliasing, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.235-248, June 15-19, 1992, San Francisco, California, United States
• 15: J. R. Larus , P. N. Hilfinger, Detecting conflicts between structure accesses, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.24-31, June 20-24, 1988, Atlanta, Georgia, United States
• 16: P. Geoffrey Lowney , Stefan M. Freudenberger , Thomas J. Karzes , W. D. Lichtenstein , Robert P. Nix , John S. O'Donnell , John Ruttenberg, The multiflow trace scheduling compiler, The Journal of Supercomputing, v.7 n.1-2, p.51-142, May 1993 [doi>10.1007/BF01205182]
• 17: Dror E. Maydan , John L. Hennessy , Monica S. Lam, Efficient and exact data dependence analysis, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.1-14, June 24-28, 1991, Toronto, Ontario, Canada
• 18: Alexandru Nicolau, Run-time disambiguation: coping with statically unpredictable dependencies, IEEE Transactions on Computers, v.38 n.5, p.633-678, May 1989
• 19: K. O'Brien, B. Itay, J. Minish, H. Schaffer, B. Schloss, A. Shepherd, and M. Zaleski. Advanced compiler technology for the RISC System/6000 architecture. In IBM RISC System/6000 Technology, pages 154-161. IBM SA23-2619, 1990.
• 20: William Pugh, The Omega test: a fast and practical integer programming algorithm for dependence analysis, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.4-13, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125848]
• 21: B. Ramakrishna Rau, Data Flow and Dependence Analysis for Instruction Level Parallelism, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.236-250, August 07-09, 1991
• 22: Gabriel M. Silberman , Kemal Ebcioglu, An Architectural Framework for Supporting Heterogeneous Instruction-Set Architectures, Computer, v.26 n.6, p.39-56, June 1993 [doi>10.1109/2.214441 ]
• 23: New cpu benchmark suites from spec. In COMPCOM, 1992.
• 24: Steven W. K. Tjiang , Michael E. Wolf , Monica S. Lam , K. Pieper , John L. Hennessy, Integrating Scalar Optimization and Parallelization, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.137-151, August 07-09, 1991
• 25: S. White, editor. IBM RiSG System/6000 Technology: Volume II. IBM, 1993.
• 26: Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Experimentation, Measurement, Performance