{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T20:42:15Z","timestamp":1759092135766,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2007,8,1]],"date-time":"2007-08-01T00:00:00Z","timestamp":1185926400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2007,8]]},"abstract":"<jats:p>Existing algorithms for computing dominators are formulated for control flow graphs of single procedures. With the rise of computing power, and the viability of whole-program analyses and optimizations, there is a growing need to extend the dominator computation algorithms to context-sensitive interprocedural dominators. Because the transitive reduction of the interprocedural dominator graph is not a tree, as in the intraprocedural case, it is not possible to extend existing algorithms directly. In this article, we propose a new algorithm for computing interprocedural dominators. Although the theoretical complexity of this new algorithm is as high as that of a straightforward iterative solution of the data flow equations, our experimental evaluation demonstrates that the algorithm is practically viable, even for programs consisting of several hundred thousands of basic blocks.<\/jats:p>","DOI":"10.1145\/1255450.1255452","type":"journal-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T13:44:55Z","timestamp":1189777495000},"page":"19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["A practical interprocedural dominance algorithm"],"prefix":"10.1145","volume":"29","author":[{"given":"Bjorn","family":"De Sutter","sequence":"first","affiliation":[{"name":"Ghent University, Gent, Belgium"}]},{"given":"Ludo","family":"Van Put","sequence":"additional","affiliation":[{"name":"Ghent University, Gent, Belgium"}]},{"given":"Koen","family":"De Bosschere","sequence":"additional","affiliation":[{"name":"Ghent University, Gent, Belgium"}]}],"member":"320","published-online":{"date-parts":[[2007,8]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 1999 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE'99)","author":"Agrawal H.","year":"1999","unstructured":"Agrawal , H. 1999 . Efficient coverage testing using global dominator graphs . In Proceedings of the 1999 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE'99) . 11--20. 10.1145\/316158.316166 Agrawal, H. 1999. Efficient coverage testing using global dominator graphs. In Proceedings of the 1999 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE'99). 11--20. 10.1145\/316158.316166"},{"key":"e_1_2_1_2_1","unstructured":"Aho A. V. and Ullman J. D. 1977. Principles of Compiler Design. Addison-Wesley Reading MA.   Aho A. V. and Ullman J. D. 1977. Principles of Compiler Design. Addison-Wesley Reading MA."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of a Symposium on Compiler Optimization. ACM Press","author":"Allen F. E.","year":"1970","unstructured":"Allen , F. E. 1970 . Control flow analysis . In Proceedings of a Symposium on Compiler Optimization. ACM Press , New York, 1--19. 10.1145\/800028.808479 Allen, F. E. 1970. Control flow analysis. In Proceedings of a Symposium on Compiler Optimization. ACM Press, New York, 1--19. 10.1145\/800028.808479"},{"key":"e_1_2_1_4_1","volume-title":"Tech. Rep. RC 3923","author":"Allen F. E.","year":"1972","unstructured":"Allen , F. E. and Cocke , J . 1972 . Graph-theoretic constructs for program control flow analysis. Tech. Rep. RC 3923 , IBM T.J. Watson Research Center . Allen, F. E. and Cocke, J. 1972. Graph-theoretic constructs for program control flow analysis. Tech. Rep. RC 3923, IBM T.J. Watson Research Center."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797317263"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1274858.1274861"},{"key":"e_1_2_1_7_1","unstructured":"Cooper K. D. Harvey T. J. and Kennedy K. 2001. A simple fast dominance algorithm. Available on-line at: http:\/\/www.hipersoft.rice.edu\/grads\/publications\/dom14.pdf.  Cooper K. D. Harvey T. J. and Kennedy K. 2001. A simple fast dominance algorithm. Available on-line at: http:\/\/www.hipersoft.rice.edu\/grads\/publications\/dom14.pdf."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/115372.115320"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/998300.997194"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1086642.1086645"},{"volume-title":"Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete Algorithms. 869--878","author":"Georgiadis L.","key":"e_1_2_1_11_1","unstructured":"Georgiadis , L. and Tarjan , R. E . 2004. Finding dominators revisited: extended abstract . In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete Algorithms. 869--878 . Georgiadis, L. and Tarjan, R. E. 2004. Finding dominators revisited: extended abstract. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete Algorithms. 869--878."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1007\/978-3-540-30140-0_60","article-title":"Finding dominators in practice","volume":"3221","author":"Georgiadis L.","year":"2004","unstructured":"Georgiadis , L. , Werneck , R. , Tarjan , R. , Triantafyllis , S. , and August , D. 2004 . Finding dominators in practice . Lecture Notes in Computer Science 3221 , 677 -- 688 . Georgiadis, L., Werneck, R., Tarjan, R., Triantafyllis, S., and August, D. 2004. Finding dominators in practice. Lecture Notes in Computer Science 3221, 677--688.","journal-title":"Lecture Notes in Computer Science"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 17th Annual ACM Symposium on Theory of Computing. ACM Press, 185--194","author":"Harel D.","year":"1985","unstructured":"Harel , D. 1985 . A linear algorithm for finding dominators in flow graphs and related problems . In Proceedings of the 17th Annual ACM Symposium on Theory of Computing. ACM Press, 185--194 . 10.1145\/22145.22166 Harel, D. 1985. A linear algorithm for finding dominators in flow graphs and related problems. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing. ACM Press, 185--194. 10.1145\/22145.22166"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/357062.357071"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/362835.362838"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-024X(200101)31:1%3C67::AID-SPE357%3E3.0.CO;2-A"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the Eastern Joint Computer Conference","author":"Prosser R. T.","year":"1959","unstructured":"Prosser , R. T. 1959 . Applications of Boolean matrices to the analysis of flow diagrams . In Proceedings of the Eastern Joint Computer Conference . Spartan Books, New York, 133--138. Prosser, R. T. 1959. Applications of Boolean matrices to the analysis of flow diagrams. In Proceedings of the Eastern Joint Computer Conference. Spartan Books, New York, 133--138."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/361532.361566"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/570886.570887"},{"volume-title":"PLDI '06: Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM Press","author":"Triantafyllis S.","key":"e_1_2_1_20_1","unstructured":"Triantafyllis , S. , Bridges , M. , Raman , E. , Ottoni , G. , and August , D . 2006. A framework for unrestricted whole-program optimization . In PLDI '06: Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM Press , New York, NY, 61--71. 10.1145\/1133981.1133989 Triantafyllis, S., Bridges, M., Raman, E., Ottoni, G., and August, D. 2006. A framework for unrestricted whole-program optimization. In PLDI '06: Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM Press, New York, NY, 61--71. 10.1145\/1133981.1133989"},{"key":"e_1_2_1_21_1","volume-title":"SIGPLAN '86: Proceedings of the 1986 SIGPLAN Symposium on Compiler construction. ACM Press","author":"Wall D. W.","year":"1986","unstructured":"Wall , D. W. 1986 . Global register allocation at link time . In SIGPLAN '86: Proceedings of the 1986 SIGPLAN Symposium on Compiler construction. ACM Press , New York, NY, 264--275. 10.1145\/12276.13338 Wall, D. W. 1986. Global register allocation at link time. In SIGPLAN '86: Proceedings of the 1986 SIGPLAN Symposium on Compiler construction. ACM Press, New York, NY, 264--275. 10.1145\/12276.13338"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1255450.1255452","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1255450.1255452","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:28Z","timestamp":1750278148000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1255450.1255452"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,8]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,8]]}},"alternative-id":["10.1145\/1255450.1255452"],"URL":"https:\/\/doi.org\/10.1145\/1255450.1255452","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"type":"print","value":"0164-0925"},{"type":"electronic","value":"1558-4593"}],"subject":[],"published":{"date-parts":[[2007,8]]},"assertion":[{"value":"2007-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}