{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T18:03:56Z","timestamp":1773943436981,"version":"3.50.1"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2005,6]]},"abstract":"<jats:p>It has long been known that a fixed ordering of optimization phases will not produce the best code for every application. One approach for addressing this phase-ordering problem is to use an evolutionary algorithm to search for a specific sequence of phases for each module or function. While such searches have been shown to produce more efficient code, the approach can be extremely slow because the application is compiled and possibly executed to evaluate each sequence's effectiveness. Consequently, evolutionary or iterative compilation schemes have been promoted for compilation systems targeting embedded applications where meeting strict constraints on execution time, code size, and power consumption is paramount and longer compilation times may be tolerated in the final stage of development, when an application is compiled one last time and embedded in a product. Unfortunately, even for small embedded applications, the search process can take many hours or even days making the approach less attractive to developers. In this paper, we describe two complementary general approaches for achieving faster searches for effective optimization sequences when using a genetic algorithm. The first approach reduces the search time by avoiding unnecessary executions of the application when possible. Results indicate search time reductions of 62%, on average, often reducing searches from hours to minutes. The second approach modifies the search so fewer generations are required to achieve the same results. Measurements show this approach decreases the average number of required generations by 59%. These improvements have the potential for making evolutionary compilation a viable choice for tuning embedded applications.<\/jats:p>","DOI":"10.1145\/1071604.1071607","type":"journal-article","created":{"date-parts":[[2005,8,1]],"date-time":"2005-08-01T17:31:42Z","timestamp":1122917502000},"page":"165-198","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":41,"title":["Fast and efficient searches for effective optimization-phase sequences"],"prefix":"10.1145","volume":"2","author":[{"given":"Prasad A.","family":"Kulkarni","sequence":"first","affiliation":[{"name":"Florida State University, Tallahassee, FL"}]},{"given":"Stephen R.","family":"Hines","sequence":"additional","affiliation":[{"name":"Florida State University, Tallahassee, FL"}]},{"given":"David B.","family":"Whalley","sequence":"additional","affiliation":[{"name":"Florida State University, Tallahassee, FL"}]},{"given":"Jason D.","family":"Hiser","sequence":"additional","affiliation":[{"name":"University of Virginia, Charlottesville, VA"}]},{"given":"Jack W.","family":"Davidson","sequence":"additional","affiliation":[{"name":"University of Virginia, Charlottesville, VA"}]},{"given":"Douglas L.","family":"Jones","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}]}],"member":"320","published-online":{"date-parts":[[2005,6]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"LCTES '04: Proceedings of the 2004 ACM SIGPLAN\/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems. ACM Press","author":"Almagor L.","unstructured":"Almagor , L. , Cooper , K. D. , Grosul , A. , Harvey , T. J. , Reeves , S. W. , Subramanian , D. , Torczon , L. , and Waterman , T . 2004. Finding effective compilation sequences . In LCTES '04: Proceedings of the 2004 ACM SIGPLAN\/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems. ACM Press , New York. 231--239. 10.1145\/997163.997196 Almagor, L., Cooper, K. D., Grosul, A., Harvey, T. J., Reeves, S. W., Subramanian, D., Torczon, L., and Waterman, T. 2004. Finding effective compilation sequences. In LCTES '04: Proceedings of the 2004 ACM SIGPLAN\/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems. ACM Press, New York. 231--239. 10.1145\/997163.997196"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the SIGPLAN'88 Conference on Programming Language Design and Implementation. ACM Press","author":"Benitez M. E.","unstructured":"Benitez , M. E. and Davidson , J. W . 1988. A portable global optimizer and linker . In Proceedings of the SIGPLAN'88 Conference on Programming Language Design and Implementation. ACM Press , New York. 329--338. 10.1145\/53990.54023 Benitez, M. E. and Davidson, J. W. 1988. A portable global optimizer and linker. In Proceedings of the SIGPLAN'88 Conference on Programming Language Design and Implementation. ACM Press, New York. 329--338. 10.1145\/53990.54023"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 1994 International Conference on Programming Languages and Architectures. 105--124","author":"Benitez M. E.","unstructured":"Benitez , M. E. and Davidson , J. W . 1994. The advantages of machine-dependent global optimization . In Proceedings of the 1994 International Conference on Programming Languages and Architectures. 105--124 . Benitez, M. E. and Davidson, J. W. 1994. The advantages of machine-dependent global optimization. In Proceedings of the 1994 International Conference on Programming Languages and Architectures. 105--124."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the SIGPLAN '95 Conference on Programming Language Design and Implementation. 79--92","author":"Calder B.","year":"2071","unstructured":"Calder , B. , Grunwald , D. , and Lindsay , D . 1995. Corpus-based static branch prediction . In Proceedings of the SIGPLAN '95 Conference on Programming Language Design and Implementation. 79--92 . 10.1145\/ 2071 10.207118 Calder, B., Grunwald, D., and Lindsay, D. 1995. Corpus-based static branch prediction. In Proceedings of the SIGPLAN '95 Conference on Programming Language Design and Implementation. 79--92. 10.1145\/207110.207118"},{"key":"e_1_2_1_5_1","volume-title":"Proc. 2nd Workshop on Feedback Directed Optimization.","author":"Chow K.","unstructured":"Chow , K. and Wu , Y . 1999. Feedback-directed selection and characterization of compiler optimizatons . Proc. 2nd Workshop on Feedback Directed Optimization. Chow, K. and Wu, Y. 1999. Feedback-directed selection and characterization of compiler optimizatons. Proc. 2nd Workshop on Feedback Directed Optimization."},{"key":"e_1_2_1_6_1","volume-title":"Workshop on Languages, Compilers, and Tools for Embedded Systems. 1--9. 10","author":"Cooper K. D.","unstructured":"Cooper , K. D. , Schielke , P. J. , and Subramanian , D . 1999. Optimizing for reduced code space using genetic algorithms . In Workshop on Languages, Compilers, and Tools for Embedded Systems. 1--9. 10 .1145\/314403.314414 Cooper, K. D., Schielke, P. J., and Subramanian, D. 1999. Optimizing for reduced code space using genetic algorithms. In Workshop on Languages, Compilers, and Tools for Embedded Systems. 1--9. 10.1145\/314403.314414"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015729001611"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing. Springer-Verlag","author":"Gao G. R.","unstructured":"Gao , G. R. , Olsen , R. , Sarkar , V. , and Thekkath , R . 1993. Collective loop fusion for array contraction . In Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing. Springer-Verlag , London. 281--295. Gao, G. R., Olsen, R., Sarkar, V., and Thekkath, R. 1993. Collective loop fusion for array contraction. In Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing. Springer-Verlag, London. 281--295."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the ACM SIGPLAN 1992 Conference on Programming Language Design and Implementation. ACM Press","author":"Granlund T.","unstructured":"Granlund , T. and Kenner , R . 1992. Eliminating branches using a superoptimizer and the GNU C compiler . In Proceedings of the ACM SIGPLAN 1992 Conference on Programming Language Design and Implementation. ACM Press , New York, San Francisco, CA. 341--352. 10.1145\/143095.143146 Granlund, T. and Kenner, R. 1992. Eliminating branches using a superoptimizer and the GNU C compiler. In Proceedings of the ACM SIGPLAN 1992 Conference on Programming Language Design and Implementation. ACM Press, New York, San Francisco, CA. 341--352. 10.1145\/143095.143146"},{"key":"e_1_2_1_10_1","volume-title":"Proc. 4th Workshop of Feedback-Directed and Dynamic Optimization.","author":"Granston E. D.","unstructured":"Granston , E. D. and Holler , A . 2001. Automatic recommendation of compiler options . In Proc. 4th Workshop of Feedback-Directed and Dynamic Optimization. Granston, E. D. and Holler, A. 2001. Automatic recommendation of compiler options. In Proc. 4th Workshop of Feedback-Directed and Dynamic Optimization."},{"key":"e_1_2_1_11_1","volume-title":"IEEE 4th Annual Workshop on Workload Characterization. 10","author":"Guthaus M. R.","year":"2001","unstructured":"Guthaus , M. R. , Ringenberg , J. S. , Ernst , D. , Austin , T. M. , Mudge , T. , and Brown , R. B . 2001. MiBench: A free, commercially representative embedded benchmark suite . IEEE 4th Annual Workshop on Workload Characterization. 10 .1109\/WWC. 2001 .15 Guthaus, M. R., Ringenberg, J. S., Ernst, D., Austin, T. M., Mudge, T., and Brown, R. B. 2001. MiBench: A free, commercially representative embedded benchmark suite. IEEE 4th Annual Workshop on Workload Characterization. 10.1109\/WWC.2001.15"},{"key":"e_1_2_1_12_1","volume-title":"Adaptation in Natural and Artificial Systems","author":"Holland J. H.","unstructured":"Holland , J. H. 1975. Adaptation in Natural and Artificial Systems . University of Michigan Press , Ann Arbor, MI . Holland, J. H. 1975. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI."},{"key":"e_1_2_1_13_1","volume-title":"POPL '88: Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM Press","author":"Irigoin F.","unstructured":"Irigoin , F. and Triolet , R . 1988. Supernode partitioning . In POPL '88: Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM Press , New York. 319--329. 10.1145\/73560.73588 Irigoin, F. and Triolet, R. 1988. Supernode partitioning. In POPL '88: Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM Press, New York. 319--329. 10.1145\/73560.73588"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2000.888348"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 2003 ACM SIGPLAN Conference on Language, Compiler, and Tool for Embedded Systems. ACM Press","author":"Kulkarni P.","unstructured":"Kulkarni , P. , Zhao , W. , Moon , H. , Cho , K. , Whalley , D. , Davidson , J. , Bailey , M. , Paek , Y. , and Gallivan , K . 2003. Finding effective optimization phase sequences . In Proceedings of the 2003 ACM SIGPLAN Conference on Language, Compiler, and Tool for Embedded Systems. ACM Press , New York. 12--23. 10.1145\/780732.780735 Kulkarni, P., Zhao, W., Moon, H., Cho, K., Whalley, D., Davidson, J., Bailey, M., Paek, Y., and Gallivan, K. 2003. Finding effective optimization phase sequences. In Proceedings of the 2003 ACM SIGPLAN Conference on Language, Compiler, and Tool for Embedded Systems. ACM Press, New York. 12--23. 10.1145\/780732.780735"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the ACM SIGPLAN '04 Conference on Programming Language Design and Implementation. ACM Press","author":"Kulkarni P.","unstructured":"Kulkarni , P. , Hines , S. , Hiser , J. , Whalley , D. , Davidson , J. , and Jones , D . 2004. Fast searches for effective optimization phase sequences . In Proceedings of the ACM SIGPLAN '04 Conference on Programming Language Design and Implementation. ACM Press , New York. 10.1145\/996841.996863 Kulkarni, P., Hines, S., Hiser, J., Whalley, D., Davidson, J., and Jones, D. 2004. Fast searches for effective optimization phase sequences. In Proceedings of the ACM SIGPLAN '04 Conference on Programming Language Design and Implementation. ACM Press, New York. 10.1145\/996841.996863"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the Second International Conference on Architectual Support for Programming Languages and Operating Systems. IEEE Computer Society Press","author":"Massalin H.","year":"1987","unstructured":"Massalin , H. 1987 . Superoptimizer: a look at the smallest program . In Proceedings of the Second International Conference on Architectual Support for Programming Languages and Operating Systems. IEEE Computer Society Press . Washington, DC, Palo Alto, CA. 122--126. 10.1145\/36206.36194 Massalin, H. 1987. Superoptimizer: a look at the smallest program. In Proceedings of the Second International Conference on Architectual Support for Programming Languages and Operating Systems. IEEE Computer Society Press. Washington, DC, Palo Alto, CA. 122--126. 10.1145\/36206.36194"},{"key":"e_1_2_1_18_1","volume-title":"Workshop on Profile and Feedback Directed Compilation.","author":"Nisbet A.","year":"1998","unstructured":"Nisbet , A. 1998 . Genetic algorithm optimized parallelization . Workshop on Profile and Feedback Directed Compilation. Nisbet, A. 1998. Genetic algorithm optimized parallelization. Workshop on Profile and Feedback Directed Compilation."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/JRPROC.1961.287814"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation. ACM Press","author":"Stephenson M.","year":"2003","unstructured":"Stephenson , M. , Amarasinghe , S. , Martin , M. , and O'Reilly , U.-M. 2003 . Meta optimization: improving compiler heuristics with machine learning . In Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation. ACM Press , New York. 77--90. 10.1145\/781131.781141 Stephenson, M., Amarasinghe, S., Martin, M., and O'Reilly, U.-M. 2003. Meta optimization: improving compiler heuristics with machine learning. In Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation. ACM Press, New York. 77--90. 10.1145\/781131.781141"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the International Symposium on Code Generation and Optimization. IEEE Computer Society","author":"Triantafyllis S.","unstructured":"Triantafyllis , S. , Vachharajani , M. , Vachharajani , N. , and August , D. I . 2003. Compiler optimization-space exploration . In Proceedings of the International Symposium on Code Generation and Optimization. IEEE Computer Society , Washington, DC. 204--215. Triantafyllis, S., Vachharajani, M., Vachharajani, N., and August, D. I. 2003. Compiler optimization-space exploration. In Proceedings of the International Symposium on Code Generation and Optimization. IEEE Computer Society, Washington, DC. 204--215."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 15th Annual Workshop on Microprogramming. IEEE Press","author":"Vegdahl S. R.","year":"1982","unstructured":"Vegdahl , S. R. 1982 . Phase coupling and constant generation in an optimizing microcode compiler . In Proceedings of the 15th Annual Workshop on Microprogramming. IEEE Press , Palo Alto, CA. 125--133. Vegdahl, S. R. 1982. Phase coupling and constant generation in an optimizing microcode compiler. In Proceedings of the 15th Annual Workshop on Microprogramming. IEEE Press, Palo Alto, CA. 125--133."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(00)00086-7"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/267959.267960"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/360128"},{"key":"e_1_2_1_26_1","volume-title":"ACM SIGPLAN Conference on Languages, Compilers, and Tools for Embedded Systems. ACM","author":"Zhao W.","unstructured":"Zhao , W. , Cai , B. , Whalley , D. , Bailey , M. , van Engelen , R. , Yuan , X. , Hiser , J. , Davidson , J. , Gallivan , K. , and Jones , D . 2002. Vista: A system for interactive code improvement . In ACM SIGPLAN Conference on Languages, Compilers, and Tools for Embedded Systems. ACM , New York. 155--164. 10.1145\/513829.513857 Zhao, W., Cai, B., Whalley, D., Bailey, M., van Engelen, R., Yuan, X., Hiser, J., Davidson, J., Gallivan, K., and Jones, D. 2002. Vista: A system for interactive code improvement. In ACM SIGPLAN Conference on Languages, Compilers, and Tools for Embedded Systems. ACM, New York. 155--164. 10.1145\/513829.513857"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1071604.1071607","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T13:16:58Z","timestamp":1672233418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1071604.1071607"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,6]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,6]]}},"alternative-id":["10.1145\/1071604.1071607"],"URL":"https:\/\/doi.org\/10.1145\/1071604.1071607","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,6]]},"assertion":[{"value":"2005-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}