Léonard Gérard
ABSTRACT
The generation of efficient sequential code for synchronous data-flow languages raises two intertwined issues: control and memory optimization. While the former has been extensively studied, for instance in the compilation of Lustre and Signal, the latter has only been addressed in a restricted manner. Yet, memory optimization becomes a pressing issue when arrays are added to such languages.
This article presents a two-level solution to the memory optimization problem. It combines a compile-time optimization algorithm, reminiscent of register allocation, paired with language annotations on the source given by the designer. Annotations express in-place modifications and control where allocation is performed. Moreover, they allow external functions performing in-place modifications to be safely imported. Soundness of annotations is guaranteed by a semilinear type system and additional scheduling constraints. A key feature is that annotations for well-typed programs do not change the semantics of the language: removing them may lead to less efficient code but will not alter the semantics.
The method has been implemented in a new compiler for a LUSTRE-like synchronous language extended with hierarchical automata and arrays. Experiments show that the proposed approach removes most of the unnecessary array copies, resulting in faster code that uses less memory.
- S. Abu-Mahmeed, C. Mccosh, Z. Budimlić, K. Kennedy, K. Ravindran, K. Hogan, P. Austin, S. Rogers, and J. Kornerup. Scheduling tasks to maximize usage of aggregate variables in place. In CC '09: Proceedings of the 18th International Conference on Compiler Construction, pages 204--219, Berlin, Heidelberg, 2009. Springer-Verlag. Google Scholar
Digital Library
- T. Amagbegnon, L. Besnard, and P. Le Guernic. Implementation of the Data-flow Synchronous Language SIGNAL. In Programming Languages Design and Implementation (PLDI), pages 163--173. ACM, 1995. Google ScholarDigital Library
- H. G. Baker. Unify and conquer. In LFP '90: Proceedings of the 1990 ACM conference on LISP and functional programming, pages 218--226, New York, NY, USA, 1990. ACM. Google ScholarDigital Library
- E. Barendsen and S. Smetsers. Uniqueness type inference. In PLILPS '95: Proceedings of the 7th International Symposium on Programming Languages: Implementations, Logics and Programs, pages 189--206, London, UK, 1995. Springer-Verlag. Google ScholarDigital Library
- A. Benveniste, P. Caspi, S. A. Edwards, N. Halbwachs, P. Le Guernic, and R. De Simone. The synchronous languages twelve years later. In Proceedings of the IEEE, pages 64--83, 2003.Google ScholarCross Ref
- A. Benveniste, P. LeGuernic, and Ch. Jacquemot. Synchronous programming with events and relations: the SIGNAL language and its semantics. Science of Computer Programming, 16:103--149, 1991. Google ScholarDigital Library
- D. Biernacki, J.-L. Colaço, G. Hamon, and M. Pouzet. Clock-directed modular code generation for synchronous data-flow languages. In LCTES '08: Proceedings of the 2008 ACM SIGPLAN-SIGBED conference on Languages, compilers, and tools for embedded systems, pages 121--130, New York, NY, USA, 2008. ACM. Google ScholarDigital Library
- D. Brélaz. New methods to color the vertices of a graph. Commun. ACM, 22(4):251--256, 1979. Google ScholarDigital Library
- P. Caspi, D. Pilaud, N. Halbwachs, and J. A. Plaice. Lustre: a declarative language for real-time programming. In POPL '87: Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, pages 178--188, New York, NY, USA, 1987. ACM. Google ScholarDigital Library
- G. J. Chaitin, M. A. Auslander, A. K. Chandra, J. Cocke, M. E. Hopkins, and P. W. Markstein. Register allocation via coloring. Computer Languages, 6(1):47--57, 1981. Google ScholarDigital Library
- J.-L. Colaço, B. Pagano, and M. Pouzet. A conservative extension of synchronous data-flow with state machines. In ACM International Conference on Embedded Software (EMSOFT'05), Jersey city, New Jersey, USA, September 2005. Google ScholarDigital Library
- P. F. Dietz. Fully persistent arrays (extended array). In WADS '89: Proceedings of the Workshop on Algorithms and Data Structures, pages 67--74, London, UK, 1989. Springer-Verlag. Google ScholarDigital Library
- J.-Y. Girard. Linear logic. Theoretical computer science, 50(1):1--102, 1987. Google ScholarDigital Library
- J. R. Goodman and W.-C. Hsu. Code scheduling and register allocation in large basic blocks. In ICS '88: Proceedings of the 2nd international conference on Supercomputing, pages 442--452, New York, NY, USA, 1988. ACM. Google ScholarDigital Library
- N. Halbwachs, P. Raymond, and C. Ratel. Generating efficient code from data-flow programs. In Third International Symposium on Programming Language Implementation and Logic Programming, Passau, Germany, August 1991.Google ScholarCross Ref
- P. Hudak and A. Bloss. The aggregate update problem in functional programming systems. In POPL '85: Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, pages 300--314, New York, NY, USA, 1985. ACM. Google ScholarDigital Library
- X. Leroy. Formal verification of a realistic compiler. Commun. ACM, 52:107--115, July 2009. Google ScholarDigital Library
- L. Morel. Array Iterators in Lustre: From a Language Extension to Its Exploitation in Validation. EURASIP Journal on Embedded Systems, 2007.Google Scholar
- D. Novillo. TreeSSA a new optimization infrastructure for GCC. In Proceedings of the 2003 GCC Developers' Summit, pages 181--193, 2003.Google Scholar
- M. Odersky. How to make destructive updates less destructive. In POPL '91: Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 25--36, New York, NY, USA, 1991. ACM. Google ScholarDigital Library
- B. Pagano. The optimization of iterators and updates for functional arrays in scade 6. Personal communication, June 2010.Google Scholar
- P. Schnorf, M. Ganapathi, and J. L. Hennessy. Compile-time copy elimination. Softw. Pract. Exper., 23(11):1175--1200, 1993. Google ScholarDigital Library
- P. Wadler. Deforestation: transforming programs to eliminate trees. In Proceedings of the Second European Symposium on Programming, pages 231--248, Amsterdam, The Netherlands, 1988. North-Holland Publishing Co. Google ScholarDigital Library
- P. Wadler. Linear types can change the world! In IFIP TC 2 Working Conference on Programming Concepts and Methods, Sea of Galilee, Israel, pages 347--359. North Holland, 1990.Google Scholar
Index Terms
- A modular memory optimization for synchronous data-flow languages: application to arrays in a lustre compiler
Recommendations
A modular memory optimization for synchronous data-flow languages: application to arrays in a lustre compiler
LCTES '12The generation of efficient sequential code for synchronous data-flow languages raises two intertwined issues: control and memory optimization. While the former has been extensively studied, for instance in the compilation of Lustre and Signal, the ...
Clock-directed modular code generation for synchronous data-flow languages
LCTES '08The compilation of synchronous block diagrams into sequential imperative code has been addressed in the early eighties and can now be considered as folklore. However, separate, or modular, code generation, though largely used in existing compilers and ...
Clock-directed modular code generation for synchronous data-flow languages
LCTES '08: Proceedings of the 2008 ACM SIGPLAN-SIGBED conference on Languages, compilers, and tools for embedded systemsThe compilation of synchronous block diagrams into sequential imperative code has been addressed in the early eighties and can now be considered as folklore. However, separate, or modular, code generation, though largely used in existing compilers and ...
Comments