Loop quasi-invariant chunk detection

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

  • 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.

OriginalsprogEngelsk
TitelAutomated Technology for Verification and Analysis : 15th International Symposium, ATVA 2017, Pune, India, October 3–6, 2017, Proceedings
RedaktørerDeepak D'Souza, K. Narayan Kumar
Antal sider18
ForlagSpringer
Publikationsdato2017
Sider91-108
ISBN (Trykt)978-3-319-68166-5
ISBN (Elektronisk)978-3-319-68167-2
DOI
StatusUdgivet - 2017
Begivenhed15th International Symposium on Automated Technology for Verification and Analysis - Pune, Indien
Varighed: 3 okt. 20176 okt. 2017
Konferencens nummer: 15

Konference

Konference15th International Symposium on Automated Technology for Verification and Analysis
Nummer15
LandIndien
ByPune
Periode03/10/201706/10/2017
NavnLecture notes in computer science
Vol/bind10482
ISSN0302-9743

ID: 188486394