@inproceedings{b8fc0087e201432a95cabe2ebcc083a6,
title = "Loop quasi-invariant chunk motion by peeling with statement composition",
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' 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 [9, 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. We already implemented a proof of concept on a toy C parser1 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.",
author = "Jean-Yves Moyen and Thomas Rubiano and Thomas Seiller",
year = "2017",
month = apr,
day = "18",
doi = "10.4204/EPTCS.248.9",
language = "English",
series = "Electronic Proceedings in Theoretical Computer Science",
publisher = "Open Publishing Association",
pages = "47--59",
editor = "Guillaume Bonfante and Georg Moser",
booktitle = "Proceedings 8th Workshop on Developments in Implicit Computational Complexity and 5th Workshop on Foundational and Practical Aspects of Resource Analysis",
note = "8th Workshop on Developments in Implicit Computational Complexity and 5th Workshop on Foundational and Practical Aspects of Resource Analysis ; Conference date: 22-04-2017 Through 23-04-2017",
}