Abstract
Classical data flow analysis determines whether a data flow fact may hold or does not hold at some program point. Probabilistic data flow systems compute a range, i.e. a probability, with which a data flow fact will hold at some program point. In this paper we develop a novel, practicable framework for probabilistic data flow problems. In contrast to other approaches, we utilize execution history for calculating the probabilities of data flow facts. In this way we achieve significantly better results. Effectiveness and efficiency of our approach are shown by compiling and running the SPECint95 benchmark suite.
This research is partially supported by the Austrian Science Fund as part of Aurora Project “Languages and Compilers for Scientific Computation” under Contract SFB-011.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
F. E. Allen and J. Cocke. A program data flow analysis procedure. Communications of the ACM, 19(3):137–147, March 1976.
G. Ammons and J.R. Larus. Improving data-flow analysis with path profiles. In Proc. of the ACM SIGPLAN’ 98 Conference on Programming Language Design and Implementation (PLDI’98), pages 72–84, Montreal, Canada, June 1998.
R. Bodík, R. Gupta, and M.L. Soffa. Complete removal of redundant expressions. ACM SIGPLAN Notices, 33(5):1–14, May 1998.
A.L. Buchsbaum, H. Kaplan, A. Rogers, and J.R. Westbrook. Linear-time pointer-machine algorithms for LCAs, MST verification, and dominators. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC-98), pages 279–288, New York, May 23–26 1998. ACM Press.
B. Calder and D. Grunwald. Reducing branch costs via branch alignment. ACM SIGPLAN Notices, 29(11):242–251, November 1994.
J. A. Fisher. Trace scheduling: A technique for global microcode compaction. IEEE Trans. Comput., C-30(7):478–490, 1981.
R. Gupta, D. Berson, and J.Z. Fang. Path profile guided partial dead code elimination using predication. In International Conference on Parallel Architectures and Compilation Techniques (PACT’97), pages 102–115, San Francisco, California, November 1997.
M.S. Hecht. Flow Analysis of Computer Programs. Programming Language Series. North-Holland, 1977.
E. Mehofer and B. Scholz. Probabilistic data flow system with two-edge profiling. Workshop on Dynamic and Adaptive Compilation and Optimization (Dynamo’00). ACM SIGPLAN Notices, 35(7):65–72, July 2000.
E. Mehofer and B. Scholz. Probabilistic procedure cloning for high-performance systems. In 12th Symposium on Computer Architecture and High Performance Computing (SBAC-PAD’2000), Sao Pedro, Brazil, October 2000.
E. Mehofer and B. Scholz. Probabilistic communication optimizations and parallelization for distributed-memory systems. In PDP 2001, Mantova, Italy, February 2001.
T. C. Mowry and C.-K. Luk. Predicting data cache misses in non-numeric applications through correlation profiling. In Proceedings of the 30th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-97), pages 314–320, Los Alamitos, December 1–3 1997. IEEE Computer Society.
G. Ramalingam. Data flow frequency analysis. In Proc. of the ACM SIGPLAN’ 96 Conference on Programming Language Design and Implementation (PLDI’96), pages 267–277, Philadephia, Pennsylvania, May 1996.
T. Reps, S. Horwitz, and M. Sagiv. Precise interprocedural dataflow analysis via graph reachability. In Proc. of the ACM Symposium on Principles of Programming Languages (POPL’95), pages 49–61, San Francisco, CA, January 1995.
B. G. Ryder and M. C. Paull. Elimination algorithms for data flow analysis. ACM Computing Surveys, 18(3):277–315, September 1986.
V. C. Sreedhar, G. R. Gao, and Y.-F. Lee. A new framework for elimination-based data flow analysis using DJ graphs. ACM Transactions on Programming Languages and Systems, 20(2):388–435, March 1998.
R. E. Tarjan. Fast algorithms for solving path problems. Journal of the ACM, 28(3):594–614, July 1981.
C. Young and M. D. Smith. Better global scheduling using path profiles. In Proceedings of the 31st Annual ACM/IEEE International Symposium on Microarchitecture (MICRO-98), pages 115–126, Los Alamitos, November 30-December 2 1998. IEEE Computer Society.
C. Young and M.D. Smith. Static correlated branch prediction. ACM Transactions on Programming Languages and Systems, 21(5):1028–1075, September 1999.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mehofer, E., Scholz, B. (2001). A Novel Probabilistic Data Flow Framework. In: Wilhelm, R. (eds) Compiler Construction. CC 2001. Lecture Notes in Computer Science, vol 2027. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45306-7_4
Download citation
DOI: https://doi.org/10.1007/3-540-45306-7_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41861-0
Online ISBN: 978-3-540-45306-2
eBook Packages: Springer Book Archive