Skip to Main content Skip to Navigation
Book sections

Rec2Poly: Converting Recursions to Polyhedral Optimized Loops Using an Inspector-Executor Strategy

Salwa Kobeissi 1, 2 Alain Ketterlin 1, 2 Philippe Clauss 1, 2
1 CAMUS - Compilation pour les Architectures MUlti-coeurS
Inria Nancy - Grand Est, ICube - Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie
Abstract : In this paper, we propose Rec2Poly, a framework which detects automatically if recursive programs may be transformed into affine loops that are compliant with the polyhedral model. If successful, the replacing loops can then take advantage of advanced loop optimizing and parallelizing transformations as tiling or skewing. Rec2Poly is made of two main phases: an offline profiling phase and an inspector-executor phase. In the profiling phase, the original recursive program, which has been instrumented, is run. Whenever possible, the trace of collected information is used to build equivalent affine loops from the runtime behavior. Then, an inspector-executor program is automatically generated, where the inspector is made of a light version of the original recursive program, whose aim is reduced to the generation and verification of the information which is essential to ensure the correctness of the equivalent affine loop program. The collected information is mainly related to the touched memory addresses and the control flow of the so-called "impacting" basic blocks of instructions. Moreover, in order to exhibit the lowest possible time-overhead, the inspector is implemented as a parallel process where several memory buffers of information are verified simultaneously. Finally, the executor is made of the equivalent affine loops that have been optimized and parallelized.
Document type :
Book sections
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download
Contributor : Philippe Clauss <>
Submitted on : Monday, October 19, 2020 - 2:52:05 PM
Last modification on : Thursday, November 19, 2020 - 2:10:06 PM


Files produced by the author(s)



Salwa Kobeissi, Alain Ketterlin, Philippe Clauss. Rec2Poly: Converting Recursions to Polyhedral Optimized Loops Using an Inspector-Executor Strategy. SAMOS 2020: Embedded Computer Systems: Architectures, Modeling, and Simulation, pp.96-109, 2020, ⟨10.1007/978-3-030-60939-9_7⟩. ⟨hal-02971434⟩



Record views


Files downloads