Removing cycles in esterel programs

Lukoschus, Jan

Esterel belongs to the family of synchronous programming languages, which are affected by cyclic signal dependencies. This prohibits a static scheduling, limiting the choice of available compilation techniques for programs with such cycles. This work proposes an algorithm that, given a constructive synchronous Esterel program, performs a semantics-preserving source-level code transformation that removes cyclic signal dependencies. The transformation is divided into two parts: Detection of cycles and iterative resolution of these cycles. It is based on the replacement of cycle signals by a signal expression involving no other cycle signals, thereby breaking the cycle. This transformation of cyclic Esterel programs enables the use of efficient compilation techniques, which are only available for acyclic programs. Furthermore, experiments indicate that the code transformation can even improve code quality produced by compilers that can already handle cyclic programs.



Citation style:

Lukoschus, Jan: Removing cycles in esterel programs. 2006.


Use and reproduction:
No CC License (german copyright law applies)