Jens Knoop
Abstract
We present a bit-vector algorithm for the optimal and economical placement of computations within flow graphs, which is as efficient as standard uni-directional analyses. The point of our algorithm is the decomposition of the bi-directional structure of the known placement algorithms into a sequence of a backward and a forward analysis, which directly implies the efficiency result. Moreover, the new compositional structure opens the algorithm for modification: two further uni-directional analysis components exclude any unnecessary code motion. This laziness of our algorithm minimizes the register pressure, which has drastic effects on the run-time behaviour of the optimized programs in practice, where an economical use of registers is essential.
- AU Aho, A. V., and Ullman, J.D. Node listings for reducible flow graphs. In Proceedings ?~h STOC, 1975, 177- 185. Google Scholar
Digital Library
- Ch Chow, F. A portable machine independent optimizer- Design and measurements. Ph.D. dissertation, Dept. of Electrical Engineering, Stanford University, Stanford, Calif., and Tech. Rep. 83-254, Computer Systems Lab., Stanford University, 1983. Google ScholarDigital Library
- Dh1 Dhamdhere, D.M. Characterization of program loops in code optimization. Comp. Lang. 8, 2 (1983), 69- 76.Google Scholar
- Dh2 Dhamdhere, D.M. A fast algorithm for code movement optimization. S~GPLAN Not. 23, 10 (xgss), 172- is0 Google ScholarDigital Library
- Dh3 Dhamdhere, D.M. Practical adaptation of the global optimization algorithm of Morel and Renvoise. A CM Trans. Program. Lang. Syst. ~3, 2 (~99~), 29~- 294. Google ScholarDigital Library
- DS Drechsler, K. H., and Stadel, M.P. A solution to a problem with Morel and Renvoise's "Global optimization by suppression of partial redundancies". A CM Trans. Program. Lang. Syst. 10, 4 (1988), 635 - 640. Google ScholarDigital Library
- GW Graham, S. L., and Wegman, M. A fast and usually linear algorithm for global flow analysis. Journal of the ACM 23, 1 (1976), 172- 202. Google ScholarDigital Library
- He Itecht, M.S. Flow analysis of computer programs. Elsevier, North-Holland, 1977. Google ScholarDigital Library
- HU1 Hecht, M. S., and Ullman, J.D. Analysis of a simple algorithm for global flow problems. In Proceedings 1st POPL, Boston, Massachusetts, 1973, 207- 217. Google ScholarDigital Library
- HU2 Hecht, M. S., and Ullman, J.D. A simple algorithm for global data flow analysis problems. In SIAM J. Comput. d, 4 (1977), 519- 532.Google Scholar
- JD1 Joshi, S. M., and Dhamdhere, D.M. A composite hoisting-strength reduction transformation for global program optimization- part I. Internat. J. Computer Maih. 11, (1982), 21 - 41.Google ScholarCross Ref
- JD2 Joshi, S. M., and Dhamdhere, D.M. A composite hoisting-strength reduction transformation for global program optimization- part II. Internat. J. Computer Math. 11, (1982), 111- 126.Google ScholarCross Ref
- Ke Kennedy, K. Node listings applied to data flow analysis. In Proceedings ~d POPL, Palo Alto, California, 1975, 10- 21. Google ScholarDigital Library
- KRS Knoop, J., Riithing, O., and Steffen, B. Lazy strength reduction. To appear.Google Scholar
- KS1 Knoop, J., and Steffen, B. The interprocedurM coincidence theorem. Aachener Informafik- Berichte Nr. 9127, Rheinisch-Westfiilische Technische Hochschule Aachen, Aachen, 1991.Google Scholar
- KS2 Knoop, J., and Steffen, B. Efficient and optimal interprocedural bit-vector data flow analyses: A uniform interprocedural framework. To appear.Google Scholar
- KU1 Kam, J. B., and Ullman, J.D. Global data flow analysis and iterative algorithms, journal o/the ACM 23, 1 (1976), 158- 171. Google ScholarDigital Library
- KU2 Kam, J. B., and Ullman, j.D. Monotone data flow analysis frameworks. Acta Informatica 7, (1977), 309- 317.Google ScholarDigital Library
- Mo Morel, E. Data flow analysis and global optimization. In: Lorho, B. (Ed.). Methods and tools for compiler construction, Cambridge University Press, 1984. Google ScholarDigital Library
- MR1 Morel, E., and Renvoise, C. Global{ optimization by suppression of partial redundancies. Commun. of the A CM 22, 2 (1979), 96- 103. Google ScholarDigital Library
- MR2 Morel, E., and Renvoise, C. Interprocedural elimination of partial redundancies. In: Muchnick, St. S., and Jones, N. D. (Eds.). Program flow analysis: Theory and applications. Prentice Hall, Englewood Cliffs, NJ, 1981.Google Scholar
- RWZ Rosen, B. K., Wegman, M. N., and Zadeck,F. K. Global value numbers and redundant computations. In Proceedings 15th POPL, San Diego, California, 1988, 12- 27. Google ScholarDigital Library
- So Sorkin, A. Some comments on A solution to a problem with Morel and Renvoise's "Global optimization by suppression of partial redundancies''. A CM Trans. Program. Lang. $yst. 11,4 (1989), 666- 668. Google ScholarDigital Library
- St Steffen, B. Data flow analysis as model checking. In Proceedings TACS'91, Sendai, Japan, Springer-Verlag, LNCS 526 (1991), 346 .-364. Google ScholarDigital Library
- SKR1 Steffen, B., Knoop, J., and Riithing, O. The value flow graph: A program representation for optimal program transformations. In Proceedings 3~d E$OP, Copenhagen, Denmark, Springer-Verlag, LNCS 432 (1990), 389 .-405. Google ScholarDigital Library
- SKR2 Steffen, B., Knoop, J., and Riithing, O. Efficient code motion and an adaption to strength reduction. In Proceedings ~ta TAP- SOFT, Brighton, United Kingdom, Springer- Verlag, LNCS 494 (1991), 394- 415. Google ScholarDigital Library
- Ta1 Tarjan, R.E. Applications of path compression on balanced trees. Journal of lhe A CM 26, 4 (1979), 690- 715. Google ScholarDigital Library
- Ta2 Tarjan, R.E. A unified approach to path problems. Journal of the A CM 28, 3 (1981), 577- 593. Google ScholarDigital Library
- Ta3 Tarjan, R.E. Fast algorithms for solving path problems. Journal of the A CM 28, 3 (:1981), 594- 614. Google ScholarDigital Library
- Ull Ullman, J.D. Fast algorithms for the elimination of common subexpressions. Acia Informaiica 2, 3 (1973), 191- 213.Google ScholarDigital Library
Index Terms
- Lazy code motion
Recommendations
Lazy code motion
PLDI '92: Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementationWe present a bit-vector algorithm for the optimal and economical placement of computations within flow graphs, which is as efficient as standard uni-directional analyses. The point of our algorithm is the decomposition of the bi-directional structure of ...
Lazy code motion
20 Years of the ACM SIGPLAN Conference on Programming Language Design and Implementation 1979-1999: A SelectionWe present a bit-vector algorithm for the optimal and economical placement of computations within flow graphs, which is as efficient as standard uni-directional analyses. The point of our algorithm is the decomposition of the bi-directional structure of ...
Lazy BTB: reduce BTB energy consumption using dynamic profiling
ASP-DAC '06: Proceedings of the 2006 Asia and South Pacific Design Automation ConferenceIn this paper, we propose an alternative BTB design, called lazy BTB, to reduce the BTB energy consumption by filtering out the redundant lookups. The most distinct feature of the lazy BTB is that it dynamically profiles the taken traces during program ...
Comments