Multi-Language Benchmark Generation via L-Systems
Resumo
This paper introduces BenchGen, a benchmark synthesizer that uses L-systems (iterated rewriting rules) to generate large, structurally self-similar programs in multiple languages. The goal of BenchGen is to support the evaluation of the performance of language processing systems: compilers, interpreters, static analyzers and such. By exploring notions of self-similarity, BenchGen can generate complex control flow without undefined behavior, and produce families of comparable programs across languages. To demonstrate its effectiveness, this paper reports representative case studies of BenchGen that illustrate how the generated benchmarks can be used to analyze different compilers.
Palavras-chave:
L-System, Benchmark, Synthesis
Referências
Jordi Armengol-Estapé, Jackson Woodruff, Alexander Brauckmann, José Wesley de Souza Magalhães, and Michael F. P. O’Boyle. Exebench: an ml-scale dataset of executable c functions. In MAPS, page 50–59, New York, NY, USA, 2022. Association for Computing Machinery.
Gergö Barany. Liveness-driven random program generation. In LOPSTR, pages 112–127, Heidelberg, Germany, 2017. Springer.
Gergö Barany. Finding missed compiler optimizations by differential testing. In Proceedings of the 27th International Conference on Compiler Construction, CC 2018, pages 82–92, New York, NY, USA, 2018. ACM.
Patrick Baudin, François Bobot, David Bühler, Loïc Correnson, Florent Kirchner, Nikolai Kosmatov, André Maroneze, Valentin Perrelle, Virgile Prevosto, Julien Signoles, and Nicky Williams. The dogged pursuit of bug-free c programs: the frama-c software analysis platform. Commun. ACM, 64(8):56–68, July 2021.
Bachir Bendrissou, Cristian Cadar, and Alastair F. Donaldson. Grammar mutation for testing input parsers. ACM Trans. Softw. Eng. Methodol., 34(4), April 2025.
Maksim Berezov, Corinne Ancourt, Justyna Zawalska, and Maryna Savchenko. COLA-Gen: Active Learning Techniques for Automatic Code Generation of Benchmarks. In Francesca Palumbo, João Bispo, and Stefano Cherubin, editors, PARMA-DITAM, volume 100 of Open Access Series in Informatics (OASIcs), pages 3:1–3:14, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
Shuai Che, Michael Boyer, Jiayuan Meng, David Tarjan, Jeremy W. Sheaffer, Sang-Ha Lee, and Kevin Skadron. Rodinia: A benchmark suite for heterogeneous computing. In IISWC, pages 44–54, Washington, DC, USA, 2009. IEEE.
Dehao Chen, David Xinliang Li, and Tipp Moseley. Autofdo: automatic feedbackdirected optimization for warehouse-scale applications. In CGO, page 12–23, New York, NY, USA, 2016. Association for Computing Machinery.
Chris Cummins, Pavlos Petoumenos, Zheng Wang, and Hugh Leather. Synthesizing benchmarks for predictive modeling. In CGO, pages 86–99, Piscataway, NJ, USA, 2017. IEEE.
Chris Cummins, Bram Wasti, Jiadong Guo, Brandon Cui, Jason Ansel, Sahir Gomez, Somya Jain, Jia Liu, Olivier Teytaud, Benoit Steiner, et al. Compilergym: Robust, performant compiler optimization environments for ai research. In CGO, pages 92–105, New York, USA, 2022. IEEE.
Charlie Curtsinger and Emery D. Berger. Coz: finding code that counts with causal profiling. In SOSP, page 184–197, New York, NY, USA, 2015. Association for Computing Machinery.
Anderson Faustino da Silva, Bruno Conde Kind, José Wesley de Souza Magalhães, Jerônimo Nunes Rocha, Breno Campos Ferreira Guimarães, and Fernando Magno Quintão Pereira. AnghaBench: A suite with one million compilable C benchmarks for code-size reduction. In CGO, pages 378–390, Los Alamitos, CA, USA, 2021. IEEE.
Chucky Ellison and Grigore Rosu. An executable formal semantics of c with applications. SIGPLAN Not., 47(1):533–544, January 2012.
Jaroslav Fowkes and Charles Sutton. Parameter-free probabilistic api mining across github. In FSE, page 254–265, New York, NY, USA, 2016. Association for Computing Machinery.
Andrés Goens, Alexander Brauckmann, Sebastian Ertel, Chris Cummins, Hugh Leather, and Jeronimo Castrillon. A case study on machine learning for synthesizing benchmarks. In Proceedings of the 3rd ACM SIGPLAN International Workshop on Machine Learning and Programming Languages, MAPL 2019, pages 38–46, New York, NY, USA, 2019. ACM.
Georgios Gousios and Diomidis Spinellis. Mining software engineering data from github. In ICSE-C, page 501–502, Washington, DC, US, 2017. IEEE Press.
M. R. Guthaus, J. S. Ringenberg, D. Ernst, T. M. Austin, T. Mudge, and R. B. Brown. MiBench: A free, commercially representative embedded benchmark suite. In WWC, pages 3–14, Washington, DC, USA, 2001. IEEE.
Xue Han and Tingting Yu. An empirical study on performance bugs for highly configurable software systems. In ESEM, New York, NY, USA, 2016. Association for Computing Machinery.
Atsushi Hashimoto and Nagisa Ishiura. Detecting arithmetic optimization opportunities for c compilers by randomly generated equivalent programs. IPSJ Transactions on System LSI Design Methodology, 9:21–29, 2016.
John L. Henning. SPEC CPU2006 benchmark descriptions. SIGARCH Comput. Archit. News, 34(4):1–17, September 2006.
Renáta Hodován, Ákos Kiss, and Tibor Gyimóthy. Grammarinator: a grammarbased open source fuzzer. In Proceedings of the 9th ACM SIGSOFT International Workshop on Automating TEST Case Design, Selection, and Evaluation, A-TEST 2018, page 45–48, New York, NY, USA, 2018. Association for Computing Machinery.
Davide Italiano and Chris Cummins. Finding missed code size optimizations in compilers using large language models. In International Conference on Compiler Construction, page 81–91, New York, NY, USA, 2025. Association for Computing Machinery.
Cecilia Conde Kind, Michael Canesche, and Fernando Magno Quintao Pereira. Jotai: a methodology for the generation of executable c benchmarks. Technical report, Technical Report 02-2022. Universidade Federal de Minas Gerais, 2022.
Kota Kitaura and Nagisa Ishiura. Random testing of compilers’ performance based on mixed static and dynamic code comparison. In Proceedings of the 9th ACM SIGSOFT International Workshop on Automating TEST Case Design, Selection, and Evaluation, A-TEST 2018, page 38–44, New York, NY, USA, 2018. Association for Computing Machinery.
Aristid Lindenmayer. Mathematical models for cellular interactions in development i. filaments with one-sided inputs. Journal of theoretical biology, 18(3):280–299, 1968.
Vsevolod Livinskii, Dmitry Babokin, and John Regehr. Random testing for c and c++ compilers with yarpgen. Proc. ACM Program. Lang., 4(OOPSLA), November 2020.
Valentin J.M. Manes, HyungSeok Han, Choongwoo Han, Sang Kil Cha, Manuel Egele, Edward J. Schwartz, and Maverick Woo. The art, science, and engineering of fuzzing: A survey. IEEE Transactions on Software Engineering, 47(11):2312–2331, 2021.
Angélica Aparecida Moreira, Guilherme Ottoni, and Fernando Magno Quintão Pereira. Vespa: static profiling for binary optimization. Proc. ACM Program. Lang., 5(OOPSLA), October 2021.
Lili Mou, Ge Li, Lu Zhang, Tao Wang, and Zhi Jin. Convolutional neural networks over tree structures for programming language processing. In AAAI, page 1287–1293, Palo Alto, CA, US, 2016. AAAI Press.
Eriko Nagai, Atsushi Hashimoto, and Nagisa Ishiura. Reinforcing random testing of arithmetic optimization of c compilers by scaling up size and number of expressions. IPSJ Trans. System LSI Design Methodology, 7:91–100, 2014.
Kazuhiro Nakamura and Nagisa Ishiura. Introducing loop statements in random testing of c compilers based on expected value calculation, 2015.
Nicholas Nethercote and Julian Seward. Valgrind: a framework for heavyweight dynamic binary instrumentation. In PLDI, page 89–100, New York, NY, USA, 2007. Association for Computing Machinery.
Oswaldo Olivo, Isil Dillig, and Calvin Lin. Static detection of asymptotic performance bugs in collection traversals. In PLDI, page 369–378, New York, NY, USA, 2015. Association for Computing Machinery.
David N Palacio, Alejandro Velasco, Daniel Rodriguez-Cardenas, Kevin Moran, and Denys Poshyvanyk. Evaluating and explaining large language models for code using syntactic structures, 2023.
Maksim Panchenko, Rafael Auler, Bill Nell, and Guilherme Ottoni. Bolt: a practical binary optimizer for data centers and beyond. In CGO, page 2–14. IEEE Press, 2019.
Paul Purdom. A sentence generator for testing parsers. BIT, 12(3):366–375, September 1972.
Gabriel Ricardo, Natanael Santos Junior, Flavio Figueiredo, and Fernando Pereira. On the practicality of llm-based compiler fuzzing. In SBLP, pages 59–66, Porto Alegre, RS, Brasil, 2025. SBC.
Konstantin Serebryany, Derek Bruening, Alexander Potapenko, and Dmitry Vyukov. Addresssanitizer: a fast address sanity checker. In USENIX ATC, page 28, USA, 2012. USENIX Association.
João Victor Amorim Vieira, Luiza de Melo Gomes, Rafael Sumitani, Raissa Maciel, Augusto Mafra, Mirlaine Crepalde, and Fernando Magno Quintão Pereira. Bottomup generation of verilog designs for testing eda tools, 2025.
Zheng Wang and Michael F. P. O’Boyle. Machine learning in compiler optimization. Proceedings of the IEEE, 106(11):1879–1901, 2018.
Chunqiu Steven Xia, Matteo Paltenghi, Jia Le Tian, Michael Pradel, and Lingming Zhang. Fuzz4all: Universal fuzzing with large language models. In Proceedings of the IEEE/ACM 46th International Conference on Software Engineering, ICSE ’24, New York, NY, USA, 2024. Association for Computing Machinery.
Xuejun Yang, Yang Chen, Eric Eide, and John Regehr. Finding and understanding bugs in c compilers. In Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’11, page 283–294, New York, NY, USA, 2011. Association for Computing Machinery.
José Antonio Zamudio Amaya. Shaping test inputs in grammar-based fuzzing. In ISSTA, page 1901–1905, New York, NY, USA, 2024. Association for Computing Machinery.
Gergö Barany. Liveness-driven random program generation. In LOPSTR, pages 112–127, Heidelberg, Germany, 2017. Springer.
Gergö Barany. Finding missed compiler optimizations by differential testing. In Proceedings of the 27th International Conference on Compiler Construction, CC 2018, pages 82–92, New York, NY, USA, 2018. ACM.
Patrick Baudin, François Bobot, David Bühler, Loïc Correnson, Florent Kirchner, Nikolai Kosmatov, André Maroneze, Valentin Perrelle, Virgile Prevosto, Julien Signoles, and Nicky Williams. The dogged pursuit of bug-free c programs: the frama-c software analysis platform. Commun. ACM, 64(8):56–68, July 2021.
Bachir Bendrissou, Cristian Cadar, and Alastair F. Donaldson. Grammar mutation for testing input parsers. ACM Trans. Softw. Eng. Methodol., 34(4), April 2025.
Maksim Berezov, Corinne Ancourt, Justyna Zawalska, and Maryna Savchenko. COLA-Gen: Active Learning Techniques for Automatic Code Generation of Benchmarks. In Francesca Palumbo, João Bispo, and Stefano Cherubin, editors, PARMA-DITAM, volume 100 of Open Access Series in Informatics (OASIcs), pages 3:1–3:14, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
Shuai Che, Michael Boyer, Jiayuan Meng, David Tarjan, Jeremy W. Sheaffer, Sang-Ha Lee, and Kevin Skadron. Rodinia: A benchmark suite for heterogeneous computing. In IISWC, pages 44–54, Washington, DC, USA, 2009. IEEE.
Dehao Chen, David Xinliang Li, and Tipp Moseley. Autofdo: automatic feedbackdirected optimization for warehouse-scale applications. In CGO, page 12–23, New York, NY, USA, 2016. Association for Computing Machinery.
Chris Cummins, Pavlos Petoumenos, Zheng Wang, and Hugh Leather. Synthesizing benchmarks for predictive modeling. In CGO, pages 86–99, Piscataway, NJ, USA, 2017. IEEE.
Chris Cummins, Bram Wasti, Jiadong Guo, Brandon Cui, Jason Ansel, Sahir Gomez, Somya Jain, Jia Liu, Olivier Teytaud, Benoit Steiner, et al. Compilergym: Robust, performant compiler optimization environments for ai research. In CGO, pages 92–105, New York, USA, 2022. IEEE.
Charlie Curtsinger and Emery D. Berger. Coz: finding code that counts with causal profiling. In SOSP, page 184–197, New York, NY, USA, 2015. Association for Computing Machinery.
Anderson Faustino da Silva, Bruno Conde Kind, José Wesley de Souza Magalhães, Jerônimo Nunes Rocha, Breno Campos Ferreira Guimarães, and Fernando Magno Quintão Pereira. AnghaBench: A suite with one million compilable C benchmarks for code-size reduction. In CGO, pages 378–390, Los Alamitos, CA, USA, 2021. IEEE.
Chucky Ellison and Grigore Rosu. An executable formal semantics of c with applications. SIGPLAN Not., 47(1):533–544, January 2012.
Jaroslav Fowkes and Charles Sutton. Parameter-free probabilistic api mining across github. In FSE, page 254–265, New York, NY, USA, 2016. Association for Computing Machinery.
Andrés Goens, Alexander Brauckmann, Sebastian Ertel, Chris Cummins, Hugh Leather, and Jeronimo Castrillon. A case study on machine learning for synthesizing benchmarks. In Proceedings of the 3rd ACM SIGPLAN International Workshop on Machine Learning and Programming Languages, MAPL 2019, pages 38–46, New York, NY, USA, 2019. ACM.
Georgios Gousios and Diomidis Spinellis. Mining software engineering data from github. In ICSE-C, page 501–502, Washington, DC, US, 2017. IEEE Press.
M. R. Guthaus, J. S. Ringenberg, D. Ernst, T. M. Austin, T. Mudge, and R. B. Brown. MiBench: A free, commercially representative embedded benchmark suite. In WWC, pages 3–14, Washington, DC, USA, 2001. IEEE.
Xue Han and Tingting Yu. An empirical study on performance bugs for highly configurable software systems. In ESEM, New York, NY, USA, 2016. Association for Computing Machinery.
Atsushi Hashimoto and Nagisa Ishiura. Detecting arithmetic optimization opportunities for c compilers by randomly generated equivalent programs. IPSJ Transactions on System LSI Design Methodology, 9:21–29, 2016.
John L. Henning. SPEC CPU2006 benchmark descriptions. SIGARCH Comput. Archit. News, 34(4):1–17, September 2006.
Renáta Hodován, Ákos Kiss, and Tibor Gyimóthy. Grammarinator: a grammarbased open source fuzzer. In Proceedings of the 9th ACM SIGSOFT International Workshop on Automating TEST Case Design, Selection, and Evaluation, A-TEST 2018, page 45–48, New York, NY, USA, 2018. Association for Computing Machinery.
Davide Italiano and Chris Cummins. Finding missed code size optimizations in compilers using large language models. In International Conference on Compiler Construction, page 81–91, New York, NY, USA, 2025. Association for Computing Machinery.
Cecilia Conde Kind, Michael Canesche, and Fernando Magno Quintao Pereira. Jotai: a methodology for the generation of executable c benchmarks. Technical report, Technical Report 02-2022. Universidade Federal de Minas Gerais, 2022.
Kota Kitaura and Nagisa Ishiura. Random testing of compilers’ performance based on mixed static and dynamic code comparison. In Proceedings of the 9th ACM SIGSOFT International Workshop on Automating TEST Case Design, Selection, and Evaluation, A-TEST 2018, page 38–44, New York, NY, USA, 2018. Association for Computing Machinery.
Aristid Lindenmayer. Mathematical models for cellular interactions in development i. filaments with one-sided inputs. Journal of theoretical biology, 18(3):280–299, 1968.
Vsevolod Livinskii, Dmitry Babokin, and John Regehr. Random testing for c and c++ compilers with yarpgen. Proc. ACM Program. Lang., 4(OOPSLA), November 2020.
Valentin J.M. Manes, HyungSeok Han, Choongwoo Han, Sang Kil Cha, Manuel Egele, Edward J. Schwartz, and Maverick Woo. The art, science, and engineering of fuzzing: A survey. IEEE Transactions on Software Engineering, 47(11):2312–2331, 2021.
Angélica Aparecida Moreira, Guilherme Ottoni, and Fernando Magno Quintão Pereira. Vespa: static profiling for binary optimization. Proc. ACM Program. Lang., 5(OOPSLA), October 2021.
Lili Mou, Ge Li, Lu Zhang, Tao Wang, and Zhi Jin. Convolutional neural networks over tree structures for programming language processing. In AAAI, page 1287–1293, Palo Alto, CA, US, 2016. AAAI Press.
Eriko Nagai, Atsushi Hashimoto, and Nagisa Ishiura. Reinforcing random testing of arithmetic optimization of c compilers by scaling up size and number of expressions. IPSJ Trans. System LSI Design Methodology, 7:91–100, 2014.
Kazuhiro Nakamura and Nagisa Ishiura. Introducing loop statements in random testing of c compilers based on expected value calculation, 2015.
Nicholas Nethercote and Julian Seward. Valgrind: a framework for heavyweight dynamic binary instrumentation. In PLDI, page 89–100, New York, NY, USA, 2007. Association for Computing Machinery.
Oswaldo Olivo, Isil Dillig, and Calvin Lin. Static detection of asymptotic performance bugs in collection traversals. In PLDI, page 369–378, New York, NY, USA, 2015. Association for Computing Machinery.
David N Palacio, Alejandro Velasco, Daniel Rodriguez-Cardenas, Kevin Moran, and Denys Poshyvanyk. Evaluating and explaining large language models for code using syntactic structures, 2023.
Maksim Panchenko, Rafael Auler, Bill Nell, and Guilherme Ottoni. Bolt: a practical binary optimizer for data centers and beyond. In CGO, page 2–14. IEEE Press, 2019.
Paul Purdom. A sentence generator for testing parsers. BIT, 12(3):366–375, September 1972.
Gabriel Ricardo, Natanael Santos Junior, Flavio Figueiredo, and Fernando Pereira. On the practicality of llm-based compiler fuzzing. In SBLP, pages 59–66, Porto Alegre, RS, Brasil, 2025. SBC.
Konstantin Serebryany, Derek Bruening, Alexander Potapenko, and Dmitry Vyukov. Addresssanitizer: a fast address sanity checker. In USENIX ATC, page 28, USA, 2012. USENIX Association.
João Victor Amorim Vieira, Luiza de Melo Gomes, Rafael Sumitani, Raissa Maciel, Augusto Mafra, Mirlaine Crepalde, and Fernando Magno Quintão Pereira. Bottomup generation of verilog designs for testing eda tools, 2025.
Zheng Wang and Michael F. P. O’Boyle. Machine learning in compiler optimization. Proceedings of the IEEE, 106(11):1879–1901, 2018.
Chunqiu Steven Xia, Matteo Paltenghi, Jia Le Tian, Michael Pradel, and Lingming Zhang. Fuzz4all: Universal fuzzing with large language models. In Proceedings of the IEEE/ACM 46th International Conference on Software Engineering, ICSE ’24, New York, NY, USA, 2024. Association for Computing Machinery.
Xuejun Yang, Yang Chen, Eric Eide, and John Regehr. Finding and understanding bugs in c compilers. In Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’11, page 283–294, New York, NY, USA, 2011. Association for Computing Machinery.
José Antonio Zamudio Amaya. Shaping test inputs in grammar-based fuzzing. In ISSTA, page 1901–1905, New York, NY, USA, 2024. Association for Computing Machinery.
Publicado
08/09/2026
Como Citar
SILVA, Vinicius Francisco da; FERRAZ, Matheus Marchesotti; PEREIRA, Fernando Magno Quintão.
Multi-Language Benchmark Generation via L-Systems. In: SIMPÓSIO BRASILEIRO DE LINGUAGENS DE PROGRAMAÇÃO (SBLP), 30. , 2026, São Paulo/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 10-19.
DOI: https://doi.org/10.5753/sblp.2026.27598.
