The algorithm and implementation of an extension to LLVM for solving the blocking between instruction sink and division-modulo combine
Compiler optimization presents a formidable challenge, seeking to enhance code quality through various techniques. One significant obstacle is the phase-ordering problem, where the sequence of optimization algorithms can impact code quality and potentially lead to performance deterioration. While ma...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2023-12-01
|
| Series: | Connection Science |
| Subjects: | |
| Online Access: | https://www.tandfonline.com/doi/10.1080/09540091.2023.2273219 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850227034261815296 |
|---|---|
| author | YungYu Zhuang Ting-Wei Lin Yin-Jung Huang |
| author_facet | YungYu Zhuang Ting-Wei Lin Yin-Jung Huang |
| author_sort | YungYu Zhuang |
| collection | DOAJ |
| description | Compiler optimization presents a formidable challenge, seeking to enhance code quality through various techniques. One significant obstacle is the phase-ordering problem, where the sequence of optimization algorithms can impact code quality and potentially lead to performance deterioration. While machine learning has shown promise in addressing this issue, it still encounters limitations in certain scenarios.Instruction Sink is a machine-independent optimization that segregates instructions like modulo and division into separate basic blocks. This separation prevents the application of the machine-dependent optimization called Division-Modulo Combine at the backend, which could otherwise lead to a decline in program performance. However, reordering these optimizations to avoid conflicts can prove to be challenging. In this paper, we propose an algorithm to enhance Instruction Sink, resolving the blocking problem, and implements it within the LLVM optimizer. Leveraging the modularity of LLVM enables us to tackle all affected back-end issues simultaneously.To assess the effectiveness of our algorithm, we conduct a comprehensive evaluation focusing on feasibility, compatibility, and targeted improvements. The results demonstrate that our approach effectively addresses the blocking problem without conflicting with other optimization algorithms, solely impacting problematic instructions while leaving normal ones unaffected. |
| format | Article |
| id | doaj-art-55d4490e412e48b29787b965c8406b76 |
| institution | OA Journals |
| issn | 0954-0091 1360-0494 |
| language | English |
| publishDate | 2023-12-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | Connection Science |
| spelling | doaj-art-55d4490e412e48b29787b965c8406b762025-08-20T02:04:55ZengTaylor & Francis GroupConnection Science0954-00911360-04942023-12-0135110.1080/09540091.2023.2273219The algorithm and implementation of an extension to LLVM for solving the blocking between instruction sink and division-modulo combineYungYu Zhuang0Ting-Wei Lin1Yin-Jung Huang2Dept. of Computer Science and Information Engineering, National Central University, Taoyuan, TaiwanDept. of Computer Science and Information Engineering, National Central University, Taoyuan, TaiwanDept. of Computer Science and Information Engineering, National Central University, Taoyuan, TaiwanCompiler optimization presents a formidable challenge, seeking to enhance code quality through various techniques. One significant obstacle is the phase-ordering problem, where the sequence of optimization algorithms can impact code quality and potentially lead to performance deterioration. While machine learning has shown promise in addressing this issue, it still encounters limitations in certain scenarios.Instruction Sink is a machine-independent optimization that segregates instructions like modulo and division into separate basic blocks. This separation prevents the application of the machine-dependent optimization called Division-Modulo Combine at the backend, which could otherwise lead to a decline in program performance. However, reordering these optimizations to avoid conflicts can prove to be challenging. In this paper, we propose an algorithm to enhance Instruction Sink, resolving the blocking problem, and implements it within the LLVM optimizer. Leveraging the modularity of LLVM enables us to tackle all affected back-end issues simultaneously.To assess the effectiveness of our algorithm, we conduct a comprehensive evaluation focusing on feasibility, compatibility, and targeted improvements. The results demonstrate that our approach effectively addresses the blocking problem without conflicting with other optimization algorithms, solely impacting problematic instructions while leaving normal ones unaffected.https://www.tandfonline.com/doi/10.1080/09540091.2023.2273219Code optimizationPhase-orderingCode motionLLVMsoftware engineering & systems development |
| spellingShingle | YungYu Zhuang Ting-Wei Lin Yin-Jung Huang The algorithm and implementation of an extension to LLVM for solving the blocking between instruction sink and division-modulo combine Connection Science Code optimization Phase-ordering Code motion LLVM software engineering & systems development |
| title | The algorithm and implementation of an extension to LLVM for solving the blocking between instruction sink and division-modulo combine |
| title_full | The algorithm and implementation of an extension to LLVM for solving the blocking between instruction sink and division-modulo combine |
| title_fullStr | The algorithm and implementation of an extension to LLVM for solving the blocking between instruction sink and division-modulo combine |
| title_full_unstemmed | The algorithm and implementation of an extension to LLVM for solving the blocking between instruction sink and division-modulo combine |
| title_short | The algorithm and implementation of an extension to LLVM for solving the blocking between instruction sink and division-modulo combine |
| title_sort | algorithm and implementation of an extension to llvm for solving the blocking between instruction sink and division modulo combine |
| topic | Code optimization Phase-ordering Code motion LLVM software engineering & systems development |
| url | https://www.tandfonline.com/doi/10.1080/09540091.2023.2273219 |
| work_keys_str_mv | AT yungyuzhuang thealgorithmandimplementationofanextensiontollvmforsolvingtheblockingbetweeninstructionsinkanddivisionmodulocombine AT tingweilin thealgorithmandimplementationofanextensiontollvmforsolvingtheblockingbetweeninstructionsinkanddivisionmodulocombine AT yinjunghuang thealgorithmandimplementationofanextensiontollvmforsolvingtheblockingbetweeninstructionsinkanddivisionmodulocombine AT yungyuzhuang algorithmandimplementationofanextensiontollvmforsolvingtheblockingbetweeninstructionsinkanddivisionmodulocombine AT tingweilin algorithmandimplementationofanextensiontollvmforsolvingtheblockingbetweeninstructionsinkanddivisionmodulocombine AT yinjunghuang algorithmandimplementationofanextensiontollvmforsolvingtheblockingbetweeninstructionsinkanddivisionmodulocombine |