Removing Cycles in Esterel Programs

Synchronous programs may contain cyclic signal interdependencies. This prohibits a static scheduling, which limits the choice of available compilation techniques for such programs. An earlier report has outlined an algorithm which, given a constructive synchronous program, performs a semantics-preserving source-level code transformation that removes cyclic signal dependencies, and also exposes opportunities for further optimization. This report presents a refined algorithm, describes a method for computing the necessary replacement expressions, and presents experimental results obtained with a prototypical implementation of this algorithm using the Columbia Esterel Compiler