Idempotent Slices with Applications to Code-Size Reduction
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908877058998272 |
|---|---|
| author | de Azevedo, Rafael Alvarenga de Sa, Daniel Augusto Costa Rocha, Rodrigo Caetano Pereira, Fernando Magno Quintão |
| author_facet | de Azevedo, Rafael Alvarenga de Sa, Daniel Augusto Costa Rocha, Rodrigo Caetano Pereira, Fernando Magno Quintão |
| contents | Given a value computed within a program, an idempotent backward slice with respect to this value is a maximal subprogram that computes it. An informal notion of an idempotent slice has previously been used by Guimaraes et al. to transform eager into strict evaluation in the LLVM intermediate representation. However, that algorithm is insufficient to be correctly applied to general control-flow graphs. This paper addresses these omissions by formalizing the notion of idempotent backward slices and presenting a sound and efficient algorithm for extracting them from programs in Gated Static Single Assignment (GSA) form. As an example of their practical use, the paper describes how identifying and extracting idempotent backward slices enables a sparse code-size reduction optimization; that is, one capable of merging non-contiguous sequences of instructions within the control-flow graph of a single function or across functions. Experiments with the LLVM test suite show that, in specific benchmarks, this new algorithm achieves code-size reductions up to -7.24% on programs highly optimized by the -Os sequence of passes from clang 17. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_09726 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Idempotent Slices with Applications to Code-Size Reduction de Azevedo, Rafael Alvarenga de Sa, Daniel Augusto Costa Rocha, Rodrigo Caetano Pereira, Fernando Magno Quintão Programming Languages 68N15 D.3.4 Given a value computed within a program, an idempotent backward slice with respect to this value is a maximal subprogram that computes it. An informal notion of an idempotent slice has previously been used by Guimaraes et al. to transform eager into strict evaluation in the LLVM intermediate representation. However, that algorithm is insufficient to be correctly applied to general control-flow graphs. This paper addresses these omissions by formalizing the notion of idempotent backward slices and presenting a sound and efficient algorithm for extracting them from programs in Gated Static Single Assignment (GSA) form. As an example of their practical use, the paper describes how identifying and extracting idempotent backward slices enables a sparse code-size reduction optimization; that is, one capable of merging non-contiguous sequences of instructions within the control-flow graph of a single function or across functions. Experiments with the LLVM test suite show that, in specific benchmarks, this new algorithm achieves code-size reductions up to -7.24% on programs highly optimized by the -Os sequence of passes from clang 17. |
| title | Idempotent Slices with Applications to Code-Size Reduction |
| topic | Programming Languages 68N15 D.3.4 |
| url | https://arxiv.org/abs/2603.09726 |