SpringerOpen Newsletter

Receive periodic news and updates relating to SpringerOpen.

This article is part of the series Synchronous Paradigm in Embedded Systems.

Open Access Open Badges Research Article

Code Generation in the Columbia Esterel Compiler

Stephen A Edwards* and Jia Zeng

Author Affiliations

Department of Computer Science, Columbia University, New York, NY 10027, USA

For all author emails, please log on.

EURASIP Journal on Embedded Systems 2007, 2007:052651  doi:10.1155/2007/52651

The electronic version of this article is the complete one and can be found online at: http://jes.eurasipjournals.com/content/2007/1/052651

Received:1 June 2006
Revisions received:21 November 2006
Accepted:18 December 2006
Published:27 February 2007

© 2007 Edwards and Zeng

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


The synchronous language Esterel provides deterministic concurrency by adopting a semantics in which threads march in step with a global clock and communicate in a very disciplined way. Its expressive power comes at a cost, however: it is a difficult language to compile into machine code for standard von Neumann processors. The open-source Columbia Esterel Compiler is a research vehicle for experimenting with new code generation techniques for the language. Providing a front-end and a fairly generic concurrent intermediate representation, a variety of back-ends have been developed. We present three of the most mature ones, which are based on program dependence graphs, dynamic lists, and a virtual machine. After describing the very different algorithms used in each of these techniques, we present experimental results that compares twenty-four benchmarks generated by eight different compilation techniques running on seven different processors.


  1. A Benveniste, P Caspi, SA Edwards, N Halbwachs, P Le Guernic, R de Simone, The synchronous languages 12 years later. Proceedings of the IEEE 91(1), 64–83 (2003). Publisher Full Text OpenURL

  2. G Berry, G Gonthier, The Esterel synchronous programming language: design, semantics, implementation. Science of Computer Programming 19(2), 87–152 (1992). Publisher Full Text OpenURL

  3. A Benveniste, P Le Guernic, C Jacquemot, The SIGNAL software environment for real-time system specification, design, and implementation. Proceedings of IEEE Control Systems Society Workshop on Computer-Aided Control System Design (CACSD '89), December 1989, Tampa, Fla, USA, 41–49

  4. P Caspi, D Pilaud, N Halbwachs, JA Plaice, LUSTRE: a declarative language for programming synchronous systems. Proceedings of the Symposium on Principles of Programming Languages (POPL '87), January 1987, Munich, Germany, 178–188

  5. SA Edwards, Tutorial: compiling concurrent languages for sequential processors. ACM Transactions on Design Automation of Electronic Systems 8(2), 141–187 (2003). Publisher Full Text OpenURL

  6. AC Nácul, T Givargis, Code partitioning for synthesis of embedded applications with phantom. Proceedings of IEEE/ACM International Conference on Computer-Aided Design (ICCAD '04), November 2004, San Jose, Calif, USA, 190–196

  7. J Ferrante, KJ Ottenstein, JD Warren, The program dependence graph and its use in optimization. ACM Transactions on Programming Languages and Systems 9(3), 319–349 (1987). Publisher Full Text OpenURL

  8. X Li, R von Hanxleden, A concurrent reactive Esterel processor based on multi-threading. Proceedings of the 21st Annual ACM Symposium on Applied Computing (SAC '06), April 2006, Dijon, France 1, 912–917

  9. PS Roop, Z Salcic, MW Sajeewa Dayaratne, Towards direct execution of Esterel programs on reactive processors. Proceedings of the 4th ACM International Conference on Embedded Software (EMSOFT '04), September 2004, Pisa, Italy, 240–248

  10. D Potop-Butucaru, Optimizations for faster execution of Esterel programs. Proceedings of the 1st International Conference on Formal Methods and Models for Codesign (MEMOCODE '03), June 2003, Mont St. Michel, France, 227–236

  11. SA Edwards, An Esterel compiler for large control-dominated systems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 21(2), 169–183 (2002). Publisher Full Text OpenURL

  12. G Berry, Preemption in concurrent systems. Proceedings of the 13th Conference on Foundations of Software Technology and Theoretical Computer Science, December 1993, Bombay, India, Lecture Notes in Computer Science 761, 72–93

  13. R Cytron, J Ferrante, BK Rosen, MN Wegman, FK Zadeck, Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems 13(4), 451–490 (1991). Publisher Full Text OpenURL

  14. B Simons, J Ferrante, An effficient algorithm for constructing a control flow graph for parallel code. in Tech, ed. by . Rep. TR-03.465 (IBM, Santa Teresa Laboratory, San Jose, Calif, USA, 1993)

  15. J Ferrante, M Mace, B Simons, Generating sequential code from parallel code. Proceedings of the 2nd International Conference on Supercomputing (ICS '88), July 1988, Saint Malo, France, 582–592

  16. B Steensgaard, Sequentializing program dependence graphs for irreducible programs. in Tech, ed. by . Rep. MSR-TR-93-14 (Microsoft, Redmond, Wash, USA, 1993)

  17. V Bertin, M Poize, J Pulou, Une nouvelle méthode de compilation pour le language Esterel [A new method for compiling the Esterel language]. Proceedings of GRAISyHM-AAA, March 1999, Lille, France

  18. D Weil, V Bertin, E Closse, M Poize, P Venier, J Pulou, Efficient compilation of Esterel for realtime embedded systems. Proceedings of International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES '00), November 2000, San Jose, Calif, USA, 2–8

  19. J Banks, JS Carson, BL Nelson, DM Nicol, Discrete-Event System Simulation, 3rd edn. (Prentice-Hall, Upper Saddle River, NJ, USA, 2000)

  20. E Closse, M Poize, J Pulou, P Venier, D Weil, SAXO-RT: interpreting Esterel semantic on a sequential execution structure. Electronic Notes in Theoretical Computer Science 65(5), 864–878 in Proceedings of Synchronous Languages, Applications, and Programming (SLAP '02) Publisher Full Text OpenURL

  21. SS Muchnick, Advanced Compiler Design and Implementation (Morgan Kaufmann, San Francisco, Calif, USA, 1997)

  22. SA Edwards, Compiling Esterel into sequential code. Proceedings of the 37th Design Automation Conference (DAC '00), June 2000, Los Angeles, Calif, USA, 322–327 Association for Computing Machinery OpenURL

  23. D White, G Lüttgen, Accessing databases within Esterel. in Synchronous Programming (SYNCHRON '04), 2005, Dagstuhl, Germany, Dagstuhl Seminar Proceedings, , ed. by Edwards SA, Halbwachs N, Hanxleden RV, Stauner T

  24. M Chiodo, D Engels, P Giusto, et al. A case study in computer-aided co-design of embedded controllers. Design Automation for Embedded Systems 1(1-2), 51–67 (1996). Publisher Full Text OpenURL

  25. EM Sentovich, KJ Singh, L Lavagno, et al. SIS: a system for sequential circuit synthesis. in Tech, ed. by . Rep. UCB/ERL M92/41 (University of California, Berkeley, Calif, USA, 1992)

  26. G Berry, L Cosserat, The Esterel synchronous programming language and its mathematical semantics. in Seminar on Concurrency, 1984, Heidelberg, Germany, Lecture Notes in Computer Science, vol. 197, , ed. by Brooks SD, Roscoe AW, Winskel G, pp. 389–448

  27. G Gonthier, in Sémantiques et modèles d'exécution des langages réactifs synchrones; application à Esterel. [Semantics and models of execution of the synchronous reactive languages: application to Esterel], Thèse d'informatique PubMed Abstract | PubMed Central Full Text OpenURL

  28. G Berry, Esterel on hardware. Philosophical Transactions of the Royal Society of London. Series A 339, 87–103 (1992). Publisher Full Text OpenURL

  29. SA Edwards, Compiling Esterel into sequential code. Proceedings of the 7th International Conference on Hardware/Software Codesign (CODES '99), May 1999, Rome, Italy, 147–151 Association for Computing Machinery OpenURL

  30. D Potop-Butucaru, in Optimizing for Faster Simulation of Esterel Programs, Ph, ed. by . D. thesis (INRIA, Sophia-Antipolis, France, 2002)

  31. PM Maurer, Event driven simulation without loops or conditionals. Proceedings of IEEE/ACM International Conference on Computer-Aided Design (ICCAD '00), November 2000, San Jose, Calif, USA, 23–26

  32. Barron DW (ed.), Pascal: The Language and Its Implementation (John Wiley & Sons, New York, NY, USA, 1981)

  33. A Goldberg, D Robson, Smalltalk-80: The Language and Its Implementation (Addison-Wesley, Reading, Mass, USA, 1983)

  34. JE Smith, R Nair, Virtual Machines (Morgan Kaufmann, San Francisco, Calif, USA, 2005)

  35. J Lukoschus, in Removing cycles in Esterel programs, Ph, ed. by . D. thesis (Department of Computer Science, Christian-Albrechts-Universität Kiel, Kiel, Germany, 2006)

  36. G Berry, The constructive semantics of pure Esterel draft book, 1999

  37. SA Edwards, O Tardieu, Efficient code generation from SHIM models. Proceedings of the ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES '06), June 2006, Ottawa, Ontario, Canada 2006, 125–134