Loop quasi-invariant chunk detection

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

T2 - 15th International Symposium on Automated Technology for Verification and Analysis

Y2 - 3 October 2017 through 6 October 2017

ER -