{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T23:56:14Z","timestamp":1743119774280,"version":"3.40.3"},"publisher-location":"Cham","reference-count":45,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319527086"},{"type":"electronic","value":"9783319527093"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-52709-3_13","type":"book-chapter","created":{"date-parts":[[2017,1,23]],"date-time":"2017-01-23T07:13:25Z","timestamp":1485155605000},"page":"153-168","source":"Crossref","is-referenced-by-count":1,"title":["Formalizing Structured Control Flow Graphs"],"prefix":"10.1007","author":[{"given":"Amit","family":"Sabne","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Putt","family":"Sakdhnagool","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rudolf","family":"Eigenmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,1,24]]},"reference":[{"key":"13_CR1","unstructured":"Control flow structuring without code explosion [Under Submission]"},{"key":"13_CR2","unstructured":"Omni OpenMP benchmarks (2016). http:\/\/www.hpcs.cs.tsukuba.ac.jp\/omni-compiler\/download\/download-benchmarks.html . Accessed 11 Mar 2016"},{"key":"13_CR3","volume-title":"Compilers: Principles, Techniques, and Tools","author":"AV Aho","year":"1986","unstructured":"Aho, A.V., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools. Addison-Wesley Longman Publishing Co., Inc., Boston (1986)"},{"issue":"3","key":"13_CR4","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1145\/360018.360025","volume":"19","author":"FE Allen","year":"1976","unstructured":"Allen, F.E., Cocke, J.: A program data flow analysis procedure. Commun. ACM 19(3), 137 (1976). http:\/\/doi.acm.org\/10.1145\/360018.360025","journal-title":"Commun. ACM"},{"key":"13_CR5","doi-asserted-by":"crossref","unstructured":"Allen, F.E.: Control flow analysis. In: Proceedings of a Symposium on Compiler Optimization, pp. 1\u201319. ACM, New York (1970). http:\/\/doi.acm.org\/10.1145\/800028.808479","DOI":"10.1145\/800028.808479"},{"key":"13_CR6","doi-asserted-by":"crossref","unstructured":"Allen, J.R., Kennedy, K., Porterfield, C., Warren, J.: Conversion of control dependence to data dependence. In: Proceedings of the 10th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL 1983, pp. 177\u2013189. ACM, New York (1983). http:\/\/doi.acm.org\/10.1145\/567067.567085","DOI":"10.1145\/567067.567085"},{"issue":"3","key":"13_CR7","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1109\/32.126773","volume":"18","author":"Z Ammarguellat","year":"1992","unstructured":"Ammarguellat, Z.: A control-flow normalization algorithm and its complexity. IEEE Trans. Softw. Eng. 18(3), 237\u2013251 (1992). http:\/\/dx.doi.org\/10.1109\/32.126773","journal-title":"IEEE Trans. Softw. Eng."},{"key":"13_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/978-3-642-54807-9_8","volume-title":"Compiler Construction","author":"J Anantpur","year":"2014","unstructured":"Anantpur, J., R., G.: Taming control divergence in GPUs through control flow linearization. In: Cohen, A. (ed.) CC 2014. LNCS, vol. 8409, pp. 133\u2013153. Springer, Heidelberg (2014). doi: 10.1007\/978-3-642-54807-9_8"},{"key":"13_CR9","unstructured":"Ashcroft, E.A., Manna, Z.: The translation of \u2018go to\u2019 programs to \u2018while\u2019 programs. In: IFIP Congress, no. 1, pp. 250\u2013255 (1971)"},{"issue":"1","key":"13_CR10","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1145\/321992.321999","volume":"24","author":"BS Baker","year":"1977","unstructured":"Baker, B.S.: An algorithm for structuring flowgraphs. J. ACM 24(1), 98\u2013120 (1977). http:\/\/doi.acm.org\/10.1145\/321992.321999","journal-title":"J. ACM"},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Blackham, B., Heiser, G.: Sequoll: A framework for model checking binaries. In: 2013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), pp. 97\u2013106, April 2013","DOI":"10.1109\/RTAS.2013.6531083"},{"issue":"5","key":"13_CR12","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1145\/355592.365646","volume":"9","author":"C B\u00f6hm","year":"1966","unstructured":"B\u00f6hm, C., Jacopini, G.: Flow diagrams, turing machines and languages with only two formation rules. Commun. ACM 9(5), 366\u2013371 (1966). http:\/\/doi.acm.org\/10.1145\/355592.365646","journal-title":"Commun. ACM"},{"key":"13_CR13","unstructured":"Carter, L., Ferrante, J., Thomborson, C.D.: Folklore confirmed: reducible flow graphs are exponentially larger. In: Conference Record of POPL 2003: The 30th SIGPLAN-SIGACT Symposium on Principles of Programming Languages, New Orleans, Louisisana, USA, 15-17 January 2003, pp. 106\u2013114 (2003). http:\/\/doi.acm.org\/10.1145\/640128.604141"},{"issue":"5","key":"13_CR14","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1145\/953395.953398","volume":"13","author":"N Chapin","year":"1978","unstructured":"Chapin, N., Denniston, S.P.: Characteristics of a structured program. SIGPLAN Not. 13(5), 36\u201345 (1978). http:\/\/doi.acm.org\/10.1145\/953395.953398","journal-title":"SIGPLAN Not."},{"key":"13_CR15","volume-title":"Surreptitious Software: Obfuscation, Watermarking, and Tamperproofing for Software Protection","author":"C Collberg","year":"2009","unstructured":"Collberg, C., Nagra, J.: Surreptitious Software: Obfuscation, Watermarking, and Tamperproofing for Software Protection, 1st edn. Addison-Wesley Professional, Boston (2009)","edition":"1"},{"key":"13_CR16","unstructured":"Collberg, C., Thomborson, C., Low, D.: A taxonomy of obfuscating transformations (1997)"},{"key":"13_CR17","doi-asserted-by":"crossref","unstructured":"Collberg, C., Thomborson, C., Low, D.: Manufacturing cheap, resilient, and stealthy opaque constructs. In: Proceedings of the 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 1998. ACM, New York (1998). http:\/\/doi.acm.org\/10.1145\/268946.268962","DOI":"10.1145\/268946.268962"},{"key":"13_CR18","unstructured":"Division, N.A.S.: NAS Parallel Benchmarks (2016). https:\/\/www.nas.nasa.gov\/publications\/npb.html\/ . Accessed 11 March 2016"},{"key":"13_CR19","doi-asserted-by":"crossref","unstructured":"Erosa, A., Hendren, L.: Taming control flow: a structured approach to eliminating goto statements. In: Proceedings of the 1994 International Conference on Computer Languages, pp. 229\u2013240, May 1994","DOI":"10.1109\/ICCL.1994.288377"},{"issue":"3","key":"13_CR20","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1145\/321832.321835","volume":"21","author":"MS Hecht","year":"1974","unstructured":"Hecht, M.S., Ullman, J.D.: Characterizations of reducible flow graphs. J. ACM 21(3), 367\u2013375 (1974). http:\/\/doi.acm.org\/10.1145\/321832.321835","journal-title":"J. ACM"},{"key":"13_CR21","volume-title":"Flow Analysis of Computer Programs","author":"MS Hecht","year":"1977","unstructured":"Hecht, M.S.: Flow Analysis of Computer Programs. Elsevier Science Inc., New York (1977)"},{"key":"13_CR22","doi-asserted-by":"crossref","unstructured":"Hecht, M.S., Ullman, J.D.: Analysis of a simple algorithm for global data flow problems. In: Proceedings of the 1st Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL 1973, pp. 207\u2013217., ACM, New York (1973). http:\/\/doi.acm.org\/10.1145\/512927.512946","DOI":"10.1145\/512927.512946"},{"key":"13_CR23","unstructured":"Hepp, S., Brandner, F.: Splitting functions into single-entry regions. In: Proceedings of the 2014 International Conference on Compilers, Architecture and Synthesis for Embedded Systems, CASES 2014, pp. 17:1\u201317:10. ACM, New York (2014). http:\/\/doi.acm.org\/10.1145\/2656106.2656128"},{"key":"13_CR24","doi-asserted-by":"crossref","unstructured":"Hundt, R., Raman, E., Thuresson, M., Vachharajani, N.: Mao \u2013 an extensible micro-architectural optimizer. In: Proceedings of the 9th Annual IEEE\/ACM International Symposium on Code Generation and Optimization, CGO 2011, pp. 1\u201310. IEEE Computer Society, Washington, D.C. (2011). http:\/\/dl.acm.org\/citation.cfm?id=2190025.2190077","DOI":"10.1109\/CGO.2011.5764669"},{"issue":"4","key":"13_CR25","doi-asserted-by":"crossref","first-page":"14:1","DOI":"10.1145\/1516507.1516509","volume":"31","author":"S Kalvala","year":"2009","unstructured":"Kalvala, S., Warburton, R., Lacey, D.: Program transformations using temporal logic side conditions. ACM Trans. Program. Lang. Syst. 31(4), 14:1\u201314:48 (2009). http:\/\/doi.acm.org\/10.1145\/1516507.1516509","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"6","key":"13_CR26","doi-asserted-by":"crossref","first-page":"1251","DOI":"10.1145\/330643.330647","volume":"21","author":"M Kandemir","year":"1999","unstructured":"Kandemir, M., Banerjee, P., Choudhary, A., Ramanujam, J., Shenoy, N.: A global communication optimization technique based on data-flow analysis and linear algebra. ACM Trans. Program. Lang. Syst. 21(6), 1251\u20131297 (1999). http:\/\/doi.acm.org\/10.1145\/330643.330647","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"13_CR27","unstructured":"Kleinsorge, J.C., Falk, H., Marwedel, P.: Simple analysis of partial worst-case execution paths on general control flow graphs. In: Proceedings of the Eleventh ACM International Conference on Embedded Software, EMSOFT 2013, pp. 16:1\u201316:10. IEEE Press, Piscataway (2013). http:\/\/dl.acm.org\/citation.cfm?id=2555754.2555770"},{"issue":"4","key":"13_CR28","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1145\/356635.356640","volume":"6","author":"DE Knuth","year":"1974","unstructured":"Knuth, D.E.: Structured programming with go to statements. ACM Comput. Surv. 6(4), 261\u2013301 (1974). http:\/\/doi.acm.org\/10.1145\/356635.356640","journal-title":"ACM Comput. Surv."},{"key":"13_CR29","doi-asserted-by":"crossref","unstructured":"Lattner, C., Adve, V.: LLVM: a compilation framework for lifelong program analysis & transformation. In: Proceedings of the International Symposium on Code Generation and Optimization: Feedback-Directed and Runtime Optimization, CGO 2004, p. 75. IEEE Computer Society, Washington, D.C. (2004). http:\/\/dl.acm.org\/citation.cfm?id=977395.977673","DOI":"10.1109\/CGO.2004.1281665"},{"key":"13_CR30","doi-asserted-by":"crossref","unstructured":"Matosevic, I., Abdelrahman, T.S.: Efficient bottom-up heap analysis for symbolic path-based data access summaries. In: Proceedings of the Tenth International Symposium on Code Generation and Optimization, CGO 2012, pp. 252\u2013263. ACM, New York (2012). http:\/\/doi.acm.org\/10.1145\/2259016.2259049","DOI":"10.1145\/2259016.2259049"},{"key":"13_CR31","doi-asserted-by":"crossref","unstructured":"Moretti, E., Chanteperdrix, G., Osorio, A.: New algorithms for control-flow graph structuring. In: Fifth Conference on Software Maintenance and Reengineering, CSMR 2001, Lisbon, Portugal, 14\u201316 March 2001, pp. 184\u2013187 (2001). http:\/\/dx.doi.org\/10.1109\/.2001.914984","DOI":"10.1109\/.2001.914984"},{"issue":"3","key":"13_CR32","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1093\/comjnl\/25.3.379","volume":"25","author":"G Oulsnam","year":"1982","unstructured":"Oulsnam, G.: Unravelling unstructured programs. Comput. J. 25(3), 379\u2013387 (1982). http:\/\/dx.doi.org\/10.1093\/comjnl\/25.3.379","journal-title":"Comput. J."},{"issue":"1","key":"13_CR33","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1093\/comjnl\/30.1.43","volume":"30","author":"G Oulsnam","year":"1987","unstructured":"Oulsnam, G.: The algorithmic transformation of schemas to structured form. Comput. J. 30(1), 43\u201351 (1987). http:\/\/dx.doi.org\/10.1093\/comjnl\/30.1.43","journal-title":"Comput. J."},{"issue":"4","key":"13_CR34","doi-asserted-by":"crossref","first-page":"893","DOI":"10.1145\/48014.48021","volume":"35","author":"L Ramshaw","year":"1988","unstructured":"Ramshaw, L.: Eliminating go to\u2019s while preserving program structure. J. ACM 35(4), 893\u2013920 (1988). http:\/\/doi.acm.org\/10.1145\/48014.48021","journal-title":"J. ACM"},{"key":"13_CR35","unstructured":"Sabne, A.J., Lin, Y., Grover, V.: Confluence analysis and loop fast-forwarding for improving SIMD execution efficiency, 21 January 2014, uS Patent Ap. 14\/160,426"},{"issue":"10","key":"13_CR36","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1145\/1103845.1094837","volume":"40","author":"A Shankar","year":"2005","unstructured":"Shankar, A., Sastry, S.S., Bod\u00edk, R., Smith, J.E.: Runtime specialization with optimistic heap analysis. SIGPLAN Not. 40(10), 327\u2013343 (2005). http:\/\/doi.acm.org\/10.1145\/1103845.1094837","journal-title":"SIGPLAN Not."},{"issue":"1","key":"13_CR37","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1002\/spe.1059","volume":"42","author":"J Stanier","year":"2012","unstructured":"Stanier, J., Watson, D.: A study of irreducibility in C programs. Softw. Pract. Experience 42(1), 117\u2013130 (2012). http:\/\/dx.doi.org\/10.1002\/spe.1059","journal-title":"Softw. Pract. Experience"},{"issue":"4","key":"13_CR38","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1145\/567097.567098","volume":"24","author":"S Unger","year":"2002","unstructured":"Unger, S., Mueller, F.: Handling irreducible loops: optimized node splitting versus DJ-graphs. ACM Trans. Program. Lang. Syst. 24(4), 299\u2013333 (2002). http:\/\/doi.acm.org\/10.1145\/567097.567098","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"1","key":"13_CR39","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1093\/comjnl\/20.1.45","volume":"20","author":"MH Williams","year":"1977","unstructured":"Williams, M.H.: Generating structured flow diagrams: the nature of unstructuredness. Comput. J. 20(1), 45\u201350 (1977). http:\/\/dx.doi.org\/10.1093\/comjnl\/20.1.45","journal-title":"Comput. J."},{"issue":"2","key":"13_CR40","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1093\/comjnl\/21.2.161","volume":"21","author":"MH Williams","year":"1978","unstructured":"Williams, M.H., Ossher, H.L.: Conversion of unstructured flow diagrams to structured form. Comput. J. 21(2), 161\u2013167 (1978)","journal-title":"Comput. J."},{"key":"13_CR41","doi-asserted-by":"crossref","unstructured":"Wimmer, C., Franz, M.: Linear scan register allocation on SSA form. In: Proceedings of the 8th Annual IEEE\/ACM International Symposium on Code Generation and Optimization, CGO 2010, pp. 170\u2013179. ACM, New York (2010). http:\/\/doi.acm.org\/10.1145\/1772954.1772979","DOI":"10.1145\/1772954.1772979"},{"issue":"1","key":"13_CR42","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1109\/TSE.1979.226497","volume":"5","author":"M Woodward","year":"1979","unstructured":"Woodward, M., Hennell, M., Hedley, D.: A measure of control flow complexity in program text. IEEE Trans. Softw. Eng. 5(1), 45\u201350 (1979)","journal-title":"IEEE Trans. Softw. Eng."},{"issue":"2","key":"13_CR43","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1177\/1094342011434814","volume":"26","author":"H Wu","year":"2012","unstructured":"Wu, H., Diamos, G., Wang, J., Li, S., Yalamanchili, S.: Characterization and transformation of unstructured control flow in bulk synchronous GPU applications. Int. J. High Perform. Comput. Appl. 26(2), 170\u2013185 (2012). http:\/\/dx.doi.org\/10.1177\/1094342011434814","journal-title":"Int. J. High Perform. Comput. Appl."},{"key":"13_CR44","doi-asserted-by":"crossref","unstructured":"Xie, Y., Aiken, A.: Saturn: a scalable framework for error detection using Boolean satisfiability. ACM Trans. Program. Lang. Syst. 29(3), Article No. 16 (2007). http:\/\/doi.acm.org\/10.1145\/1232420.1232423","DOI":"10.1145\/1232420.1232423"},{"issue":"4","key":"13_CR45","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1109\/TSE.2004.1274043","volume":"30","author":"F Zhang","year":"2004","unstructured":"Zhang, F., D\u2019Hollander, E.H.: Using hammock graphs to structure programs. IEEE Trans. Softw. Eng. 30(4), 231\u2013245 (2004). http:\/\/dx.doi.org\/10.1109\/TSE.2004.1274043","journal-title":"IEEE Trans. Softw. Eng."}],"container-title":["Lecture Notes in Computer Science","Languages and Compilers for Parallel Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-52709-3_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,25]],"date-time":"2017-06-25T04:51:30Z","timestamp":1498366290000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-52709-3_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319527086","9783319527093"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-52709-3_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}