Loop quasi-invariant chunk detection

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Standard

Loop quasi-invariant chunk detection. / Moyen, Jean-Yves; Rubiano, Thomas; Seiller, Thomas.

Automated Technology for Verification and Analysis: 15th International Symposium, ATVA 2017, Pune, India, October 3–6, 2017, Proceedings. ed. / Deepak D'Souza; K. Narayan Kumar. Springer, 2017. p. 91-108 (Lecture notes in computer science, Vol. 10482).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Harvard

Moyen, J-Y, Rubiano, T & Seiller, T 2017, Loop quasi-invariant chunk detection. in D D'Souza & KN Kumar (eds), Automated Technology for Verification and Analysis: 15th International Symposium, ATVA 2017, Pune, India, October 3–6, 2017, Proceedings. Springer, Lecture notes in computer science, vol. 10482, pp. 91-108, 15th International Symposium on Automated Technology for Verification and Analysis, Pune, India, 03/10/2017. https://doi.org/10.1007/978-3-319-68167-2_7

APA

Moyen, J-Y., Rubiano, T., & Seiller, T. (2017). Loop quasi-invariant chunk detection. In D. D'Souza, & K. N. Kumar (Eds.), Automated Technology for Verification and Analysis: 15th International Symposium, ATVA 2017, Pune, India, October 3–6, 2017, Proceedings (pp. 91-108). Springer. Lecture notes in computer science Vol. 10482 https://doi.org/10.1007/978-3-319-68167-2_7

Vancouver

Moyen J-Y, Rubiano T, Seiller T. Loop quasi-invariant chunk detection. In D'Souza D, Kumar KN, editors, Automated Technology for Verification and Analysis: 15th International Symposium, ATVA 2017, Pune, India, October 3–6, 2017, Proceedings. Springer. 2017. p. 91-108. (Lecture notes in computer science, Vol. 10482). https://doi.org/10.1007/978-3-319-68167-2_7

Author

Moyen, Jean-Yves ; Rubiano, Thomas ; Seiller, Thomas. / Loop quasi-invariant chunk detection. Automated Technology for Verification and Analysis: 15th International Symposium, ATVA 2017, Pune, India, October 3–6, 2017, Proceedings. editor / Deepak D'Souza ; K. Narayan Kumar. Springer, 2017. pp. 91-108 (Lecture notes in computer science, Vol. 10482).

Bibtex

@inproceedings{a1ce7a801a5742dfb8f6b0eb9a4cfbba,
title = "Loop quasi-invariant chunk detection",
abstract = "Several techniques for analysis and transformations are used in compilers. Among them, the peeling of loops for hoisting quasi-invariants can be used to optimize generated code, or simply ease developers{\textquoteright} lives. In this paper, we introduce a new concept of dependency analysis borrowed from the field of Implicit Computational Complexity (ICC), allowing to work with composed statements called “Chunks” to detect more quasi-invariants. Based on an optimization idea given on a WHILE language, we provide a transformation method - reusing ICC concepts and techniques [8, 10] - to compilers. This new analysis computes an invariance degree for each statement or chunks of statements by building a new kind of dependency graph, finds the “maximum” or “worst” dependency graph for loops, and recognizes if an entire block is Quasi-Invariant or not. This block could be an inner loop, and in that case the computational complexity of the overall program can be decreased. In this paper, we introduce the theory around this concept and present a prototype analysis pass implemented on LLVM. We already implemented a proof of concept on a toy C parser (https://github.com/ThomasRuby/LQICM_On_C_Toy_Parser) analysing and transforming the AST representation. In a very near future, we will implement the corresponding transformation within our prototype LLVM pass and provide benchmarks comparisons.",
keywords = "Compilers, Complexity, Loop invariants, Optimization, Quasi-invariants, Static analysis, Transformations",
author = "Jean-Yves Moyen and Thomas Rubiano and Thomas Seiller",
year = "2017",
doi = "10.1007/978-3-319-68167-2_7",
language = "English",
isbn = "978-3-319-68166-5",
series = "Lecture notes in computer science",
publisher = "Springer",
pages = "91--108",
editor = "Deepak D'Souza and Kumar, {K. Narayan}",
booktitle = "Automated Technology for Verification and Analysis",
address = "Switzerland",
note = "null ; Conference date: 03-10-2017 Through 06-10-2017",

}

RIS

TY - GEN

T1 - Loop quasi-invariant chunk detection

AU - Moyen, Jean-Yves

AU - Rubiano, Thomas

AU - Seiller, Thomas

N1 - Conference code: 15

PY - 2017

Y1 - 2017

N2 - Several techniques for analysis and transformations are used in compilers. Among them, the peeling of loops for hoisting quasi-invariants can be used to optimize generated code, or simply ease developers’ lives. In this paper, we introduce a new concept of dependency analysis borrowed from the field of Implicit Computational Complexity (ICC), allowing to work with composed statements called “Chunks” to detect more quasi-invariants. Based on an optimization idea given on a WHILE language, we provide a transformation method - reusing ICC concepts and techniques [8, 10] - to compilers. This new analysis computes an invariance degree for each statement or chunks of statements by building a new kind of dependency graph, finds the “maximum” or “worst” dependency graph for loops, and recognizes if an entire block is Quasi-Invariant or not. This block could be an inner loop, and in that case the computational complexity of the overall program can be decreased. In this paper, we introduce the theory around this concept and present a prototype analysis pass implemented on LLVM. We already implemented a proof of concept on a toy C parser (https://github.com/ThomasRuby/LQICM_On_C_Toy_Parser) analysing and transforming the AST representation. In a very near future, we will implement the corresponding transformation within our prototype LLVM pass and provide benchmarks comparisons.

AB - Several techniques for analysis and transformations are used in compilers. Among them, the peeling of loops for hoisting quasi-invariants can be used to optimize generated code, or simply ease developers’ lives. In this paper, we introduce a new concept of dependency analysis borrowed from the field of Implicit Computational Complexity (ICC), allowing to work with composed statements called “Chunks” to detect more quasi-invariants. Based on an optimization idea given on a WHILE language, we provide a transformation method - reusing ICC concepts and techniques [8, 10] - to compilers. This new analysis computes an invariance degree for each statement or chunks of statements by building a new kind of dependency graph, finds the “maximum” or “worst” dependency graph for loops, and recognizes if an entire block is Quasi-Invariant or not. This block could be an inner loop, and in that case the computational complexity of the overall program can be decreased. In this paper, we introduce the theory around this concept and present a prototype analysis pass implemented on LLVM. We already implemented a proof of concept on a toy C parser (https://github.com/ThomasRuby/LQICM_On_C_Toy_Parser) analysing and transforming the AST representation. In a very near future, we will implement the corresponding transformation within our prototype LLVM pass and provide benchmarks comparisons.

KW - Compilers

KW - Complexity

KW - Loop invariants

KW - Optimization

KW - Quasi-invariants

KW - Static analysis

KW - Transformations

UR - http://www.scopus.com/inward/record.url?scp=85031424748&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-68167-2_7

DO - 10.1007/978-3-319-68167-2_7

M3 - Article in proceedings

AN - SCOPUS:85031424748

SN - 978-3-319-68166-5

T3 - Lecture notes in computer science

SP - 91

EP - 108

BT - Automated Technology for Verification and Analysis

A2 - D'Souza, Deepak

A2 - Kumar, K. Narayan

PB - Springer

Y2 - 3 October 2017 through 6 October 2017

ER -

ID: 188486394