{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:39:11Z","timestamp":1750307951214,"version":"3.41.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2007,10,1]],"date-time":"2007-10-01T00:00:00Z","timestamp":1191196800000},"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,10]]},"abstract":"<jats:p>\n            Interprocedural data flow analysis extends the scope of analysis across procedure boundaries in search of increased optimization opportunities. Call strings based approach is a general approach for performing flow and context sensitive interprocedural analysis. It maintains a history of calls along with the data flow information in the form of call strings, which are sequences of unfinished calls. Recursive programs may need infinite call strings for interprocedural data flow analysis. For bit vector frameworks this method is believed to require all call strings of lengths up to 3\n            <jats:italic>K<\/jats:italic>\n            , where\n            <jats:italic>K<\/jats:italic>\n            is the maximum number of distinct call sites in any call chain.\n          <\/jats:p>\n          <jats:p>\n            We combine the nature of information flows in bit-vector data flow analysis with the structure of interprocedurally valid paths to bound the call strings. Instead of bounding the length of call strings, we bound the number of occurrences of any call site in a call string. We show that the call strings in which a call site appears at most three times, are sufficient for convergence on interprocedural maximum fixed point solution. Though this results in the same worst case length of call strings, it does not require constructing all call strings up to length 3\n            <jats:italic>K<\/jats:italic>\n            . Our empirical measurements on recursive programs show that our bound reduces the lengths and the number of call strings, and hence the analysis time, significantly.\n          <\/jats:p>","DOI":"10.1145\/1286821.1286829","type":"journal-article","created":{"date-parts":[[2007,11,15]],"date-time":"2007-11-15T14:26:02Z","timestamp":1195136762000},"page":"38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["An improved bound for call strings based interprocedural analysis of bit vector frameworks"],"prefix":"10.1145","volume":"29","author":[{"given":"Bageshri","family":"Karkare","sequence":"first","affiliation":[{"name":"IIT Bombay"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Uday P.","family":"Khedker","sequence":"additional","affiliation":[{"name":"IIT Bombay"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1177220"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Alt M.\n     and \n      \n      \n      Martin F\n      \n  \n  . \n  1995\n  . Generation of Efficient Interprocedural Analyzers with PAG. In Proceedings of Static Analysis Symposium (SAS'95) Lecture Notes in Computer Science vol. \n  983 Springer 33--50.   Alt M. and Martin F. 1995. Generation of Efficient Interprocedural Analyzers with PAG. In Proceedings of Static Analysis Symposium (SAS'95) Lecture Notes in Computer Science vol. 983 Springer 33--50.","DOI":"10.1007\/3-540-60360-3_31"},{"key":"e_1_2_1_3_1","unstructured":"Alt M. Martin F. and Wilhelm R. 1995. Generating Dataflow Analyzers with PAG. Tech. rep. A 10\/95 Universit\u00e4t des Saarlandes.  Alt M. Martin F. and Wilhelm R. 1995. Generating Dataflow Analyzers with PAG. Tech. rep. A 10\/95 Universit\u00e4t des Saarlandes."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/12276.13327"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/178243.178264"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/512976.512979"},{"key":"e_1_2_1_7_1","unstructured":"Hecht M. S. 1977. Flow Analysis of Computer Programs. Elsevier Science Inc.   Hecht M. S. 1977. Flow Analysis of Computer Programs. Elsevier Science Inc."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00290339"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575467_20"},{"volume-title":"The Compiler Design Handbook","author":"Khedker U. P.","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/186025.186043"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/512927.512945"},{"key":"e_1_2_1_13_1","unstructured":"Muchnick S. S. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers Inc. San Francisco CA.   Muchnick S. S. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers Inc. San Francisco CA."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/567532.567556"},{"key":"e_1_2_1_15_1","unstructured":"Pande H. Landi W. and Ryder B. 1992. Interprocedural reaching definitions in the presence of single level pointers. Tech. rep. lost-tr-193 Laboratory for Computer Science Research Rutgers University.  Pande H. Landi W. and Ryder B. 1992. Interprocedural reaching definitions in the presence of single level pointers. Tech. rep. lost-tr-193 Laboratory for Computer Science Research Rutgers University."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199462"},{"key":"e_1_2_1_17_1","unstructured":"Sharir M. and Pnueli A. 1981. Two approaches to interprocedural data flow analysis. In Program Flow Analysis: Theory and Applications S. S. Muchnick and N. D. Jones Eds. Prentice-Hall Inc.  Sharir M. and Pnueli A. 1981. Two approaches to interprocedural data flow analysis. In Program Flow Analysis: Theory and Applications S. S. Muchnick and N. D. Jones Eds. Prentice-Hall Inc."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/996841.996859"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1286821.1286829","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1286821.1286829","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:57:49Z","timestamp":1750258669000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1286821.1286829"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10]]},"references-count":18,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2007,10]]}},"alternative-id":["10.1145\/1286821.1286829"],"URL":"https:\/\/doi.org\/10.1145\/1286821.1286829","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"type":"print","value":"0164-0925"},{"type":"electronic","value":"1558-4593"}],"subject":[],"published":{"date-parts":[[2007,10]]},"assertion":[{"value":"2007-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}