Loop quasi-invariant chunk detection

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

  • Jean-Yves Moyen
  • Thomas Rubiano
  • Thomas Seiller

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.

Original languageEnglish
Title of host publicationAutomated Technology for Verification and Analysis : 15th International Symposium, ATVA 2017, Pune, India, October 3–6, 2017, Proceedings
EditorsDeepak D'Souza, K. Narayan Kumar
Number of pages18
PublisherSpringer
Publication date2017
Pages91-108
ISBN (Print)978-3-319-68166-5
ISBN (Electronic)978-3-319-68167-2
DOIs
Publication statusPublished - 2017
Event15th International Symposium on Automated Technology for Verification and Analysis - Pune, India
Duration: 3 Oct 20176 Oct 2017
Conference number: 15

Conference

Conference15th International Symposium on Automated Technology for Verification and Analysis
Nummer15
LandIndia
ByPune
Periode03/10/201706/10/2017
SeriesLecture notes in computer science
Volume10482
ISSN0302-9743

    Research areas

  • Compilers, Complexity, Loop invariants, Optimization, Quasi-invariants, Static analysis, Transformations

ID: 188486394