Loop Quasi-Invariant Chunk Motion by peeling with statement composition

Jean-Yves Moyen
(Department of Computer Science University of Copenhagen (DIKU))
Thomas Rubiano
(Université Paris 13 - LIPN)
Thomas Seiller
(Department of Computer Science University of Copenhagen (DIKU))

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 - 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. We already implemented a proof of concept on a toy C parser 1 analysing and transforming the AST representation. In this paper, we introduce the theory around this concept and present a prototype analysis pass implemented on LLVM. In a very near future, we will implement the corresponding transformation and provide benchmarks comparisons.

In Guillaume Bonfante and Georg Moser: Proceedings 8th Workshop on Developments in Implicit Computational complExity and 5th Workshop on FOundational and Practical Aspects of Resource Analysis (DICE-FOPARA 2017), Uppsala, Sweden, April 22-23, 2017, Electronic Proceedings in Theoretical Computer Science 248, pp. 47–59.
Published: 18th April 2017.

ArXived at: http://dx.doi.org/10.4204/EPTCS.248.9 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org